Смекни!
smekni.com

Математичне програмування (стр. 2 из 3)

В якості ведучого виберемо стовпець, відповідної змінної x2, Так як це найбільший коефіцієнт по модулю.

План Базис В x1 x2 x3 x4 x5 x6
5 x1 8 1 0 0 0.2308 0.3077 0
x2 1 0 1 0 0.0769 -0.2308 0
x3 11 0 0 1 0.8462 -0.5385 -1
Індексний рядок F(X5) 66 0 0 0 2 2 1M

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

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

x1 = 8

x2 = 1

x3 = 11

F(X) = 8*8 + 2*1 = 66


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

2y1+3y2+y3≥8

5y1+4y2-3y3≥2

10y1+28y2+5y3 => min

y1 ≤ 0

y2 ≥ 0

y3 ≥ 0

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

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

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

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

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

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

Оптимальний план двоїстої задачі дорівнює:

y1 = 0

y2 = 2

y3 = 2

Z(Y) = 10*0+28*2+5*2 = 66


Завдання 3

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

1 4 7 2 3 300
1 5 3 1 6 90
2 1 3 1 4 70
100 20 70 100 180

Розв’язок

Побудова математичної моделі. Нехай xij — кількість продукції, що перевозиться з і-го пункту виробництва до j-го споживача

. Оскільки
, то задачу треба закрити, тобто збалансувати (зрівняти) поставки й потреби:

У нашому випадку робиться це введенням фіктивного постачальника, оскільки

З уведенням фіктивного постачальника в транспортній таблиці додатково заявляється n робочих клітинок.Ціни, додатковим клітинкам, щоб фіктивний рядок був нейтральним щодо оптимального вибору планових перевезень, призначаються усі рівні нулю.


Занесемо вихідні дані у таблицю.

В1 В2 В3 В4 В5 Запаси
А1 1 4 7 2 3 300
А2 1 5 3 1 6 90
А3 2 1 3 1 4 70
А4 0 0 0 0 0 10
Потреби 100 20 70 100 180

Забезпечивши закритість розв'язуваної задачі, розпочинаємо будувати математичну модель даної задачі:

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

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

Загальні витрати, пов’язані з транспортуванням продукції, визначаються як сума добутків обсягів перевезеної продукції на вартості транспортування од. продукції до відповідного замовника і за умовою задачі мають бути мінімальними. Тому формально це можна записати так:

minZ=1x11+4x12+7x13+2x14+3x15+1x21+5x22+3x23+1x24+6x25+2x31+1x32+3x33+1x34+ +4x35+0x41+0x42+0x43+0x44+0x45.

Загалом математична модель сформульованої задачі має вигляд:

minZ=1x11+4x12+7x13+2x14+3x15+1x21+5x22+3x23+1x24+6x25+2x31+1x32+3x33+1x34+ +4x35+0x41+0x42+0x43+0x44+0x45.

за умов:

Запишемо умови задачі у вигляді транспортної таблиці та складемо її перший опорний план у цій таблиці методом «північно-західного кута».

Ai Bj ui
b1 = 100 b2 = 20 b3 = 70 b4=100 b5=180
а1 = 300 1100 420 7[-]70 2100 3[+]10 u1 = 0
а2 = 90 1 5 3[+] 1 6[-]90 u2 = 3
а3 = 70 2 1 3 1 470 u3 = 1
а4 = 10 0 0 0 0 010 u4 = -3
vj v1 =1 v2 =4 v3 =7 v4 =2 v5 =3

В результаті отримано перший опорний план, який є допустимим, оскільки всі вантажі з баз вивезені, потреба магазинів задоволена, а план відповідає системі обмежень транспортної задачі.

Підрахуємо число зайнятих клітин таблиці, їх 8, а має бути m+n-1=8. Отже, опорний план є не виродженим.

Перевіримо оптимальність опорного плану. Знайдемо потенціали ui, vi. по зайнятих клітинам таблиці, в яких ui + vi = cij, вважаючи, що u1 = 0:

u1=0, u2=3, u3=1, u4=-3, v1=1, v2=4, v3=7 v4=2, v5=3. Ці значення потенціалів першого опорного плану записуємо у транспортну таблицю.

Потім згідно з алгоритмом методу потенціалів перевіряємо виконання другої умови оптимальності ui + vj ≤ cij (для порожніх клітинок таблиці).

Опорний план не є оптимальним, тому що існують оцінки вільних клітин для яких ui + vi > cij

(2;1): 3 + 1 > 1; ∆21 = 3 + 1 - 1 = 3

(2;2): 3 + 4 > 5; ∆22 = 3 + 4 - 5 = 2

(2;3): 3 + 7 > 3; ∆23 = 3 + 7 - 3 = 7

(2;4): 3 + 2 > 1; ∆24 = 3 + 2 - 1 = 4

(3;2): 1 + 4 > 1; ∆32 = 1 + 4 - 1 = 4

