Лабораторная работа №3 по "Основам теории систем" (Теория двойственности в задачах линейного програм...
Реферат - Компьютеры, программирование
Другие рефераты по предмету Компьютеры, программирование
,3-0,300-1011,7T000,320,1200,40,6005,28. Значение целевой функции при этом равно 5,28.
2. Решение по второй теореме двойственности.
Согласно второй теореме двойственности, планы и начальной и двойственной задачи соответственно являются оптимальными тогда и только тогда, когда выполняются соотношения:
(5)
(6)
Покомпонентно для наших задач эти соотношения записываются следующим образом:
(5).
(6)
Из системы (5) видно, что во втором и третьем уравнениях в скобках получается ноль, поскольку и положительны, . Из системы (6) получаем, что , поскольку в третьем и четвёртом уравнениях в скобках получаются положительные числа.
Из первого и третьего уравнений системы (5) имеем:
откуда
Таким образом, .
3. Решение с помощью симплекс-таблицы исходной задачи.
Запишем еще раз оптимальную симплекс-таблицу исходной задачи:
44,55,867,5000MMСвБ.П.X1X2X3X4X5X6X7X8X9X10В4,5X21,41000200-0,200,40X80,12000,20,30,601-0,4600,125,8X3-0,40111-2001,200,60X70,12000,20,3-0,4100,54-10,32F-0,0200-0,2-1,7-2,600-6,0605,28FM00000000-1-10Из теории известно, что справедливы следующие формулы: (7); (8).
В системе ограничений (2) исходной задачи переменной соответствует первое ограничение, содержащее базисную переменную , переменной второе, содержащее базисную переменную , переменной третье, содержащее базисную переменную и четвёртое с переменной . Запишем условие (7) для оценок ,, и приведенной симплекс-таблицы: ; ; ; ;
Теперь запишем условие (8) для нашего случая:
, что покомпонентно записывается как: , , , , откуда , , ,
С учетом того, что мы решали симплекс-методом не исходную задачу (1), а задачу в канонической форме (2), т.е. по оптимальной симплекс-таблице мы можем найти решение двойственной задачи к канонической форме исходной задачи. Очевидно, задача в симметричной и канонической форме две разные задачи, отличающиеся знаком и количеством ограничений в двойственных задачах. Более того, так как все ограничения в канонической задаче равенства, то в двойственной задаче все могут быть любого знака, поэтому наши не являются ошибкой. Но нам необходимо решить не двойственную к канонической задаче, а двойственную к симметричной. Если сделать замену , то двойственная задача к симметричной задаче примет форму двойственной к канонической задаче. Следовательно, или .
4. Решение через матрицу, обратную к базисной.
Оптимальное решение двойственной задачи можно найти по формуле . Как видно из оптимальной симплекс-таблицы, . Тогда . Соответственно,
.
Получим:
,
Откуда .
Таким образом, мы видим, что всеми четырьмя способами было получено одно и то же решение: ;.
Экономическая интерпретация трех теорем двойственности.
Согласно первой теореме двойственности, если одна из пары двойственных задач имеет оптимальный план, то и другая имеет оптимальный план, причем значения функций цели при оптимальных планах равны между собой; если же целевая функция одной из задач неограниченна, то другая совсем не имеет планов, и наоборот.
В нашем случае пара задач имеет оптимальные планы, значения целевых функций при которых равны 5,28. Экономический смысл этого состоит в том, что в оптимальном плане минимальные затраты фирмы на производство тонны сплава равны максимальной прибыли некой другой фирмы от продажи первой фирме необходимых для производства ресурсов по условным ценам, равным двойственным оценкам этих ресурсов.
Как было указано выше, вторая теорема двойственности заключается в выполнении соотношений дополняющей нежесткости в случае оптимальности планов пары задач (соотношения (5) и (6)). Приведем сначала экономическую интерпретацию условия (6). Каждому из четырёх "ресурсов" исходной задачи соответствует его двойственная оценка, или условная цена (,, и соответственно). В случае положительности двойственной оценки (в нашем случае и ) справедливы равенства
,
т.е. первый и второй "ресурсы" используются полностью и являются дефицитными. Следует оговориться, что первое равенство выполняется всегда, в противном случае задача не имеет решения. Это логически понятно, поскольку сумма частей всегда равна целому. Что касается третьего и четвёртого ресурсов, то они имеют нулевую двойственную оценку, т.е. эти ресурсы не является дефицитным. Рассмотрим теперь условие (5). Поскольку , то справедливы неравенства:
.
Экономически это значит, что затраты на сырье №1, 4 и 5 превосходят возможные затраты в случае закупки отдельных ресурсов, поэтому эти виды сырья использоваться не будут. С другой стороны, ,, следовательно,
т.е. затраты на сырье первого и второго вида равны альтернативным затратам на производство, значит эти виды сырья будут использоваться.
Третья теорема двойственности позволяет определить зависимость изменения целевой функции начальной задачи от изменения запасов "ресурсов": , т.е. в нашем случае как изменяются минимальные издержки на производство единицы сплава в зависимости от изменения "ресурсов". Так, пусть, например, максимальная доля олова увеличится на 0,1, т.е. до 40 %. Тогда, по третьей теореме двойственности, минимальные издержки на производство единицы сплава уменьшатся на [у.е.]. С другой стороны, изменение минимальной доли цинка или свинца не приведет к изменению минимальных издержек, поскольку их двойственные оценки равны нулю. Но двойственные оценки позволяют о влиянии на целевую функцию не любых изменений ресурсов, а лишь таких, какие не приводят к недопустимости оптимального решения.