Решение двойственной задачи

Решение двойственной задачи

Введем переменные: x₁ — количество кабеля типа I, x₂ — количество кабеля типа II. По определению эти переменные должны быть неотрицательны. При связи, использующей x₁ кабелей I типа и x₂ кабелей II типа, могут использоваться 5x₁+x₂ телефонных каналов, 5x₁+4x₂ телеграфных каналов и 2x₁+5x₂ фототелеграфных каналов. Для осуществления связи необходимо наличие не менее требуемого количества каналов. Получаем ограничения на количества имеющихся каналов:

Затраты на осуществление связи, имеющей x₁ кабелей I типа и x₂ кабелей II типа, составят: (11x₁+x₂)1000=11 000x₁+1000x₂ условных единиц. Получаем математическую модель задачи:

5x₁+x₂?12.

• 5x₁+4x₂?33
• 2x₁+5x₂?20

x₁; x₂?0, целое.

P (x)=11 000×1+1000×2?min.

• 5x₁+x₂?12 x₂?12−5x₁
• 5x₁+4x₂?33 x₂?33/4−5x₁/4
• 2x₁+5x₂?20 x₂?4−2x₁/5

x₁; x₂?0, целое. x₁; x₂?0, целое.

Первое неравенство системы ограничений задачи x₂?12−5x₁ описывает полуплоскость, лежащую выше прямой x₂=12−5 x₁, которую строим по точкам (1;7) и (2;2).

Второе неравенство системы ограничений задачи x₂?33/4−5x₁/4 описывает полуплоскость, лежащую выше прямой x₂=33/4−5x₁/4, которую строим по точкам (1;28/4) и (2;23/4).

Третье неравенство системы ограничений задачи x₂?4−2x₁/5 описывает полуплоскость, лежащую выше прямой x₂=4−2x₁/5, которую строим по точкам (1;18/5) и (2;16/5).

Неограниченная сверху область ABC — множество допустимых решений системы ограничений задачи.

Строим линию уровня, т. е. 11000x₁+1000x₂=0 x₂=-11x₁

Вектор-градиент, составленный из коэффициентов целевой функции, указывает направление минимизации F (X). Начало вектора — точка (0; 0), конец — точка (11 000; 1000). Будем двигать эту прямую параллельным образом. Поскольку нас интересует минимальное решение, поэтому двигаем прямую до первого касания обозначенной области.

Прямая F (x) = const пересекает область в точке A. Так как точка A получена в результате пересечения прямых 5x₁+x₂=12 и x₁=0, найдем ее координаты, решив систему уравнений:

5x₁+x₂=12.

x₁=0.

Решив систему уравнений, получим: x₁ = 0, x₂ = 12.

Откуда найдем минимальное значение целевой функции:

F (X) = 11 000*0 + 1000*12 = 12 000.

Задача 2.

Составить двойственную задачу к задаче 1. Найти ее решение по теореме равновесия.

Решение. Составим двойственную задачу к данной.

5x₁+x₂?12.

• 5x₁+4x₂?33
• 2x₁+5x₂?20

x₁; x₂?0, целое.

5y₁+5y₂+2y3?11 000.

y₁+4y₂+5y₃?1000.

y₁; y₂; y₃?0.

F=12y₁+33y₂+20y₃>max.

Найдем оптимальное решение двойственной задачи по теореме равновесия. Запишем условия дополняющей нежесткости.

y₁(5x₁+x₂-12)=0.

y₂(5x₁+4x₂-33)=0.

y₃(2x₁+5x₂-20)=0.

x₁(5y₁+5y₂+2y₃-11 000)=0.

x₂(y₁+4y₂+5y₃-1000)=0.

Подставим в составленную систему оптимальное решение исходной задачи X_опт=(0;12):

y₁(5*0+12−12)=0.

y₂(5*0+4*12−33)=0.

y₃(2*0+5*12−20)=0.

x₁(5y₁+5y₂+2y₃-11 000)=0.

x₂(y₁+4y₂+5y₃-1000)=0.

y₁(0+0)=0.

y₂(0+33−33)=0.

y₃(0+60−20)=0.

x₁(5y₁+5y₂+2y₃-11 000)=0.

x₂(y₁+4y₂+5y₃-1000)=0.

y₁*0=0;

y₂*0=0.

y₃*40=0; y₃=0.

x₁(5y₁+5y₂+2y₃-11 000)=0.

x₂(y₁+4y₂+5y₃-1000)=0.

Тогда.

x₁(5y₁+5y₂+2*0−11 000)=0.

x₂(y₁+4y₂+5*0−1000)=0.

• 0(5y₁₊5y₂-11 000)=0
• 12(y₁₊4y₂-1000)=0
• 5у1=1000−5у2; у1=200-у2.
• 12(200-у2)+60у2−12 000=0, 48у2=9600, у2=200, у1=0.

Оптимальное решение двойственной задачи.

F=12y₁+33y₂+20y3=12*0+33*200+20*0=6600.

Задача3.

Решить двухкритериальную задачу линейного программирования методом идеальной точки.

решение двойственный равновесие точка Решение:

OABCD — область допустимых решений системы ограничений задачи.

y=4+x/2 y=4 A (0;4).

x=0 x=0.

y=18−3×18−3x=4+x/2 7x/2=14 x=4 B (4;6).

y=4+x/2 y=4+x/2 y=4+x/2 y=6.

y=18−3×18−3x=3x/2−9/2 9х=45 x=5 C (5;3).

y=3x/2−9/2 y=3x/2−9/2 y=3x/2−9/2 y=3.

y=3x/2−9/2 x=3 D (3;0).

y=0 y=0.

Рассмотрим преобразование.

В этом случае,.

O (0;0)>O'(0;0); A (0;4) >A'(12;-4); B (4;6) >B'(-18;-2);

C (5;3)>C'(-36;2); D (3;0) >D'(-27;3).

Точка утопии М*(12,3) — точка, в которой первая и вторая координаты новых точек принимают максимальные значения.

Граница Парето пятиугольника О` A`B`C`D` состоит из отрезков O`D` и О`A`.

Найдем уравнение прямой, проходящей через точки O'(0;0) и A'(12;-4):

Найдем уравнение прямой L, перпендикулярной прямой O`A` и проходящей через точку М:

Таким образом, уравнение искомой прямой имеет вид:.

Найдем точку пересечения полученных перпендикулярных прямых, решив систему из соответствующих уравнений:

v=15.75.

u=6.75.

Находим соответствующие значения x и y:

x=40.5.

y=24.75.