(3;3): 1 + 7 > 3; ∆33 = 1 + 7 - 3 = 5

(3;4): 1 + 2 > 1; ∆34 = 1 + 2 - 1 = 2

(4;2): -3 + 4 > 0; ∆42 = -3 + 4 - 0 = 1

(4;3): -3 + 7 > 0; ∆43 = -3 + 7 - 0 = 4

max(3,2,7,4,4,5,2,1,4) = 7

Тому від нього необхідно перейти до другого плану, змінивши співвідношення заповнених і порожніх клітинок таблиці. Вибираємо максимальну оцінку вільної клітини (2;3): 3. Для цього в перспективну клітку (2;3) поставимо знак «+», а в інших вершинах багатокутника чергуються знаки «-», «+», «-». Цикл наведено в таблиці.

Тепер необхідно перемістити продукцію в межах побудованого циклу. З вантажів хij що стоять в мінусових клітинах, вибираємо найменше, тобто у = min (1, 3) = 70. Додаємо 70 до обсягів вантажів, що стоять в плюсових клітинах і віднімаємо 70 з хij, що стоять в мінусових клітинах. В результаті отримаємо новий опорний план.

Усі інші заповнені клітинки першої таблиці, які не входили до циклу, переписуємо у другу таблицю без змін. Кількість заповнених клітинок у новій таблиці також має відповідати умові невиродженості плану, тобто дорівнювати (n + m – 1).

Отже, другий опорний план транспортної задачі матиме такий вигляд:

Ai Bj ui
b1 = 100 b2 = 20 b3 = 70 b4=100 b5=180
а1 = 300 1100 420 7 2[-]100 3[+]80 u1 = 0
а2 = 90 1 5 370 1[+] 6[-]20 u2 = 3
а3 = 70 2 1 3 1 470 u3 = 1
а4 = 10 0 0 0 0 010 u4 = -3
vj v1 =1 v2 =4 v3 =0 v4 =2 v5 =3

Перевіримо оптимальність опорного плану. Знайдемо потенціали ui, vi. по зайнятих клітинам таблиці, в яких ui + vi = cij, вважаючи, що u1 = 0.

Опорний план не є оптимальним, тому що існують оцінки вільних клітин для яких ui + vi > cij

(2;1): 3 + 1 > 1; ∆21 = 3 + 1 - 1 = 3

(2;2): 3 + 4 > 5; ∆22 = 3 + 4 - 5 = 2

(2;4): 3 + 2 > 1; ∆24 = 3 + 2 - 1 = 4

(3;2): 1 + 4 > 1; ∆32 = 1 + 4 - 1 = 4

(3;4): 1 + 2 > 1; ∆34 = 1 + 2 - 1 = 2

(4;2): -3 + 4 > 0; ∆42 = -3 + 4 - 0 = 1

max(3,2,4,4,2,1) = 4


Вибираємо максимальну оцінку вільної клітини (2;4): 1

Для цього в перспективну клітку (2;4) поставимо знак «+», а в інших вершинах багатокутника чергуються знаки «-», «+», «-». Цикл наведено в таблиці.

З вантажів хij що стоять в мінусових клітинах, вибираємо найменше, тобто у = min (2, 5) = 20. Додаємо 20 до обсягів вантажів, що стоять в плюсових клітинах і віднімаємо 20 з Хij, що стоять в мінусових клітинах. В результаті отримаємо новий опорний план.

Ai Bj ui
b1 = 100 b2 = 20 b3 = 70 b4=100 b5=180
а1 = 300 1100 4[-]20 7 280 3[+]100 u1 = 0
а2 = 90 1 5 370 120 6 u2 = -1
а3 = 70 2 1[+] 3 1 4[-]70 u3 = 1
а4 = 10 0 0 0 0 010 u4 = -3
vj v1 =1 v2 =4 v3 =4 v4 =2 v5 =3

Перевіримо оптимальність опорного плану. Знайдемо потенціали ui, vi. по зайнятих клітинам таблиці, в яких ui + vi = cij, вважаючи, що u1 = 0.

Опорний план не є оптимальним, тому що існують оцінки вільних клітин для яких ui + vi > cij

(3;2): 1 + 4 > 1; ∆32 = 1 + 4 - 1 = 4

(3;3): 1 + 4 > 3; ∆33 = 1 + 4 - 3 = 2

(3;4): 1 + 2 > 1; ∆34 = 1 + 2 - 1 = 2

(4;2): -3 + 4 > 0; ∆42 = -3 + 4 - 0 = 1

(4;3): -3 + 4 > 0; ∆43 = -3 + 4 - 0 = 1

max(4,2,2,1,1) = 4


Вибираємо максимальну оцінку вільної клітини (3;2): 1

Для цього в перспективну клітку (3;2) поставимо знак «+», а в інших вершинах багатокутника чергуються знаки «-», «+», «-». Цикл наведено в таблиці.