- •Лабораторна робота №4 Тема: Транспортні моделі
- •Теоретичні відомості
- •1. Постановка задачі і її математична модель.
- •2. Розв’язання закритої транспортної задачі.
- •2.1 Визначення початкового опорного розв’язку.
- •Метод мінімального елемента
- •Метод подвійної переваги
- •Метод апроксимації Фогеля
- •2.2. Знаходження оптимального розв’язку транспортної задачі методом потенціалів.
- •Для цього використовуємо умова
- •Величина перерахунку
- •3. Відкрита транспортна модель
- •Теоретичні відомості
Лабораторна робота №4 Тема: Транспортні моделі
Мета роботи: Познайомитися зі спеціальним класом задач лінійного програмування транспортними задачами і зі способом їх розв'язання
Ключові слова: транспортна задача (ТЗ), поставщики, споживачі, перевезення, опорний план ТЗ, відкрита / закрита ТЗ, система потенціалів
Теоретичні відомості
Транспортними моделями (задачами) називаються задачі визначення оптимального плану перевезень вантажу з даних пунктів відправлення ( початковий пункт, наприклад місце виробництва, або склад) в задані пункти споживання (магазин, грузохранилище, знову ж склад).
1. Постановка задачі і її математична модель.
Найпростіше формулювання транспортної задачі, яке отримало назву задачі по критерію вартості, наступна:
деякий однорідний продукт, зосереджений у m постачальникiв Ai в кількостях ai (i=1, m) одиниць відповідно, необхідно доставити n споживачам Bj в кількостях bj (j= 1, n) одиниць. Відома вартість сij перевезення одиниці вантажу від i - го постачальника до j - го споживача.
Нехай xij - кількість одиниць вантажу, що перевозиться з початкового пункту i в пункт призначення j; тоді задача лінійного програмування транспортного типу в загальному вигляді формулюється таким чином:
мінімізувати z =
при обмеженнях
, i=1,…, m (сумарний об'єм перевезень з деякого початкового пункту не може перевищувати запаси, що є )
, j=1,…, n (сумарні перевезення продукції в деякий пункт споживання повністю задовольняє попит)
xij 0,
Якщо сумарні запаси рівні сумарному попиту = , то задача називається закритою (або збалансованою) транспортною задачею. У цьому випадку модель має вигляд:
min
= ai, i=
= bj, j=
xij 0,
Особливістю транспортної моделі є:
1. Коефіцієнти при невідомих у всіх умовах- обмеженнях рівні одиниці.
2. Кожна змінна зустрічається тільки в двох рівняннях- обмеженнях.
3. Система рівнянь симетрична відносно всіх змінних xik.
Основні властивості закритої транспортної задачі.
1. Закрита ТЗ в будь-якому випадку допустима і вирішувана.
2. Ранг матриці системи обмежень задачі рівний m+n-1. З цього слідує, що кожний опорний розв'язок буде мати r=m+n-1 базисних змінних і k=mn-(m+n-1)=(m-1)(n-1) вільних змінних.
3. Якщо в задачі все ai і всі bj - цілі числа, то хоч би один її оптимальний розв’язок також цілочисельний
.
2. Розв’язання закритої транспортної задачі.
Розв’язання ТЗ буде проводитися за допомогою загального прийому послідовного поліпшення розв'язків, який складається з наступних основних етапів:
визначення початкового опорного розв’язку;
оцінка цього розв’язку;
перехід до наступного розв’язку шляхом однократного заміщення однієї базисної змінної на вільну.
Спеціальний метод розв’язання транспортної задачі, заснований на симплекс- методі, передбачає використання транспортних таблиць (таблиця 1)
Таблиця 1
Постачальник |
Споживач |
Запас |
|||
|
В1 |
В2 |
… |
Вn |
|
А1 |
Х11 С11 |
Х12 С12 |
|
Х1n С1n |
а1 |
А2 |
Х21 С21 |
Х22 С22 |
|
Х2n С2n |
а2 |
… |
|
|
|
|
… |
Аm |
Хm1 Сm1 |
Хm2 Сm2 |
|
Хmn Сmn |
аm |
Потреба |
b1 |
b2 |
… |
bn |
bj = aj |
Змінні xij - називають перевезеннями.
Матриця ||xij|| називається планом перевезення.