![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Постановка задачі
Так звана транспортна задача (ТЗ) є частинним випадком загальної задачі лінійного програмування. Її прості в математичному аспекті умови дозволяють застосувати значно більш ефективні методи розв’язування, ніж для загальної задачі. Один із варіантів постановки ТЗ полягає у знаходженні оптимального плану перевезень деякого однорідного вантажу з Оптимізація плану перевезень полягає у мінімізації загальної вартості перевезень або мінімального часу їх доставки. Сформулюємо математичну постановку цього варіанту задачі (з мінімізацією загальної вартості). Задано: - обсяги виробництва (запаси), що дорівнюють - обсяги споживання (заявки), що дорівнюють - матриця Треба знайти множину
за умов:
(задоволення всіх заявок);
(реалізація всіх запасів)
(зворотні перевезення від У найпростішому варіанті повинна виконуватися ще умова рівності суми заявок і запасів:
Цю умову можна записати ще й так:
звідки видно, що одне з рівнянь систем (1.2) і (1.3) не є незалежним, оскільки є наслідком решти. У цьому варіанті задача називається закритою. Якщо умова (1.5) не виконується, задача називається відкритою. Вона легко зводиться до закритої. Означення. Множина Означення. Допустимий план, у якому не більше, як Означення. Базисний план, що мінімізує функцію (1.1), називається оптимальним. Твердження. На відміну від загальної задачі ЛП, ТЗ завжди має допустимий і оптимальний плани.
|