6. Двоїста задача лінійного програмування
Вихідна система обмежень і цільова функція задачі показані на малюнку нижче. <В
при обмеженнях:
В
Рішення: Наведемо систему обмежень до стандартного вигляду:
В
Завдання, двоїста даної матиме вигляд:
,
В
Рішення двоїстої задачі буде виконуватися простим симплекс-методом.
Перетворимо цільову функцію так, щоб вирішувалося завдання мінімізації, і запишемо систему обмежень в стандартній формі для вирішення симплекс-методом. br/>
y6 = 1 - (-2 y1 + 2y2 + y3 + y4 + y5) = 5 - (-3y1 - y2 + y3 + y4)
Ф = 0 - (3y1 + 9y2 + 3y3 + y4)?? min
Побудуємо вихідну симплекс-таблицю для вирішення двоїстої задачі ЛП.
? Y1Y2Y3 Y4 Y5Y61 1/2-2 -12 1/21 1/21 1/21 1/2Y75 1/2-3 -1-1 1/21 1/21 1/20 1 /2Фmin0 -9/23 99 -9/2 3 -9/21 -9/2 0 -9/2
Перший крок симплекс-методу
? Y1Y6Y3 Y4 Y5Y21/2 -11/8 -1 -1/4 1/2 -1/8 1/2 -3/81/2 -3/81/2 -1/8 Y711/2 -11/8-4 -1/41/2 -1/83/2 -3/83/2 -3/8 ВЅ -1/8Фmin-9/2 33/212 3-9/2 3/2-3/2 9/2-7/2 9/2-9/2 3/2
Другий крок симплекс-методу
? Y1Y6Y3 Y4 Y5Y21/2 -11/8 -1 -1/4 ВЅ -1/1 серпня /2 -3/81/2 -3/81/2 -1/8 Y711/2 -11/8-4 -1/41/2 -1/83/2 -3/83/2 -3/81/ 2 -1/8Фmin-9/2 33/212 3-9/2 3/2-3/2 9/2-7/2 9/2-9/2 3/2 Третій крок симплекс-методу
? Y7Y6Y3 Y4 Y5Y2-7/8 -1/4 3/81/81/81/8Y1-11/8-1/4-1/8 -3/8-3/8- 1/8Фmin123 -331-3
Отже, на третьому кроці симплекс-методу знайдено оптимальне рішення задачі мінімізації з наступними результатами: y2 = -7/8, y1 = -11/8, Ф = 12. Для того, щоб знайти значення цільової функції двоїстої задачі, підставимо знайдені значення базисних і вільних змінних у функцію максимізації:
фmax = - Фmin = 3 * (-11/8) + 9 (-7/8) + 3 * 0 + 0 = -12
Так як значення цільової функції прямої і двоїстої задач збігаються, рішення прямої задачі знайдено і дорівнює 12.
Fmin = фmax = -12
7. Рішення задачі цілочислового лінійного програмування методом В«гілок і границьВ»
Перетворимо вихідну завдання таким чином, щоб не виконувалася умова цілочисельності при вирішенні звичайними методами.
В
Вихідний багатокутник рішень задачі цілочисельного програмування.
Для перетвореного багатокутника рішень побудуємо нову систему обм...
