max Z = - 5 x1 + 2 x2 ;
В В
Розв'язання . Перш чем записатися двоїсту задачу, звітність, пряму задачу звесті до стандартного вигляд. Оскількі цільова функція F максімізується и всістемі обмежень є нерівності, то їх слід звесті до увазі В«В». Тому перше обмеження задачі помножімо на (-1). Отрімаємо:
max Z = - 5 x1 + 2 x2 ;
В
Тепер за відповіднімі правилами складемо двоїсту задачу:
min F = - y1 + 5 y2 ;
В
Оскількі запісані задачі сіметрічні, то будь-яку з них можна розв'язати симплекс-методом. Наприклад, візначімо спочатку оптимальний план прямої задачі. Для цього застосуємо алгоритм симплекс-методу.
1. max Z = - 5 x1 + 2 x2 + 0 x3 + 0 x4 ;
В
2. векторна форма запису системи обмежень має вигляд:
,
де,,,,.
У Системі векторів для Утворення початкових одінічного базису відсутній один вектор. Тому введемо Штучний змінну в перше обмеження.
3. розширено завдання лінійного програмування буде такою:
max Z = - 5 x1 + 2 x2 + 0 x3 + 0 x4 - М x5 ;
В
У Цій задачі х 4 та х +5 - базісні змінні, а х1, х2, х3 - Вільні. Нехай х1 = х2 = х3 = 0, тоді х4 = 5; х5 = 1.
Перший опорний план задачі:
X0 = (0, 0, 0, 5, 1), Z0 = - M.
Зх Останньоі симплекс-табліці запішемо оптимальний план прямої задачі :
Х * = (0; 5/3; 2/3; 0), Z max = 10/3.
Згідно Зі співвідношенням двоїстості за дерло теореми можна вісновуваті, что оптимальний план двоїстої задачі існує и min F = max Z = 10/3.
компоненти вектора Y * (Оптимальний план двоїстої задачі) візначімо за формулою:
,
де та містіться в стовпчік В«СбазВ» Останньоі симплекс-табліці;
.
Матриця D-1 такоже містіться в Останній симплекс-табліці у стовпчік змінніх В« x5 В» та В« X4 В», Які утворювалі початковий базис. p> Отже,
,
min F = - 1 х 0 + 5 х 2/3 = 10/3. br/>
застосувались для розв'язування прямої задачі симплекс-метод, ми нашли ее оптимальний план, а потім визначили оптимальний розв'язок двоїстої задачі за помощью СПІВВІДНОШЕНЬ Першої теореми двоїстості.
До заданої задачі лінійного програмування записатися двоїсту задачу. Розв'язано двоїсту задачу графічно, візначіті оптимальний план прямої задачі.
min Z = x1 + 2 x2 + 2 x3 ;
В
Розв'язання . За відповіднімі правилами побудуємо двоїсту задачу:
мах F = y1 + 4 y2 ;
В
Зауважімо, что задачі несіметрічні, и того змінна у1, что відповідає первом рівнянню в Системі обмежень прямої задачі, может мати будь-який знак, а змінна у2 - позбав невід'ємна.
Двоїста задача має Дві змінні, а отже, ее можна розв'язати графічно (рис. 3.2).
В
Рис. 3.2
Найбільшого Значення цільова функція двоїстої задачі F досягає в точці В багатокутніка ABCD . Ее координат та візначімо розв'язанням системи рівнянь
В
Отже, Y * = (- 2/3, 4/3); мах F = +1 х (- 2/3) + 4 х 4/3 = 14/3. p> Оптимальний план прямої задачі візначімо помощью СПІВВІДНОШЕНЬ Другої теореми двоїстості.
Підставімо Y * у систему обмежень двоїстої задачі и з'ясуємо, як віконуються обмеження цієї задачі:
В
Оскількі перше обмеження для оптимального плану двоїстої задачі віконується як строга нерівність, то вісновуємо, что перша змінна прямої задачі дорівнюватіме нулю х 1 = 0 (Перша частина Другої теореми двоїстості). p> Тепер проаналізуємо оптимальний план двоїстої задачі. Оскількі одного компонента планом у2 = 4/3 додатного, то друга обмеження прямої задачі для Х * віконуватіметься як строге рівняння (друга частина Другої теореми двоїстості).
об'єднуючи здобути інформацію, можна записатися систему обмежень прямої задачі як систему двох рівнянь, в якій х1 = 0, та візначіті Решті змінніх:
В
тоб Х * = (0; 5/3, 2/3), min Z = 1 х 0 + 2 х 5/3 + 2 х 2/3 = 14/3. p> Умова min Z = max F = 14/3 віконується, и того Х * = (0; 5/3; 2/3); Y * = (- 2/3; 4/3) є оптимальними планами відповідно прямої та двоїстої задач. p> Візначіті, чі є оптимальними Такі плани сформульованої задачі лінійного програмування:
min Z = 12 x1 - 4 x2 + ...
