Первая теорема двойственности

Для прямой задачи:	Для двойственной задачи:
ден. единиц.	=120.

Вторая теорема двойственности

Если . Значит, 1й и 2й ресурсы будут находиться в дефиците.

Значения . Значит, 3й и 4й ресурсы будут находиться в избытке.

Третья теорема двойственности

Изменим значение 1го ресурса на единицу, т.е. и тогда .

Тогда денежных единиц.

Разница ден.ед.  т.е. это составляет столько единиц, сколько их в двойственной оценке 1го ресурса денежных единиц/ед. ресурсов.

Если , то ден.ед., т.е. ден.ед. ( ).

Нужно отметить, что в случае заявки на производство новой продукции, экономическая целесообразность устанавливается по критерию :

Если , производство новой продукции экономически оправдано (для нашего оптимального решения ).

Если , то производство новой продукции экономически нецелесообразно.

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

В случае целочисленных переменных область допустимых решений может состоять из нескольких разрозненных областей. Ниже приводится пример, когда условие целочисленности для исходной задачи №1 приводит к появлению задач №2 и №3 (в задаче №3 ОДР оказывается пустой). Тогда задача №2 распадается еще на две задачи: №4 и №5. Задача №5 распадается еще на две: №6 (ОДР – пустая) и №7. В задаче №4 получено целочисленное решение с большим значением целевой функции, чем в задаче №7 – то же с целочисленным результатом. Вывод ясен: решение заключено в варианте задачи №4. Приведем этот пример.

Найти максимальное значение целевой функции Z= x₁ + 2x₂ при ограничениях:

7x₁ + 5x₂  35 (1)

2x₁ + 3x₂  6 (2)

Значения переменных должны быть неотрицательными и в целых числах. Решение задачи №1: Z = 9,64; x₁=2,42; x₂ =3,61. На рис.2 – это координата точки В. Целочисленный результат переменных не достигнут.

Рис. 2. Две ОДР для случая целочисленных значений переменных

Разобьем ОДР по значению x₂: x₂  3 и x₂  4. Тогда возникнут еще две задачи: №2 и №3 – с теми же выражениями целевой функции и ограничений. Но в задаче №2 указывается: x₁, x₂  0; в задаче №3 значения x₁0; x₂  4.

Проведем горизонтальные прямые x₂ = 3 и x₂ = 4. Теперь видим, что для задачи №3 область допустимых решений – пустое множество, не ограниченное сверху. Для задачи №2 решение существует x₁ = 2,86; x₂ = 3; Z= 8,86. Но целочисленность переменных не достигнута.

Поэтому задача №2 распадается на две: №4 с ОДР1, обозначенную буквами OADFK, №5 с ОДР2, обозначенную буквами MLC (треугольник).

Для ОДР1 в точке F находится целочисленное решение: x₁=2; x₂=3; значение Z = 8. В задаче же №5 значение Z=8,6; x₁=3; x₂=2,8. Это решение находится в угловой точке L(3; 2,8). Поэтому задача №5 распадается на две новые: №6 и №7.

Но в задаче №6 не существует ОДР. А в задаче №7 в точке S(3; 2) существует целочисленное решение, для которого значение функции Z = 7. В точке S значение целевой функции меньше, чем в точке F. Поэтому результат оптимального решения задачи будет однозначным: Z = 8; x₁=2; x₂ = 3. Оптимальное значение целевой функции находится в угловой точке F(2; 3) области, обозначенной буквами OADFKO.

Булевы переменные используются, когда надо дать однозначный ответ: ДА (x₁ = 1), НЕТ (x₂ = 0). Это значит, что принимается первый вариант.

Пример 1. При рассмотрении двух вариантов развития экономики области было получено: x₁ = 1, x₂ = 0. Значит, развивать экономику надо не во втором регионе, а в первом.

Пример 2. В таблице 2 указаны 4 варианта использования ресурсов, величина удельной прибыли и располагаемые значения трудовых ресурсов.

Таблица 2

Варианты	Первый	Второй	Третий	Четвертый	Располагаемые ресурсы
Прибыль	70	80	90	210
Труд	10	15	22	28	50
Финансы	200	180	240	250	650

Требуется выбрать вариант с максимальным значением прибыли.

Целевая функция будет иметь вид:

Z = 70x₁ + 80x₂ + 90x₃ + 210x₄ max

Ограничение по труду: 10x₁+15x₂+22x₃+28x₄  50 (1)

Ограничение по финансовым ресурсам будет в виде:

200x₁+180x₂+240x₃+250x₄  650 (2)

Граничные условия: Все x_j должны быть целыми числами, заключенными в интервале 0  x_j 1.

Результат моделирования: x₃ = 1, x₄ = 1. Значит, следует выбрать третий и четвертый варианты, а первый и второй отклонить. При этом максимальная величина прибыли составит 370 единиц, а сэкономлено будет 160 финансовых единиц.

Дискретная оптимизация предполагает использование булевых переменных.

Пример 3. Требуется поместить жидкий материал в отдельном помещении, в контейнерах формы параллелепипеда, причем его длина «а» может быть только трех размеров: 4,25; 5,5; 6,75 метра. Два других размера: b – ширина, h – высота. Объем контейнера должен быть максимальным.

Целевая функция: V = abh  max. Используем булевы переменные для длины а = 4,25x₁ + 5,5x₂ + 6,75x₃ . Тогда появятся два других ограничения: а  4,25x₁ + 5,5x₂ + 6,75x₃ = 0 (1)

x₁ + x₂ + x₃ = 1 (2)

Дополнительные условия: Все x_j должны быть целыми числами, заключенными в интервале 0  x_j 1.

Результат поиска: x₁ = 1; a = 4,25; b = 0,55; h = 0,55; V = 1,3 м³. Примечательно, что первоначальная стоимость контейнера уменьшилась с 100 денежных единиц до 60.