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