Тема 7. Розв’язання транспортної задачі

 

Відомо обсяги поставок і потреба споживачів (таб. 7.1). Задано тарифи на перевезення 1т. Вантажу від кожного постачальника кожному споживачу (таб. 7.2).

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

Вхідні данні

Таб. 7.1. Постачальники Вантаж Таб. 7.2. Споживачі вантаж

Тарифи на перевезення, грн./т

Постачальники	Споживачі

 

Розташувати ці данні як показано на рис 7.1

 

рис 7.1. розташування вхідних даних для розв’язання задачі

 

Для розв’язання цієї задачі необхідно:

- побудувати такі таблиці, як вказано на рис 2.49;

- у чарунку В25 ввести формулу В17* В35 (вартість перевезення вантажу від першого постачальника до першого споживача) і продублювати цю формулу, як вказано на рис. 7.2;

- загальні витрати, тобто вартість перевезення всього вантажу, розрахувати у чарунці Н29 як загальну суму витрат усіх постачальників (цільова чарунка повинна мати мінімальне значення);

- вибрати команду Сервис – Поиск решения....;

 

 

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

- натиснути кнопку Параметри та встановити їх значення, як показано на рис. 7.4, і натиснути кнопку ОК;

- у вікні Поиск решения натиснути кнопку Выполнить;

- якщо результати рішення (рис. 7.5) Вас задовольняють, у вікні Результаты поиска решения (рис. 7.6) вибрати перемикач Сохранитьнайденое решение і натиснути кнопку ОК.

 

 

ТЕСТИ

Тест 1 Яка необхідна умова розв’язання економічної задачі симплексним методом:

а). Вільні члени від’єднані;

б). Вільні члени додані;

в). В нерівностях повинен бути тільки знак ≤;

г). В нерівностях можуть бути різні знаки.

 

Тест 2. Як заповняється Z рядок, якщо задача на мах:

а). Коефіцієнти беремо з цільової функції;

б). Коефіцієнти беремо з цільової функції з оберненим знаком;

в). Коефіцієнти беремо з нерівностей.

г). Інші варіанти.

 

Тест 3. Як заповнюється Z рядок, якщо задача на min:

а). Коефіцієнти беремо з цільової функції з оберненим знаком;

б). Коефіцієнти беремо з цільової функції:

в). Коефіцієнти беремо з нерівностей;

г). Інші варіанти.

 

Тест 4. Як визначається вирішальний стовпчик, якщо задача на мах:

а). По Z рядку найбільше додатне число;

б). По Z рядку найбільше від’ємне число по модулю;

в). По більших членах найбільше додатне число;

г). По більших членах найбільше від’ємне число по модулю.

 

Тест 5. Як визначається вирішальний стовпчик, якщо задача на min:

а). По Z рядку найбільше від’ємне число по модулю;

б). По Z рядку найбільше додатне число;

в). По вільних членах найбільше від’ємне число по модулю;

г). По вільних членах найбільше додатне число.

 

Тест 6. Як визначається симплексне відношення:

а). Коефіцієнти цільової функції ділимо на елементи вирішального стовпчика;

б). Вільні члени ділимо на елементи вирішального стовпчика;

в). Інші варіанти.

 

Тест 7. Коли план буде оптимальним, якщо задача на мах:

а). в Z ряду всі елементи від’ємні;

б). В Z ряду всі елементи додатні;

в). В Z ряду всі елементи від’ємні або нульові;

г). В Z ряду всі елементи додатні або нульові.

 

Тест 8. Коли план буде оптимальним, якщо задача на min:

а). В Z ряду всі елементи від’ємні;

б). В Z ряду всі елементи додатні;

в). В Z ряду всі елементи додатні або нульові;

г). В Z ряду всі елементи від’ємні або нульові.

 

Тест 9. Яка умова розв’язання задачі М методом:

а). вільні члени від’ємні;

б). вільні члени додатні;

в). в нерівностях повинен бути тільки знак ≤;

г). В нерівностях можуть бути різні знаки.

 

Тест 10. Як заповнюється Z рядок, якщо задача на min:

а). Коефіцієнти беремо з цільової функції;

б). Коефіцієнти беремо з цільової функції з оберненим знаком;

в). Коефіцієнти беремо з нерівностей;

г). Інші варіанти.

 

Тест 11. Як визначається вирішальний стовпчик, якщо задача на мах:

а). По Z рядку найбільше додатне число;

б). По Z рядку найбільше від’ємне число по модулю;

в). По L рядку найбільше додатне число;

г). По L рядку найбільше від’ємне число по модулю.

 

Тест 12. Як визначається вирішальний стовпчик, якщо задача на min:

а). По Z рядку найбільше від’ємне число по модулю;

б). По Z рядку найбільше додатне числи;

