Задачі математичного програмування

Завдання 2

Записати двоїсту задачу до поставленої задачі лінійного програмування. Розв’язати одну із задач симплексним методом і визначити оптимальний план іншої задачі. Оптимальні результати перевірити графічно.

Розв’язок

Розв’яжемо задачу лінійного програмування симплексним методом.

Визначимо мінімальне значення цільової функції F(X) = 4x1+2x2 при наступних умовах-обмежень.

x1-x2≤4

x1+3x2≤6

x1+2x2≥2

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

Оскільки маємо змішані умови-обмеження, то введемо штучні змінні x.

1x1-1x2 + 1x3 + 0x4 + 0x5 = 4

1x1 + 3x2 + 0x3 + 1x4 + 0x5 = 6

1x1 + 2x2 + 0x3 + 0x4-1x5 = 2

Для постановки задачі на мінімум цільову функцію запишемо так:

F(X) = 4x1+2x2 - Mx6 => max

Вважаючи, що вільні змінні рівні 0, отримаємо перший опорний план:

ПланБазисВx1x2x3x4x5х6
0х341-11000
x46130100
х621200-11
Індексний рядокF(X0)0000000

Переходимо до основного алгоритму симплекс-методу.

ПланБазисВx1x2x3x4x5x6min
1x341-110000
x461301002
x621200-111
Індексний рядокF(X1)00000000

Оскільки, в індексному рядку знаходяться негативні коефіцієнти, поточний опорний план неоптимальний, тому будуємо новий план. У якості ведучого виберемо елемент у стовбці х2, оскільки значення коефіцієнта за модулем найбільше.

ПланБазисВx1x2x3x4x5x6min
2x351.5010-0.50.53.33
х43-0.50011.5-1.50
x210.5100-0.50.52
Індексний рядокF(X2)00000000

Даний план, також не оптимальний, тому будуємо знову нову симплексну таблицю. У якості ведучого виберемо елемент у стовбці х2.

План Базис В x1 x2 x3 x4 x5 x6 min
3 x320-3101-12
 X4401011-14
 X121200-110
 Індексний рядок F(X3)00000000
ПланБазисВx1x2x3x4x5x6min
4х520-3101-10
X4204-11000.5
X141-110000
Індексний рядокF(X4)00000000
ПланБазисВx1x2x3x4x5х6
5х53.5000.250.751-1
х20.501-0.250.2500
х14.5100.750.2500
Індексний рядокF(X5)0000000

Оптимальний план можна записати так:

x5 = 3.5

x2 = 0.5

x1 = 4.5

F(X) = 4*4.5 + 2*0.5 = 19

Складемо двоїсту задачу до поставленої задачі лінійного програмування.

y1+y2+y3≥4

-y1+3y2+2y3≥2

4y1+6y2+2y3 => min

y1 ≥ 0

y2 ≥ 0

y3 ≤ 0

Рішення двоїстої задачі дає оптимальну оцінок ресурсів. Використовуючи останню інтиграцію прямої задачі знайдемо,оптимальний план двоїстої задачі. Із теореми двоїстості слідує, що Y = C*A-1.

Сформуємо матрицю A із компонентів векторів, які входять в оптимальний базис.

Визначивши обернену матрицю А-1 через алгебраїчне доповнення, отримаємо:

Як видно із останнього плану симплексної таблиці, обернена матриця A-1 розміщена у стовбцях додаткових змінних.

Тоді Y = C*A-1 =

Запишемо оптимальний план двоїстої задачі:

y1 = 2.5

y2 = 1.5

y3 = 0

Z(Y) = 4*2.5+6*1.5+2*0 = 19


Завдання 3

Розвязати транспортну задачц.

12415200
12131120
21331150
100902003080
Актуально: