Постановка задачи
1. В m пунктах отправления 
, которые будем в дальнейшем называть поставщиками, сосредоточено определенное количество единиц некоторого однородного продукта, которое обозначим 
.
Однородный – одного вида (например: пищевые продукты, одежда, обувь, ткани).
2. Данный продукт потребовался в n пунктах 
, которые будем называть потребителями. Объем потребителя обозначим 
.
3. Известны расходы на перевозку единицы продукта из пункта 
в пункт 
, которые равны 
и приведены в матрице транспортных расходов 
.
4. Требуется составить такой план прикрепления потребителей к поставщикам, т.е. план перевозок, при котором
1) весь продукт вывозится из пунктов 
в пункты в соответствии с потребностью
2) общая величина транспортных издержек будет минимальной.
Обозначим количество продукта, перевозимого из пункта в пункт через 
. Тогда получим матрицу перевозок 
.
А также матрицу стоимости перевозок (иногда ее называют «матрицей тарифов»)
Тогда целевая функция задачи имеет вид
(4.1)
а ограничения выделяют следующим образом:
(4.2)
(Условие по потребности)
(4.3)
(Условие по запасам)
(4.4)
Необходимым и достаточным условием того чтобы задача имела решение, является условие баланса:
(4.5)
Транспортная задача, в которой имеет место равенство (5) называется закрытой.
Решение транспортной задачи состоит из 2-х этапов:
1) Нахождение первоначального опорного плана.
2) Нахождение оптимального плана перевозок по методу потенциалов.
Виды моделей транспортной задачи
Модель транспортной задачи включает в себя: целевую функцию (4.1) и систему ограничений (4.2), (4.3) и (4.4).
Модель транспортных задач бывает 2-х типов.
1. Закрытая модель .
Для того чтобы решать транспортную задачу ее необходимо привезти к закрытому виду.
Для закрытых моделей доказана теорема о существовании допустимого плана.
Теорема. Для того чтобы транспортная задача имела допустимые планы необходимо и достаточно, чтобы объем запасов совпадал с объемом потребностей.
2. Открытые модели:
2а) 
Запасы превышают потребности
В этом случае вводится фиктивный потребитель 
, потребности которого равны 
. Стоимость перевозки единицы груза от поставщиков к 
-му потребителю равна 0.
2б) 
Потребности превышают запасы
В этом случае вводится фиктивный поставщик 
. Запасы которого равны 
.
Построение первоначального опорного плана
В транспортной задаче существуют понятия вырожденного и невырожденного плана.
План невырожденный, когда количество занятых клеток равно 
, где m – число поставщиков, n – число потребителей.
План вырожденный, когда количество занятых клеток 
.
Если план оказывается вырожденным, то следует часть свободных клеток условно считать занятыми. Для этого в них реально записываются нули, которые стоят там «негласно». Это делают в одной или нескольких клетках, исходя из требования, состоящего в том, что общее число занятых клеток должно быть 
. В дальнейшем с другими клетками обращаются как с занятыми.
| Поставщики | Потребители | Запасы | ||||
| 
| 
| … | 
| ||
| С11
| С12
| 
| |||
| 
| |||||
| 
| |||||
| … | … | |||||
| Сmn
| 
| ||||
| Потребности | 
| 
| 
| … | 
|
Метод северо-западного угла для построения первоначального опорного плана
Есть 4 поставщика 
, у них запасы 
. Есть 5 потребителей 
, у них потребности 
; 
; 
, 
, 
.
- модель закрытая.
Заполнение клеток в методе северо-западного угла начинается с левой верхней клетки 
и туда заносят либо 
либо 
, после чего вычеркивают строку для поставщика либо столбец для потребителя .
| Поставщики | Потребители | Запасы | ||||
|
|
|
| 
| 
| ||
|
| - | - | - | - | ||
|
| ↓ 2 100→ | - | - | - | ||
|
| - | ↓ 5 50→ | 100→ | |||
| - | - | - | ↓ 16 50→ | ||
| Потребности |
Значение целевой функции для данного опорного плана
ед.
Проверяем число занятых клеток k
план невырожденный.