Оптимізація економічних показників (стр. 2 из 3)

8x1-x2-4x3≥1

-6x1-2x2+x3≤2

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

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

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

Введемо штучні змінні х.

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

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

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

F(X) = -48x1-5x2+12x3 - Mx6 =>max

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

X1 = (0,0,0,0,2,1)

План	Базис	В	x1	x2	x3	x4	x5	x6
0	x6	1	8	-1	-4	-1	0	1
x5	2	-6	-2	1	0	1	0
Індекснийрядок	F(X0)	0	0	0	0	0	0	0

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

План	Базис	В	x1	x2	x3	x4	x5	x6	min
1	x6	1	8	-1	-4	-1	0	1	0.125
x5	2	-6	-2	1	0	1	0	0
Індекснийрядок	F(X1)	0	0	0	0	0	0	0	0

План	Базис	В	x1	x2	x3	x4	x5	x6
2	x1	0.125	1	-0.125	-0.5	-0.125	0	0.125
x5	2.75	0	-2.75	-2	-0.75	1	0.75
Індекснийрядок	F(X2)	0	0	0	0	0	0	0

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

x1 = 0.125

x5 = 2.75

F(X) = -48*0.13 = -6

Завдання 3

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

1	4	7	8	1	200
2	3	1	4	1	150
5	1	3	2	3	350
120	130	200	180	110

Розв’язок

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

. Оскільки

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

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

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

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

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

В1	В2	В3	В4	В5	Запаси
А1	1	4	7	8	1	200
А2	2	3	1	4	1	150
А3	5	1	3	2	3	350
А4	0	0	0	0	0	40
Потреби	120	130	200	180	110

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

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

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

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

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

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

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

за умов:

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

Ai	Bj					ui
Ai	b1 = 120	b2 = 130	b3 = 200	b4=180	b5=110	ui
а1 = 200	1120	480	7	8	1	u1 = 0
а2 = 150	2	350	1100	4	1	u2 = -1
а3 = 350	5	1	3100	2180	370	u3 = 1
а4 = 40	0	0	0	0	040	u4 = -2
vj	v1 =1	v2 =4	v3 =2	v4 =1	V5 =2

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

Z1 = 1 × 120 + 4 × 80 + 3 × 50 + 1× 100 + 3× 100+ 2 × 180 + 3 × 70 + 0 × 40 = 1560

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

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

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

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

А1B3 : u1 + v3 = 0 + 2 = 2 < 7;

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

А1B5 : u1 + v5 = 0 + 2 = 2 > 1;

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

А2B4 : u2 + v4 = -1 + 1 = 0 < 4;

А2B5 : u2 + v5 = -1 + 2 = 1 =1;

А3B1 : u3 + v1 = 1 + 1 = 2 < 5;

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

А4B1 : u4 + v1 = -2 + 1 = -1 < 0;

А4B2 : u4 + v2 = -2 + 4 = 2 > 0;

А4B3 : u4 + v3 = -2 + 2 = 0 = 0;

А4B4 : u4 + v4 = -2 + 1 = -1 < 0.

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

А1B5 : u1 + v5 = 0 + 2 = 2 > 1

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

А4B2 : u4 + v2 = -2 + 4 = 2 > 0.

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

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

У даному разі

, тобто

. Виконавши перерозподіл перевезень продукції згідно із записаними правилами, дістанемо такі нові значення: для клітинки А3B3 — 50 од. продукції, а для А2B2 – звільняється і в новій таблиці буде порожньою, а для А3B2 – (0 + 50) = 50 од. Клітинка А2B3 – 100 + 50 = 150. Усі інші заповнені клітинки першої таблиці, які не входили до циклу, переписуємо у другу таблицю без змін. Кількість заповнених клітинок у новій таблиці також має відповідати умові невиродженості плану, тобто дорівнювати (n + m – 1).

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

Ai	Bj					ui
Ai	b1 = 120	b2 = 130	b3 = 200	b4=180	b5=110	ui
а1 = 200	1120	480	7	8	1	u1 = 0
а2 = 150	2	3	1150	4	1	u2 = -5
а3 = 350	5	150	350	2180	370	u3 = -3
а4 = 40	0	0	0	0	040	u4 = -6
vj	v1 =1	v2 =4	v3 =6	v4 =5	V5 =6

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

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

А1B5 : u1 + v5 = 0 + 6 = 6 > 1

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

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

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

Ai	Bj					ui
Ai	b1 = 120	b2 = 130	b3 = 200	b4=180	b5=110	ui
а1 = 200	1120	4[-] 10	7	8	1[+] 70	u1 = 0
а2 = 150	2	3	1150	4	1	u2 = -5
а3 = 350	5	1[+] 120	3[-] 50	2180	3	u3 = -3
а4 = 40	0	0	0[+]	0	0[-] 40	u4 = -1
vj	v1 =1	v2 =4	v3 =6	v4 =5	V5 =1