в). По L рядку найбільше додатне число;

г). По L рядку найбільше від’ємне число по модулю.

 

Тест 13. Коли план буде оптимальним, якщо задача на min:

а). По Z рядку всі елементи нульові або від’ємні;

б). По Z рядку всі елементи додатні або нульові;

в). По L рядку всі елементи від’ємні;

г). По L рядку всі елементи додатні.

 

Тест 14. Коли план буде оптимальним, якщо задача на max:

а). По Z рядку всі елементи додатні або нульові;

б). По Z рядку всі елементи від’ємні або нульові;

в). По L рядку всі елементи від’ємні;

г). По L рядку всі елементи додатні.

 

Тест 15. Якщо одна з пари двоїстих задач сформульована на мах цільової функції, то друга:

а). На min;

б). На max;

в). Інші варіанти.

 

Тест 16. Коефіцієнти цільової функції однієї із задач є:

а). Вільними членами системи обмежень другої задачі;

б). Коефіцієнтами системи обмежень;

в). Обмеженими коефіцієнтами системи обмежень

 

Тест 17. Що таке М у задачах лінійного програмування.

а) дуже маленьке число;

б) помилка при обчисленнях;

в) дуже велике число;

г) грошова оцінка.

 

Тест 18. Що таке коефіцієнти структурних зрушень?

а) Коефіцієнти в стовпцях змінних першої симплексної таблиці

б) Коефіцієнти Z-рядка першої симплексної таблиці;

в) Коефіцієнти Z-рядка останньої симплексної таблиці

г) Коефіцієнти в стовпцях змінних останньої симплексної таблиці;

д) Коефіцієнти в рядках змінних останньої симплексної таблиці;

 

Тест 19. Змінювати оптимальний план можна в таких напрямках:

а) збільшити змінну, що ввійшла в базис;

б) вводити в базисне рішення штучну змінну

в) вводити в базисне рішення додаткову змінну;

г) вводити в базисне рішення додаткову змінну;

д) вводити в базисне рішення нову змінну.

 

Тест 20. Введення додаткових умов в оптимальний план можливе в таких випадках:

а) їх введення не повинно збільшувати значення цільової функції;

б) їх введення не повинно приводити до додатних значень базисних змінних;

в) їх введення не повинно приводити до від’ємних значень базисних змінних;

г) їх значення повинні попадати ву визначений інтервал.

 

Тест 21. Що таке альтернативні розв’язки?

а) планово-економічна задача має безліч оптимальних варіантів розв’язків з рівнозначним функціоналом;

б) планово-економічна задача має безліч оптимальних варіантів розв’язків з різними функціоналами;

в) не існує оптимального плану;

г) область визначення початкової задачі не сумісна.

 

Тест 22. Матриці, складені з коефіцієнтів обмежень вихідної і двоїстої задач, є:

а) оберненими;

б) одиничними;

в) добутком одиничної матриці на обернену;

г) взаємно транспонованими.

 

Тест 23. Чим відрізняються симетричні і несиметричні спряжені задачі?

а) в симетричних задачах в обмеженням стоїть знак „=”;

б) в несиметричних задачах в обмеженням стоїть знак „=”;

в) в симетричних задачах в обмеженнях всі знаки „³”;

г) в несиметричних задачах в обмеженнях всі знаки „≤”;

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

 

Тест 24. Який запис має канонічна форма задачі лінійного програмування?

а) в обмеженням всі знаки мають однаковий напрямок;

б) відсутня умова невід’ємності основних змінних;

в) накладено умову невід’ємності на додаткові змінні;

г) в обмеженнях всі знаки „≥”;

д) в обмеженнях всі знаки „≤”;

е) в обмеженнях всі знаки „=”.

Тест 25. Критерій оптимальності опорного плану?

а) в задачах на максимум в Z-рядку відсутні додатні елементи;

б) в задачах на максимум в Z-рядку відсутні від’ємні елементи;

в) в задачах на мінімум в Z-рядку відсутні додатні елементи;

г) в задачах на мінімум в Z-рядку відсутні від’ємні елементи;

д) в задачах на максимум в Z-рядку відсутні нульові оцінки;

е) в задачах на мінімум в Z-рядку відсутні нульові оцінки.

 

Питання для підсумкового контролю

1. Що розуміють під математичною моделлю задачі?

2. Дайте змістовну постановку задачі лінійного програмування.

3. Дайте змістовну постановку задачі про дієту.

4. Дайте змістовну постановку задачі виробничого планування.

5. Складіть математичні моделі задач, перерахованих в пункті 2, 3, 4

6. Сформулюйте основну задачу лінійного програмування (ЛП).

7. Запишіть модель задачі ЛП. у стандартній і канонічній формах. Матрична форма моделей.

