Транспортная задача 5
Содержание
Введение2
1.Постановка задачи и ее математическая модель3
2.Модели транспортной задачи7
2.1.Закрытая модель транспортной задачи7
2.2. Открытая модель транспортной задачи8
3.Определение оптимального и опорного плана транспортной задачи10
4.Методы определения первоначального опорного плана12
4.1.Метод минимального элемента12
4.2.Метод аппроксимации Фогеля14
5.Методы определения оптимального плана16
5.1.Венгерский метод16
5.2.Метод потенциалов17
Список использованной литературы19
Введение
Транспортная задача линейного программирования получила в настоящее время широкое распространение в теоретических обработках и практическом применении на транспорте и в промышленности. Особенно важное значение она имеет в деле рационализации постановок важнейших видов промышленной и сельскохозяйственной продукции, а также оптимального планирования грузопотоков и работы различных видов транспорта.
Кроме того, к задачам транспортного типа сводятся многие другие задачи линейного программирования - задачи о назначениях, сетевые, календарного планирования.
Цель заданной работы - освоить математическую постановку транспортной задачи линейного программирования.
1. Постановка задачи и ее математическая модель
Транспортная задача является частным типом задачи линейного программирования и формулируется следующим образом. Имеется m пунктов отправления (или пунктов производства) Аi …, Аm , в которых сосредоточены запасы однородных продуктов в количестве a1 , ..., аm единиц. Имеется n пунктов назначения (или пунктов потребления) В1 , ..., Вm , потребность которых в указанных продуктах составляет b1 , ..., bn единиц. Известны также транспортные расходы Сij , связанные с перевозкой единицы продукта из пункта Ai в пункт Вj , i 1, …, m; j 1, ..., n. Предположим, что
т. е. общий объем производства равен общему объему потребления. Требуется составить такой план перевозок (откуда, куда и сколько единиц продукта везти), чтобы удовлетворить спрос всех пунктов потребления за счет реализации всего продукта, произведенного всеми пунктами производства, при минимальной общей стоимости всех перевозок. Приведенная формулировка транспортной задачи называется замкнутой транспортной моделью. Формализуем эту задачу.
Пусть хij - количество единиц продукта, поставляемого из пункта Аi в пункт Вj . Подлежащие минимизации суммарные затраты на перевозку продуктов из всех пунктов производства во все пункты потребления выражаются формулой:
(1)
Суммарное количество продукта, направляемого из каждого пункта отправления во все пункты назначения, должно быть равно запасу продукта в данном пункте. Формально это означает, что
, i 1, …, m (2)
Суммарное количество груза, доставляемого в каждый пункт назначения из всех пунктов отправления, должно быть равно потребности. Это условие полного удовлетворения спроса:
, j 1, …, n (3)
Объемы перевозок - неотрицательные числа, так как перевозки из пунктов потребления в пункты производства исключены:
xij 0, i 1, ..., m; j 1, ..., n (4)
Транспортная задача сводится, таким образом, к минимизации суммарных затрат при выполнении условий полного удовлетворения спроса и равенства вывозимого количества продукта запасам его в пунктах отправления.
Определение 1.
Всякое неотрицательное решение системы линейных уравнений
, j 1, …, n и , i 1, …, m,
определяемое матрицей X=(xij )(i 1, …, m; j 1, ..., n), называется планом транспортной задачи.
Определение 2.
План X*=(x*ij )(i1, …, m; j1, ..., n), при котором функция
принимает свое минимальное значение, называется оптимальным планом транспортной задачи.
Обычно исходные данные записываются в виде таблицы 1.
Таблица 1.
| Пункты отправления | Пункты назначения | Запасы | ||||
| В1 | … | Bj | … | Bn | А1 | |
| A1 | C11 X11 | … | C1j X1j | … | C1n X1n | a1 |
| … | … | … | … | … | … | … |
| Ai | Ci1 Xi1 | … | Cij Xij | … | Cin Xin | ai |
| … | … | … | … | … | … | … |
| Am | Cm1 Xm1 | … | Cmj Xmj | … | Cmn Xmn | am |