This page has been robot translated, sorry for typos if any. Original content here.

Математичне програмування - Наконечний С.І.

Заключні зауваження

Практичне застосування класичної економіко-математичної моделі транспортної задачі наштовхується на певні труднощі. Насамперед, як правило, необхідно перевозити неоднорідні продукти. Тоді транспортна задача ускладнюється. Економіко-математичну модель для багатопродуктової транспортної задачі запишемо так:

за умов: ,

;

,

;

,

де k — вид продукції, яку треба перевезти.

Часто господарські зв’язки між постачальниками і споживачами вимагають відповідних обмежень:

;

,

де М1, М2 — відповідні множини індексів i, j, за якими вводяться обмеження на обсяги перевезень і-ї продукції до j-го споживача. Обмеженнями гарантується, що відповідний j-й споживач отримає і-ї продукції не менше від заданого обсягу. Обмеженнями виду описують транспортні можливості.

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

У класичній транспортній задачі допускається, що витрати на транспортування лінійно залежать від обсягів перевезень. Але на практиці ця умова порушується, тобто такі зв’язки, як правило, є нелінійними, стохастичними тощо. Особливої уваги заслуговує така постановка транспортної задачі, в якій необхідно мінімізувати тривалість виконання заданих обсягів робіт, наприклад, перевезення сировини та продукції, яка швидко псується. Цей критерій часто використовується для оптимізації військових операцій, виконання сільськогосподарських робіт (наприклад, збору урожаю) тощо.

Транспортна задача значно ускладнюється за моделювання виробничо-транспортних економічних систем, які виробляють продукцію в широкому асортименті, а для перевезення її застосовують різні види транспорту.

Контрольні запитання

  1. Опишіть економічну і математичну постановку класичної транспортної задачі.
  2. Чим відрізняється транспортна задача від загальної задачі лінійного програмування?
  3. Сформулюйте необхідну і достатню умови існування розв’язку транспортної задачі.
  4. Які ви знаєте властивості опорних планів транспортної задачі?
  5. Чим відрізняється відкрита транспортна задача від закритої?
  6. Як перетворити відкриту транспортну задачу на закриту?
  7. Які ви знаєте методи побудови опорного плану?
  8. Побудуйте невироджений опорний план методом північно-західного кута: для задачі:

ai = 50, 70, 90; bj = 70, 65, 70, 75.

  1. Що означає «виродження» опорного плану? Як його позбутися?
  2. Назвіть етапи алгоритму методу потенціалів.
  3. Як обчислюють потенціали?
  4. Назвіть умови оптимальності транспортної задачі.
  5. Опишіть економічну і математичну постановку двохетапної транспортної задачі.
  6. Назвіть особливості розв’язування транспортних задач з обмеженнями виду .

Приклади та завдання для самостійної роботи

Розв’язати наведені нижче транспортні задачі:

Задача 5.1.

ai = (8; 10; 5);

bj = (5; 5; 10);

.

Задача 5.2.

ai = (8; 7; 6);

bj = (7; 10; 6);

.

Задача 5.3.

ai = (15; 10; 5; 20);

bj = (10; 20; 15);

.

Задача 5.4.

ai = (10; 20; 40);

bj = (30; 10; 60).

.



 

Created/Updated: 25.05.2018

stop war in Ukraine

ukrTrident

stand with Ukraine