Общая постановка транспортной задачи
Важным частным случаем задачи ЛП является транспортная задача.
Задача. Имеются 3 поставщика и 4 потребителя. В таблице приведены мощности поставщиков и спросы потребителей, а также затраты на перевозку единицы груза для каждой пары «поставщик – потребитель».
| Поставщики | Мощность поставщиков | Потребители и их спрос | |||
х11 
| х12 | х13 | х14 | ||
| х21 | х22 | х23 | х24 | ||
| х31 | х32 | х33 | х34 |
В левом верхнем углу (i, j) клетки (i – номер строки, j - номер столбца) стоит коэффициент затрат (затраты на перевозку 1 ед. груза от i-го поставщика jтому потребителю). Необходимо найти объемы перевозок для каждой пары «поставщик – потребитель» так, чтобы:
1) мощности всех поставщиков были реализованы;
2) спросы всех потребителей были удовлетворены;
3) суммарные затраты на перевозку были бы минимальными.
Р е ш е н и е: построим экономико-математическую модель задачи. Искомый объем перевозки от i-того поставщика к j-тому потребителю обозначим через хij и назовем поставкой клетки (i; j). Объем груза, забираемого от 1-го, например, поставщика должен быть равен мощности этого поставщика – 60 ед. Значит х11 + х12 + х13 + х14 = 60. Аналогично – для других поставщиков. Получим систему:
Аналогично необходимо удовлетворить спрос каждого потребителя и получим систему
.
Очевидно, что объем перевозимого груза не может быть отрицательным. Поэтому хij 
0. Суммарные затраты F на перевозку составят F = x11 + 2x12 + 5x12 + 3x14 + x21+ 6x22 + 5x23 + 2x24 + 6x31 + 3x32 + 7x33 + 4x34.
Тогда математическая формулировка задачи: на множестве неотрицательных решений системы ограничений найти такое решение Х = (x11, x12, …, x33, x34), при котором линейная функция F принимает минимальное значение.
Особенности экономико-математической модели транспортной задачи:
· система ограничений – система уравнений (т.е. задана в каноническом виде)
· коэффициенты при переменных системы ограничений равны 1 или 0
· каждая переменная входит в систему ограничений два раза.
Сформулируем постановку транспортной задачи в общем виде. Пусть сij – коэффициенты затрат, Мi – мощности поставщиков, Nj – мощности потребителей, i = 1, …,m; j = 1, …,n; m –число поставщиков, n – число потребителей. Система ограничений примет вид 
; ( 30 ) 
(31). Линейная функция F = 
(32).
Математическая формулировка транспортной задачи в общей постановке: на множестве неотрицательных (допустимых) решений системы ограничений (30) и (31) найти такое решение Х = (x11, x12, …, xmn), при котором значение линейной функции (32) минимально.
Произвольное допустимое решение Х = (x11, x12, …, xmn) системы ограничений (30) и (31) называют распределением поставок.
В рассмотренной выше задаче 
= 
. Задачи, удовлетворяющие этому условию, называют закрытыми. В противном случае модель и задача – открытая.
Решение транспортной задачи
Метод «северо-западного угла».
Одним из возможных методов нахождения первоначального базисного распределения поставок является метод «северо-западного угла».
Решим этим методом задачу п.1.2. Дадим переменной х11 максимально возможное значение (поставку в клетку (1,1) – «северо-западный» угол таблицы поставок): х11 = min{60, 20} = 20. после этого спрос 1-го потребителя удовлетворен полностью (клетки ниже перечеркнуты пунктиром).
| ||||
|
20
| ||||
В таблице поставок найдем новый «северо-западный угол» - клетка (1, 2) и дадим в нее максимально возможной значение. Учтем, что у первого поставщика осталось только 40 ед. товара, тогда х12 = min{40; 110} = 40. И мощность первого поставщика полностью реализована (клетки (1,3), (1,4) – пунктиром). Далее снова ищем «северо-западный угол» и действуем аналогично до заполнения всей таблицы. Суммарные затраты F = 20 + 80+420+ 200 + 20 + 400 = 1140.
Недостаток этого метода в том, что он не учитывает коэффициенты затрат.