Транспортная задача как частный случай общей распределительной задачи.

Содержание
Введение
Глава I: теоретическая часть
1) Постановка транспортной задачи
2) Математическая модель транспортной задачи
3) Необходимое и достаточное условия решения транспортной задачи.
4) Транспортная задача как частный случай общей распределительной задачи.
5) Первоначальное распределение поставок
• Метод северо-западного угла
•Метод минимальных затрат
• Метод Фогеля
6) Нахождения оптимального решения
• Метод потенциалов
• Венгерский метод
• Распределительный метод
7) Транспортная задача с неправильным балансом
8) Открытая модель транспортной задачи
9) Закрытая модель транспортной задачи
Глава II: практическая часть
Список используемой литературыПриложение

Транспортная задача как частный случай общей распределительной задачи.

1. Постановка транспортной задачи.

Однородный груз сосредоточен у m поставщиков в объемах [pic]. Данный груз необходимо доставить n потребителям в объемах [pic]. Известны [pic], i=1,2,,…,m, j=1,2,…,n- стоимости перевозки единицы груза от каждого I-го поставщика каждому j-му потребителю.Требуется составить такой план перевозок, при котором запасы всех потребителей полностью удовлетворены и суммарные затраты на перевозку всех грузов минимальны.
Исходные данные транспортной задачи обычно записываются в таблице (таб1.1).

|[pic] |[pic] |[pic] |… |[pic] |
|[pic] | | || |
|[pic] |[pic] |[pic] |… |[pic] |
|[pic] |[pic] |[pic] |… |[pic] |
|… |… |… |…. |…. |
|[pic] |[pic] |[pic] |… |[pic] |Таблица1.1.

Исходные данные задачи могут быть представлены также в виде вектора запасов поставщиков А=([pic]), вектора запросов потребителей
В=([pic]) и матрицы стоимостей [pic] .

В транспортных задачах под поставщиками и потребителями понимаются различные промышленные и сельскохозяйственные предприятия, заводы, фабрики, слады, магазины и т.д. Однородными считаются грузы,которые могут быть перевезены одним видом транспорта. Под стоимостью перевозок понимаются тарифы, расстояния, время, расход топлива и т.п.

2. Математическая модель транспортной задачи

Переменными (неизвестными) транспортной задачи являются [pic] i=1,2,,…,m, j=1,2,…,n – объемы перевозок от каждого i-го поставщика каждому j-му потребителю. Эти переменные можно записать в видематрицы перевозок
[pic] .
Так как произведение [pic][pic] определяет затраты на перевозку груза от i-го поставщика j-му потребителю, то суммарные затраты на перевозку всех грузов равны [pic][pic]. По условию задачи требуется обеспечить минимум суммарных затрат. Следовательно, целевая функция имеет вид [pic][pic][pic].
Система ограничений задачи состоит из двух групп уравнений. Перваягруппа из m уравнений описывает тот факт, что запасы всех m поставщиков вывозятся полностью:
[pic], i=1,2,…,m.
Вторая группа из n уравнений выражает требование полностью удовлетворить запросы всех n потребителей:
[pic], j=1, 2, … , n.
Учитывая условие неотрицательности объемов перевозок, математическую модель задачи можно записать так:
[pic][pic][pic],(1)
[pic], i=1,2,…,m , (2)

[pic], j=1, 2, … , n, (3)

[pic], i=1,2,,…,m, j=1,2,…,n (4)
3. Необходимое и достаточное условия решения транспортной задачи

Для разрешимости транспортной задачи необходимо и достаточно, чтобы запасы груза в пунктах отправления были равны потребностям в грузе в пунктах...