Міністерство освіти і науки україни
Національний університет “Львівська політехніка”
Кафедра САПР
Розв’язання транспортних задач лінійного програмування. Методичні вказівки
до лабораторної роботи № 7
з курсу “Математичні методи дослідження операцій” для студентів базових напрямків
6.050101 “Комп’ютерні науки”
ЗАТВЕРДЖЕНО
на засіданні кафедри
“Системи автоматизованого проектування”
Протокол № 1
від “ 22 ” серпня 2011 р.
Львів 2011
РОЗВ’ЯЗАННЯ ТРАНСПОРТНИХ ЗАДАЧ ЛІНІЙНОГО ПРОГРАМУВАННЯ. Методичні вказівки до лабораторної роботи № 7 з курсу “Математичні методи дослідження операцій” для студентів базових напрямків 6.050101 “Комп’ютерні науки” // Укл. Марікуца У.Б.
Укладачі:
Марікуца У.Б., доцент
Рецензенти:
Каркульовський В.І., к.т.н., доцент
Відповідальний за випуск:
Ткаченко С.П., к.т.н., доцент
Мета роботи: Вивчити особливості розв’язування транспортних задач за допомогою Solver.
1.1 Теоретичні відомості.
При розв’язуванні транспортної задачі вирішується задача оптимізації з лінійною цільовою функцією й обмеженнями у виді рівностей і нерівностей.
Транспортна задача
У цьому прикладі вами має бути визначити оптимальний план перевезень продукції зі складів у пункти реалізації.
Припустимо, що вам потрібно перевести весь вантаж із трьох складів у два пункти, причому весь вантаж повинний бути перевезений в усі пункти. У 1 пункт повинне бути перевезено 45 одиниць вантажу, у 2 - 79. На складах вантаж розподілений у такий спосіб: на 1 - 18, 2- 75, 3- 31 умовних одиниць.
Вартість перевезення одиниці вантажу зі складу в пункт визначається табл. 1.
Табл. 1. Вартість перевезення одиниці вантажу
Пункти Склади
п.1 п.2 номер у вантажу
17 6 с.1 18
12 13 с.2 75
9 8 с.3 31
45 79
У табл. 2 приведені змінні, котрі позначають обсяги перевезень зі складу в пункти призначення. Наприклад, змінна c4 позначає величину вантажу, що перевезений зі складу 1 у пункт 2.
Табл. 2. Позначення для об'ємів перевезень
Пункти Склади
1 2 номер
c1 c4 1
c2 c5 2
c3 c6 3
У даному прикладі цільова функція, визначена як сума витрат на перевезення, має такий вигляд:
Q(c1,c2,c3,c4,c5,c6) = 17*c1 + 12*c2 + 9*c3 + 6*c4 + 13*c5 + 8*c6
Запишемо рівняння для обмежень. Той факт, що усі вантажі перевезені записується у виді трьох рівнянь:
c1 + c4 = 18
c2 + c5 = 75
c3 + c6 = 31
Сума вантажів у кожному пункті дає ще два рівняння:
c1 + c2 + c3 = 45
c4 + c5 + c6 = 79
Ще два обмеження представляються цілком природними. Усі значення змінних повинні бути цілими і ненегативними.
Задача поставлена і приступаємо до її рішення. Виконайте наступні дії:
Введіть в комірку A1 формулу для цільової функції: =17*c1+12*c2+9*c3+6*c4+13*c5+8*c6.
Введіть в комірку A3 формулу для обмеження: =c1+c4.
Введіть в комірку A4 формулу для обмеження =c2+c5.
Введіть в комірку A5 формулу для обмеження =c3+c6.
Введіть в комірку A6 формулу для обмеження =c1+c2+c3.
Введіть в комірку A7 формулу для обмеження =c4+c5+c6.
Введіть в комірки C1:C6 початкові значення змінних. У даному випадку покладемо ці значення нульовими.
Виконайте команду Сервіс | Пошук рішення. З'явиться вікно діалогу “Пошук рішення”.
У поле введення Установити цільов комірку уведіть посилання на комірку A1.
Установіть перемикач Мінімальне значення.
У поле введення Змінюючи комірки вкажіть посилання на комірки C1:C6.
Починаємо вводити інформацію в поле введення Обмеження. Натисніть кнопку Додати. З'явиться вікно діалогу “Додати обмеження”. У поле введення Посилання на комірку уведіть посилання на комірку A3. У поле введення Обмеження введіть = і число 18. Аналогічну операцію проробіть з комірками A4:A7.
Для введення обмеження на невід’ємність змінних у вікні діалогу “Додати обмеження” у поле введення Посилання на комірку уведіть посилання на комірки C1:C6. У поле введення Обмеження введіть >= і число 0 (рис.1). Аналогічну операцію проробіть для введення обмеження на цілочисельність змінних.. У поле введення Обмеження введіть: цілий (рис.2). На рис. 3 представлене заповнене вікно діалогу “Пошук рішення”.
Рис. 1. Обмеження на невід’ємність
Рис.2. Обмеження на цілочисельність ь
Рис. 3. Заповнене вікно діалогу “Пошук рішення”
Натисніть кнопку Виконати. Виведіть результати розрахунків на окремий лист.
Транспортна задача вирішена і її результат представлений на рис. 4.
Рис. 4. Результат вирішення транспортної задачі
Рішення в цілих числах не завжди може бути отримане. У таких випадках у вікні діалогу “Результати пошуку рішення” виводиться відповідне повідомлення. Однією з можливих причин може бути помилка в записі обмежень.