Введення
транспортний лінійний програмування
Транспортна задача - це задача про найбільш економічному плані перевезень вантажу. Транспортна задача є однією з найпоширеніших спеціальних завдань лінійного програмування. Приватні постановки завдання розглянуті поруч фахівців з транспорту, наприклад, О.М. Толстим. p align="justify"> Перша сувора постановка транспортної задачі належить Хічкоку, і тому в зарубіжній літературі іноді її називають проблемою Хічкока.
Перший точний метод вирішення транспортної задачі розроблено радянськими вченими Л.В. Канторовичем і М.К. Гавуріним. br/>
1.Аналітіческая частина
.1 Опис і постановка задачі
Нехай у пунктах А1, А2, ..., Аm виробляють деякий однорідний продукт, причому обсяг виробництва в пункті А i становить a i одиниць (i = 1, 2, ..., m). Припустимо, що даний продукт споживають у пунктах В 1 , ..., В n , а обсяг споживання в пункті В j становить b j одиниць (j = 1, 2, ..., n).
Припустимо, що з кожного пункту виробництва можливе транспортування продукту в будь-який пункт споживання. Транспортні витрати з перевезення з пункту А i в пункт В j одиниці продукції дорівнюють c ij (i = 1, 2, ..., m; j = 1, 2, ..., n).
Завдання полягає у визначенні такого плану перевезень, при якому запити всіх споживачів повністю задоволені, весь продукт з пунктів виробництва вивезений і сумарні транспортні витрати мінімальні.
Умови транспортної задачі зручно представити в наступному вигляді:
Нехай x ij - кількість продукту, перевезеного з пункту А i в пункт В j . Потрібно визначити безліч змінних x ij > 0 (i = 1, 2, ..., m; j = 1, 2, ..., n), що задовольняють умовам
(i = 1, 2, ..., m), (1.1)
(j = 1, 2, ..., n), (1.2)
і таких, що цільова функція досягає мінімуму.
(1.3)
Таблиця 1.1 - Таблична форма запису умов транспортної задачі
В
Умова (1...