8. Як зводиться задача мінімізації цільової функції до задачі максимізації?

9. Яка геометрична інтерпретація рішення лінійних нерівностей з однією, двома, трьома змінними?

10. Що називається допустимим рішенням і областю допустимих рішень (ОДР) задачі математичного програмування.

11. Яка геометрична інтерпретація рішення системи лінійних нерівностей з двома змінними?

12. Побудуйте лінію рівня цільової функції Z = 3x1 - 2x2, відповідну значенню Z = 0.

13. Чим визначається напрям швидкого зростання цільової функції? Побудуйте вектор-нормаль (grad) Z для функції Z = 4x1 - x2.

14. Що називається оптимальним рішенням задачі ЛП?

15. Які випадки можливі при рішенні задачі ЛП?

16. Як виражається оптимальне рішення за наявності альтернативного оптимуму?

17. У чому полягає ідея симплекс-методу?

18. У якому вигляді повинна бути записана модель задачі ЛП для вирішення її симплекс методом?

19. Як побудувати перше базисне рішення? У якому випадку воно буде опорним рішенням задачі ЛП?

20. З яких етапів складається перехід від одного опорного рішення до іншого?

21. Як визначити який з небазисних стовпців розширеної матриці А* увійде до базису?

22. Яким чином зберігається позитивність змінних нового базисного рішення?

23. Що є критерієм оптимальності рішення задачі ЛП в симплекс-методі?

24. Як визначається поточне значення цільової функції з таблиці?

25. У якому випадку для вирішення задачі ЛП використовується метод штучного базису?

26. Як будується М-задача?

27. Що таке М?

28. Як розв'язується М-задача?

29. Як за рішенням М-задачі визначається рішення початкової задачі? Назвіть можливі випадки.

30. Запишіть математичні моделі пари подвійних задач.

31. Дайте економічну інтерпретацію пари подвійних задач.

32. Сформулюйте правила побудови подвійної задачі до початкової.

33. Сформулюйте першу теорему подвійності і дайте економічну інтерпретацію.

34. Сформулюйте і дайте економічну інтерпретацію другої теореми подвійності.

35. Перерахуйте властивості подвійних оцінок. У чому полягає їх економічне значення?

 

ВИКОРИСТАНА ЛІТЕРАТУРА

1. Акулия И.Л. Математическое программирование в примерах и задачах. - М.: Высшая школа, 1996.

2. Балашевич В.А. Основы математического программирования.

3. Вентцель Е.С. Исследование операций: задачи, принципы, методология. - М.: Наука, 1988.

4. Деордица Ю.С., Нефедов Ю.М. Исследование операций в планировании и управлении. - К.: Высшая школа, 1991.

5. Зайченко Ю.П. Исследование операций. - К.: Высшая школа, 1988.

6. Калихман И.Л. Сборник задач по математическому программированию. - М.: Высшая школа, 1975.

7. Карманов В.Г. Математическое программирование. - М.: Наука, 1986.

8. Кузнецов А.В., Сакович В.А., Холод Н.М. Высшая математика. Математическое программирование. - Минск, Высшая школа, 1994.

9. Кузнецов Ю.Н., Кузубов В.И., Волощенко А.Б. Математическое программирование. - М.: Высшая школа, 1980.

10. Сакович В.А. Исследование операций. - Минск, Высшая школа, 1985.

11. Таха Х. Введение в исследование операций: в 2 книгах. - М.: Мир, 1985.

 

Мета і програма викладання дисципліни. 3

Форма і критерії оцінки. 5

Тема 1. Графічний метод розв'язання задач лінійного програмування. 7

Тема 2. Симплексний метод розв'язку задачі лінійного програмування. 10

Тема 3. М-метод (метод великих штрафів) 10

Тема 4. Двоїста задача лінійного програмування. 17

Тема 5. Транспортна задача лінійного програмування, її структура та методи розв'язку 21

Тема 6. Пошук рішення. 34

ТЕСТИ.. 40

Питання для підсумкового контролю.. 45

ВИКОРИСТАНА ЛІТЕРАТУРА.. 46

 

Математичне програмування

Робочий зошит. Модуль 1.

 

 

Склали: О.С. Бондар – к.е.н.

М.І. Трофимчук – к.е.н.

А.Ф Неборака - - асистент

О.Ю Углова - - асистент

С.І. Романенко - - асистент

О.В. Савчук - - асистент

О.В. Лісовий - - асистент

О.Б. Яломистий - - асистент

В.І. Кармазін - асистент

 

Редактор

Комп’ютерна верстка

 

 

Здано до склад. Підп. До друку Формат Ум. друк. арк. Тираж Зам. ціна 09117 Біла Церква, Соборна пл.,8; тел. 3-11-01