Контрольная работа: Оптимізація економічних показників

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

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
	b1 = 120	b2 = 130	b3 = 200	b4=180	b5=110
а1 = 200	1 120	« 1 2 3 4 5 6 7 8 9 10 » К-во Просмотров: 413 Бесплатно скачать Контрольная работа: Оптимізація економічних показників >>> Скачать <<< Меню Поиск