МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ "ЛЬВІВСЬКА ПОЛІТЕХНІКА" Інститут КНІТ Кафедра ПЗ ЗВІТ До лабораторної роботи № 3 На тему: “ Транспортна задача лінійного програмування” З дисципліни: “Дослідження операцій” Лектор: доц. каф. ПЗ Журавчак Л.М. Львів – 2010 Тема роботи: Транспортна задача лінійного програмування. Мета роботи: Ознайомитись із поняттям транспортної задачі лінійного програмування. Навчитись розв’язувати транспортну задачу задачу лінійного програмування. Теоретичні відомості Транспортна задача - класична задача лінійного програмування. До неї зводяться багато оптимізаційних задач. Формулюється вона так: На m складах знаходиться вантаж, який потрібно розвезти n споживачам. Хай ai (i = 1 ..., n) - кількість вантажу на i-тому складі, а bj (j = 1 ..., m) - потреба у вантажі j-го споживача, cij - вартість перевезення одиниці вантажу з i-го складу j-му споживачу. Вимагається мінімізувати вартість перевезень. Якщо позначити через xij об'єм перевезень з i-го складу j-му споживачу, то транспортна задача формалізується так:
(всі споживачі повинні бути задоволені)
(весь вантаж повинен бути доставлений споживачу)
(не можна перевозити вантаж від споживача на склад). Необхідна і достатня умови для вирішення транспортної задачі. Теорема. Для того, щоб транспортна задача лінійного програмування мала рішення, необхідно і достатньо, щоб сумарні запаси постачальників дорівнювали сумарним запитам споживачів, тобто задача повинна бути з правильним балансом. Класичну транспортну задачу можна представити у вигляді так званої транспортної таблиці (табл. 1).
Табл.1 Транспортна таблица Ця таблиця відповідає матриці змінних моделі X, в яку доданий один стовпець (поставки) і один рядок (попит), а в правій половині клітинки, відповідні кожній змінній xij, вписано відповідне значення сij. Помітимо також, що при вирішенні транспортних задач транспортні таблиці грають ту ж роль, що і симплекс-таблиці при рішенні задач лінійного програмування. Завдання Розв’язати транспортну задачу лінійного програмування.
Код та результати роботи
Висновок На цій лабораторній роботі я ознайомився із поняттям транспортної задачі лінійного програмування та навчився її розв’язувати. Для знаходження розв’язку транспортної задачі було використано програмний засіб MathCad.