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

8x1 + 3x2 + 0x3 + 1x4 + 0x5 = 5

-14x1 + 2x2-11x3 + 0x4 + 1x5 = 3

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

План	Базис	В	x1	x2	x3	x4	x5
0	x4	5	8	3	0	1	0
x5	3	-14	2	-11	0	1
Індексний рядок	F(X0)	0	8	3	-9	0	0

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

План	Базис	В	x1	x2	x3	x4	x5	min
1	x4	5	8	3	0	1	0	1.67
x5	3	-14	2	-11	0	1	1.5
Індексний рядок	F(X1)	0	-14	-27	11	0	0	0

План	Базис	В	x1	x2	x3	x4	x5	min
2	X4	0.5	29	0	16.5	1	-1.5	0.0172
X2	1.5	-7	1	-5.5	0	0.5	0
Индексная строка	F(X2)	40.5	-203	0	-137.5	0	13.5	0

План	Базис	В	x1	x2	x3	x4	x5
3	x1	0.0172	1	0	0.569	0.0345	-0.0517
x2	1.62	0	1	-1.52	0.2414	0.1379
Индексная строка	F(X3)	44	0	0	-22	7	3

План	Базис	В	x1	x2	x3	x4	x5
4	x3	0.0303	1.76	0	1	0.0606	-0.0909
x2	1.67	2.67	1	0	0.3333	0
Индексная строка	F(X4)	44.67	38.67	0	0	8.33	1

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

x3 = 0.0303

x2 = 1.67

F(X) = 27*1.67 + -11*0.03 = 44.67

Завдання 3

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

1	4	1	5	6	300
1	3	1	1	2	250
4	1	2	2	3	200
100	120	90	70	80

Розв’язок

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

. Оскільки

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

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

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

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

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

В1	В2	В3	В4	В5	В6	Запаси
А1	1	4	1	5	6	0	300
А2	1	3	1	1	2	0	250
А3	4	1	2	2	3	0	200
Потреби	100	120	90	70	80	290

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

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

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

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

minZ = 1x11 + 4x12 + 1x13 + 5x14 +6x15 + 0x16 +1x21 + 3x22 + 1x23 + 1x24 +2x25+0x26+4x31 + 1x32 + 2x33 + 2x34 +3x35 + 0x36.

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

minZ = 1x11 + 4x12 + 1x13 + 5x14 +6x15 + 0x16 +1x21 + 3x22 + 1x23 + 1x24 +2x25 +0x26+4x31 + 1x32 + 2x33 + 2x34 +3x35 + 0x36.

за умов:

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

Ai	Bj						ui
Ai	b1 = 100	b2 = 120	b3 = 90	b4=70	b5=80	B6=290	ui
а1 = 300	1100	4[-]120	1[+]80	5	6	0	u1 = 0
а2 = 250	1	3	1[-]10	170	280	0[+]90	u2 = 0
а3 = 200	4	1[+]	2	2	3	0[-]200	u3 = 0
vj	v1 =1	v2 =4	v3 =1	v4 =1	v5=2	V6 =0

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

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

Перевіримо оптимальність опорного плану, складемо систему рівнянь (для заповнених клітин таблиці) для визначення потенціалів першого опорного плану:

Записана система рівнянь є невизначеною, і один з її розв’язків дістанемо, узявши, наприклад, u1 = 0. Тоді всі інші потенціали однозначно визначаються з цієї системи рівнянь: u1 =0, u2 = 0, u3 = 0, v1 =1, v2 =4, v3 =1 v4=1, v5=2, v6=0. Ці значення потенціалів першого опорного плану записуємо у транспортну таблицю.

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

А1B4 : u1 + v4 = 0 + 1 = 1<5;

А1B5 : u1 + v5 = 0 + 2 = 2<6;

А1B6 : u1 + v6 = 0 + 0 = 0=0;

А2B1 : u2 + v1 = 0 + 1 = 1= 1;

А2B2 : u2 + v2 = 0 + 4 = 4>3;

А3B1 : u3 + v1 = 0 + 1 = 1< 4;

А3B2 : u3 + v2 = 0 + 4 = 4> 1;

А3B3 : u3 + v3 = 0 + 1 = 1<2;

А3B4 : u4 + v1 = 0 + 1 = 1<2;

А3B5 : u4 + v2 = 0 + 2 = 2<3;

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

А2B2 : u2 + v2 = 0 + 4 = 4>3;

А3B2 : u3 + v2 = 0 + 4 = 4> 1;

Тому від нього необхідно перейти до другого плану, змінивши співвідношення заповнених і порожніх клітинок таблиці. Вибираємо максимальну оцінку вільної клітини (А3B2): 1

Ставимо в ній знак «+». Для визначення клітинки, що звільняється, будуємо цикл, починаючи з клітинки А3B2, та позначаємо вершини циклу почергово знаками «–» і «+». Тепер необхідно перемістити продукцію в межах побудованого циклу. Для цього у порожню клітинку А1B4 переносимо менше з чисел хij, які розміщені в клітинках зі знаком «–». Одночасно це саме число хij додаємо до відповідних чисел, що розміщені в клітинках зі знаком «+», та віднімаємо від чисел, що розміщені в клітинках, позначених знаком «–».

З вантажів хij що стоять в мінусових клітинах, вибираємо найменше,

, тобто

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

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

Ai	Bj						ui
Ai	b1 = 100	b2 = 120	b3 = 90	b4=70	b5=80	B6=290	ui
а1 = 300	1100	4[-] 110	190	5	6	0[+]	u1 = 0
а2 = 250	1	3	1	170	280	0100	u2 = -3
а3 = 200	4	1[+] 10	2	2	3	0[-] 190	u3 = -3
vj	v1 =1	v2 =4	v3 =1	v4 =4	v5=5	V6 =3

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

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

(А1B6): 0 + 3 = 3 >0;

Вибираємо максимальну оцінку вільної клітини (А1B6): 0

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

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

Ai	Bj						ui
Ai	b1 = 100	b2 = 120	b3 = 90	b4=70	b5=80	B6=290	ui
а1 = 300	1100	4	190	5	6	0110	u1 = 0
а2 = 250	1	3	1	170	280	0100	u2 = 0
а3 = 200	4	1120	2	2	3	080	u3 = 0
vj	v1 =1	v2 =1	v3 =1	v4 =1	v5=2	V6 =0

Перевіримо оптимальність опорного плану, тобто повторюємо описані раніше дії.