Пример работы с двойственностью и чувствительностью

Анализ чувствительности оптимального решения – пределы действия теневых цен.

Задача называется нечувствительной, т.е. устойчивой к изменению какого-либо параметра, если при таком изменении структура оптимального решения сохраняется, т.е. сохраняется расположение нулей в оптимальном решении. Например, пусть изменился какой-то параметр и вместо решения Хст=(1 0 0 3 5), мы получили Хопт новое=(2 0 0 4 8). Такое изменение соответствует устойчивому решению. Но если же при изменении мы получили Хнов опт=(1 0,1 0 3,2 0), то такое изменение ведет к неустойчивости оптимального решения. Это все для канонической задачи!!!

Для устойчивой задачи теневые цены действительны.

Во все компьютерных приложениях, где есть линейное программирование, обязательно дается редуцированные цены, теневые цены и значения максимального и минимального увеличения коэффициентов функции цели (цены) и правых частей ограничения (ресурсов). По этим параметрам видно при каких ценах на продукт сохраняется оптимальный полученных выпуск и при каких покупках (продажах) действует теневая цена.

**1

Если решить двойственную задачу, то в результате решения я получаю следующее….

Виртуальный рынок ресрсов установил следующую цену на ресурс: на первый ресурс (30 единиц) нулевую цену, он у нас в излишке, чтобы мы его не продавали, а второй ресурс (6 единиц), у нас в дефиците, мы его израсходовали полностью, следовательно, первый ресурс не покупаем не под каким видом (u реальное не может быть меньше нуля), а продаем 15 единиц за любую реальную цену, второй ресурс – покупаем по цене не больше, чем 1,5 за единичку, а продаем больше, чем 1,5 за единичку, но!!! надо знать зону действия теневой цены. Легко с помощью математических преобразований получить допустимое максимальное увеличение правой части при сохранении структуры оптимального решения. Для первого ресурса 30 может увеличиваться до бесконечности, а уменьшаться - не меньше чем до 15 (допустимое увеличение бесконечность, допустимое уменьшение 15). Для второго 6 может увеличиваться до 12, а уменьшаться до 2. Барьер 1 увеличение до 3, а уменьшение до бесконечности.

Только в рамках этих изменений действуют теневые цены и можно говорить о корректности сделки. Если увеличение вне этих рамках - нечего сказать нельзя по разделу!!! (можно сказать не знаю).

Пример 3, на рынке ресурсов предлагается лот из трех единиц второго ресурса за все просят 5 денежных единиц.

02.03.2012

Реализация программы линейного программирования на Excel

Приложение Excel позволяет получать решение задач линейного программирования в том виде, в котором необходимо для экономистов. Для того чтобы использовать программу для решения линейного программирования путем настроек необходимо подключать к системе Solver.

В Excelе решается произвольная задача линейного программирования. Т.е. перевод в каноническую форму осуществляется системой. Переменные используемые в линейном программировании Х1,Х2,Х3 это любые ячейки Excelя. В нашем примере это В1 и В2. Все функции используемые в задаче задаются формулами в Excelе. Всё что слева от формул или от переменных все будут именами этих формул или переменных и в протоколах употребляться под этими именами.

Не Надо в поле ограничения записывать знак больше или равно

Пишется имя и значение левой части R1, записана формула, статус не связан (если связан – четкое равенство).

С помощью статуса легко определяется слековые и сурпласовые переменные, которые используются в Excelе. Т.е. для ограничения R1 слековая переменная была Х3, а Х3 оптимальное равно 15. Для ограничение R1 слековое Х4 оптимальное равно 0, следовательно Х4 не базисное. Для R3 не связанное сурпласовая переменная Х4 оптимальная равна 2, она базисная. Таким образом легко определить базисные переменные X2,X3, X5, небазисные Х1, Х4

Х1 и Х2 это результат исходной задачи, а полученные Х3 и Х4 и Х5 к Х1 и Х2 это решение канонической задачи.

Отчет по устойчивости.

Нормированная стоимость для основных переменных (редуцированная цена) указаны прямо для слековых переменных – это соответствующие теневая цена с обратным знаком, т.е. нормированная стоимость для Х3 равна 0 (R1). Для Х4 равна -1,5. А для Х5 = 0.

В этом листе в конце каждой таблицы указывается анализ на чувствительность соответствующего параметра, если параметр укладывается в увеличение (уменьшение), то оптимальный базис сохраняется (в нашем случает базисные Х2, Х3 и Х5, а не базисные Х1 и Х4).

То что касается правой части, то допустимое увеличение или допустимое уменьшение – пределы, когда еще сохраняется оптимальный базис, действует и действует теневая цена.

Например, для второго ресурса теневая цена 1,5 действует, если его покупать не более чем 6 единиц и продавать не более чем 4 единицы. Т.е. можно решить следующую задачу: предлагаю купить 3 единички второго ресурса за все прошу 4 денежных единички. Будем брать, так как теневая цена равна 1,5 реальная цена равна 4/3 теневая цена больше реальной цены, покупать есть смысл.

Теневая цена это и есть U оптимальное.

Задание №2. Решить с помощью приложения Excel, получить решение, распечатать листы отчет по резльутам и отчет по устойчивости.

Написать кононическую задачу и для не по распечатке написать Х оптимальое

Написать двойственную задачу и по отчету по устойчивости, написать для неё оптимальное решение.

Линейное программирование в примерах и задачах.

Кузнецов

Дата добавления: 2014-01-03