Зміст

Вступ 2

1 Транспортна задача 3

2 Методи рішення транспортиних задач 6

2.1Метод північно-західного кута 6

2.2 Метод мінімального елемента (мінімальної вартості) 6

2.3Метод потенціалів розв’язання транспортної задачі 7

3 ЦІЛОЧИСЛОВІ ТА ДИСКРЕТНІ ЗАДАЧІ ЛІНІЙНОГО ПРОГРАМУВАННЯ 13

3.1 Задача про призначення 13

3.2 Задача про комівояжера 14

3.3Задача про рюкзак 14

3.4Задача про вибір транспортних засобів 15

3.5Транспортна задача з фіксованими доплатами 16

16

3.6 Методи відтинання. 17

3.7Метод гілок і меж 20

Висновки 24

ПЕРЕЛІК ВИКОРИСТАНИХ ДЖЕРЕЛ 25

Вступ

Методи лінійного програмування застосовуються для вирішення багатьох екстремальних задач, з якими досить часто доводиться мати справу. Вирішення таких задач зводиться до знаходження крайніх значень (максимуму і мінімуму) деяких функцій змінних величин.

Під назвою «транспортна задача» об'єднується широкий круг задач з єдиною математичною моделлю. Дані задачі відносяться до задач лінійного програмування і можуть бути вирішені симплексним методом. Проте матриця системи обмежень транспортної задачі настільки своєрідна, що для її вирішення розроблені спеціальні методи, які ми розглядатимемо далі. Ці методи, як і симплексний метод, дозволяють знайти початкове опорне рішення, а потім, покращуючи його, отримати оптимальне рішення.

Основною метою задачі є мінімізувати витрати на транспортування продукції споживачам.

1 Транспортна задача

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

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

Математична модель задачі складається з цільової функції

множини допустимих значень, заданої нерівностями

і прямих обмежень

Якщо попит і пропозицію збалансовано, тобто виконується умова

маємо так звану закриту ТЗ. Якщо умова (1.5) не виконується, то задача називається відкритою.

Будь-яку відкриту ТЗ можна звести до закритої введенням фіктивного виробника , коли попит перевищує пропозицію, чи фіктивного споживача, коли пропозиція перевищує попит. При цьому обсяг продукції фіктивних учасників перевезень становить

чи

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

Закрита ТЗ має такі властивості:

1) вона завжди допустима та має розв’язок;

2) серед рівнянь-обмежень (1.2) та (1.3) лише лінійно незалежні;

3) якщо в умовах задачі всі числа , , та ,, цілі, то оптимальний розв’язок задачі також цілочисловий.

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

Базисні розв’язки ТЗ як різновиду ЗЛП лежать у вершинах допустимої області. Це означає, що будь-який базисний розв’язок складається з додатних і нульових координат, причому додатних координат у не виродженому розв’язку рівно стільки, скільки лінійно незалежних обмежень у задачі. Якщо розв’язок вироджений, то додатних координат менше, ніж таких обмежень. Отже, із загальних властивостей ЗЛП та другої властивості ТЗ можна дійти висновку, що не вироджений базисний розв’язок ТЗ містить рівно ненульових перевезень. У виродженому розв’язку ненульових перевезень менше.

Обчислення, пов’язані з розв’язанням ТЗ, виконують у транспортних таблицях. Вони відрізняються від звичайних симплекс-таблиць тим, що в них заповнюють лише ті клітини , у яких перевезення ненульові:. Такі клітини називають зайнятими (заповненими), а інші вільними. Зрозуміло, що не виродженому розв’язку відповідає рівнозайнятих клітин.

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

Побудувати початковий базисний розв’язок ТЗ значно простіше, ніж для звичайної ЗЛП. Опишемо два найпоширеніші та найчастіше застосовувані методи визначення початкового базисного розв’язку ТЗ.