• Гідрологія і Гідрометрія
• Господарське право
• Економіка будівництва
• Економіка природокористування
• Економічна теорія
• Земельне право
• Історія України
• Кримінально виконавче право
• Медична радіологія
• Методи аналізу
• Міжнародне приватне право
• Міжнародний маркетинг
• Основи екології
• Предмет Політологія
• Соціальне страхування
• Технічні засоби організації дорожнього руху
• Товарознавство продовольчих товарів

Постановка задачі

Задача лінійного програмування транспортного типу

На попередніх лекціях ми розглянули загальні методи рішення задач лінійного програмування. Проте існують частинні типи задач лінійного програмування, які, в силу особливості своєї структури, допускають рішення більш простішими методами. Одним з таких типів задач лінійного програмування є задачі найбільш раціональної організації (тобто оптимальної) перевезення однорідного продукту з пунктів відправлення (ПВ) до пунктів призначення (ПП), які мають задані ресурси і потреби. Скорочено цей тип задач має назву – транспортна задача.

Критерієм якості плану перевезення може бути їх вартість, або термін (час). Відповідно вирішується транспортна задача за критерієм вартості, або критерієм часу.

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

Постановка задачі: нехай маємо m пунктів відправлення , у кожному з яких міститься певна кількість однорідного продукту одиниць відповідно. Є n пунктів призначення , куди потрібно доставити відповідно одиниць продукту. Передбачається, що сумарний ресурс (загальна кількість) продукту в ПВ дорівнює сумарній потребі усіх ПП , тобто

(1)

Крім того, відома вартість перевезення одиниці продукту від кожного ПВ до кожного ПП . Загальна вартість перевезення по будь-якому маршруту пропорційна кількості продукту, що перевозиться.

Необхідно скласти такий план перевезення (звідки, куди і скільки одиниць), щоб загальна вартість усіх перевезеньбіла мінімальна.

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

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

Перш ніж розглянути математичну модель задачі та її рішення зробимо кілька зауважень.

Транспортна задача може бути закритого чи відкритого типу. Умова (1) показує, що задача відноситься до закритого типу. Якщо умова (1) не виконується, тобто

або ,

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

Читайте також:

1. Алгоритм розв’язання задачі
2. Алгоритм розв’язання розподільної задачі
3. Алгоритм розв’язування задачі
4. Алгоритм розв’язування задачі
5. Алгоритм розв’язування задачі
6. Алгоритм розв’язування задачі
7. Алгоритм розв’язування задачі
8. Алгоритм розв’язування задачі
9. Алгоритм розв’язування задачі оптимізації в Excel
10. Аналіз інформації та постановка задачі дослідження
11. Визначення коефіцієнтів рівнянь лінійної регресії для багатофакторної задачі
12. Визначення множини допустимих планів задачі ЛП

Переглядів: 1189