ТЗ за критерієм часу. Двостапна ТЗ. Розв’язання по сітці.
Компанія контролює три фабрики 
здатні виготовляти 150, 60 та 80 тис. од. продукції щотижня. Компанія уклала договір із чотирма замовниками 
яким потрібно щотижня відповідно 110, 40, 60 та 80 тис. од. продукції. Вартість виробництва та транспортування 1000 од. продукції замовникам з кожної фабрики наведено в таблиці.
| Фабрика | Вартість виробництва і транспортування 1000 од. продукції за замовниками | |||
| 
| 
| 
| |
| 4 | 4 | 2 | 5 |
| 5 | 3 | 1 | 2 |
| 2 | 1 | 4 | 2 |
Визначити для кожної фабрики оптимальний план перевезення продукції до замовників, що мінімізує загальну вартість виробництва і транспортних послуг.
Побудова математичної моделі. Нехай 
— кількість продукції, що перевозиться з і -ї фабрики до j-го замовника 
. Оскільки транспортна задача за умовою є збалансованою, закритою 
, то математична модель задачі матиме вигляд
Економічний зміст записаних обмежень полягає ось у чому: уся вироблена на фабриках продукція має вивозитися до замовників повністю.
Аналогічні обмеження можна записати відносно замовників: продукція, що надходить до споживача, має повністю задовольняти його попит. Математично це записується так:
Загальні витрати, пов'язані з виробництвом і транспортуванням продукції, складаються як добуток обсягу перевезеної продукції та питомої вартості перевезень за відповідним маршрутом і за умовою задачі мають бути мінімальними. Тому
|
|
|
У цілому математичну модель поставленої задачі можна записати так:
Розв'язування. Розв'язування задачі подамо в таблицях, які назвемо транспортними. Перший опорний план задачі побудуємо методом мінімальної вартості.
|
|
|
| |||
| 
| 
| 
| ||
| 4 110 | 4 | 2 2 + | 5 40- | 
|
| 5 | 3 | 1 -60 | 2 0+ | 
|
| 2 | 1 40 | 4 | 2 40 | 
|
| 
| 
| 
| 
| |
Тому 
ум. од.
Перший опорний план транспортної задачі вироджений, оскільки кількість заповнених клітинок у таблиці дорівнює п'яти, а (m + n - 1) = 3 + 4 - 1= 6. Для подальшого розв'язування задачі необхідно в одну з порожніх клітинок записати «нульове перевезення» так, щоб не порушити опорності плану, тобто можна зайняти будь-яку вільну клітинку, яка не утворює замкненого циклу. Наприклад, заповнимо клітинку 
. Тепер перший план транспортної задачі є не виродженим, і його можна перевірити на оптимальність за допомогою методу потенціалів.
На основі першої умови оптимальності 
складемо систему рівнянь для визначення потенціалів плану:
Записана система рівнянь є невизначеною, і один з її розв'язків дістанемо, якщо, наприклад, . Тоді всі інші потенціали однозначно визначаються: 
.
Далі згідно з алгоритмом методу потенціалів перевіряємо виконання другої умови оптимальності 
(для порожніх клітинок таблиці):
|
|
|
Умова оптимальності не виконується для клітинки 
. Порушення 
записуємо в лівому нижньому кутку відповідної клітинки.
Перший опорний план транспортної задачі є неоптимальним. Тому від нього необхідно перейти до другого плану, змінивши співвідношення заповнених і порожніх клітинок таблиці.
Потрібно заповнити клітинку , в якій є єдине порушення умови оптимальності. Ставимо в ній знак «+». Для визначення клітинки, що звільняється, будуємо цикл, починаючи з клітинки , та позначаємо вершини циклу почергово знаками «-» і «+». Тепер необхідно перемістити продукцію в межах побудованого циклу. Для цього у вільну клітинку переносимо менше з чисел , які розміщуються в клітинках зі знаком «-». Одночасно це саме число додаємо до відповідних чисел, що розміщуються в клітинках зі знаком «+», та віднімаємо від чисел, що розміщуються в клітинках, позначених знаком «-».
У даному випадку 
, тобто 
. Виконавши перерозподіл продукції згідно із записаними правилами, дістанемо такі нові значення: клітинка — 40 од. продукції, 
од., 
од. Клітинка 
, звільняється і в новій таблиці буде порожньою. Усі інші заповнені клітинки першої таблиці, які не входили до циклу, переписують у другу таблицю без змін. Кількість заповнених клітинок у новій таблиці також має відповідати умові невиродженості, тобто дорівнювати (п + т - 1).
|
|
|
Отже, другий опорний план транспортної задачі матиме такий вигляд:
|
|
|
| |||
|
|
|
| ||
|
| 4 -110 | 4 | 2 40+ | 5 | 
|
|
| 5 | 3 | 1 -20 | 2 40+ | 
|
|
| 2 1 + | 1 40 | 4 | 2 40- | 
|
|
| 
| 
| 
| 
| |
Тому 
ум. од.
Новий план знову перевіряємо на оптимальність, тобто повторюємо описані раніше дії. Другий план транспортної задачі також неоптимальний (порушення для клітинки 
). За допомогою побудованого циклу виконаємо перехід до третього опорного плану транспортної задачі і дістанемо таку таблицю:
|
|
|
| |||
|
|
|
|
| ||
|
| 4 90 | 4 | 2 60 | 5 | 
|
|
| 5 | 3 | 1 | 2 60 | 
|
|
| 2 20 | 1 40 | 4 | 2 20 | 
|
|
| 
| 
| 
| 
| |
Тому 
ум. од.
Перевірка останнього плану на оптимальність за допомогою методу потенціалів показує, що він оптимальний. Тому
За оптимальним планом перевезень перший замовник отримує 90 тис. од. продукції з першої фабрики та 20 тис. од. — з третьої. Другий споживач задовольняє свій попит за рахунок виробництва та перевезення 40 тис. од. продукції з третьої фабрики і т. д. При цьому загальна вартість виробництва та перевезення всієї продукції є найменшою і становить 720 ум. од.
|
|
|
ТЕМА 6.
Дата добавления: 2022-01-22; просмотров: 29; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!