Министерство образования 
Республики Беларусь 
 
БЕЛОРУССКИЙ НАЦИОНАЛЬНЫЙ 
ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ 
 
Кафедра «Высшая математика № 2» 
 
 
 
 
 
 
 
РЕШЕНИЕ ЗАДАЧ ОПТИМИЗАЦИИ 
ТРАНСПОРТНОГО ТИПА 
 
Методические указания 
и контрольные задания 
 
 
 
 
 
 
 
 
 
 
 
Минск  
БНТУ  
2014 
МИНИСТЕРСТВО ОБРАЗОВАНИЯ РЕСПУБЛИКИ БЕЛАРУСЬ 
Белорусский национальный технический университет 
 
Кафедра «Высшая математика № 2» 
 
 
 
 
 
 
 
 
 
 
РЕШЕНИЕ ЗАДАЧ ОПТИМИЗАЦИИ 
ТРАНСПОРТНОГО ТИПА 
 
Методические указания и контрольные задания 
для студентов инженерных и инженерно-экономических 
специальностей 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Минск  
БНТУ  
2014 
УДК 519.85(075.8) 
ББК 18.87я7 
Р47 
 
Составитель   А. Д. Корзников 
 
Рецензенты :  
канд. физ.-мат. наук, доцент В. В. Веременюк; 
канд. физ.-мат. наук, доцент И. Н. Катковская 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Методические указания предназначены для студентов экономических и 
технических специальностей при изучении разделов «Математическое про-
граммирование», «Прикладная математика» и «Математические методы 
поиска оптимальных решений». Описаны алгоритмы решения задач опти-
мизации транспортного типа, основанные на идеях линейного программи-
рования (модифицированный метод потенциалов) и методах оптимизации 
на графах. Работа алгоритмов детально проиллюстрирована на примерах. 
Подобраны задачи для самостоятельного решения. В силу чрезвычайной 
простоты программная реализация сетевого алгоритма вполне доступна 
студентам, обладающим элементарными навыками программирования.  
Издание также будет полезно для преподавателей, ведущих занятия по 
соответствующим разделам. 
 
© Белорусский национальный  
технический университет, 2014 
3 
ОГЛАВЛЕНИЕ 
 
Введение .................................................................................................. 4 
 
1. Модифицированный метод потенциалов решения транспортной 
задачи с ограниченными пропускными способностями ..................... 5 
 
2. Двойственный алгоритм решения обобщенной транспортной 
задачи ..................................................................................................... 28 
 
Задачи для самостоятельного решения .............................................. 41 
 
Литература ............................................................................................ 44 
 
 
4 
ВВЕДЕНИЕ 
 
Среди оптимизационных задач особое место занимают задачи 
оптимизации транспортного типа. Они являются математической 
моделью задач распределения некоторого продукта в территори-
ально агрегированных системах: информационных, транспортных, 
энергетических и т.п. Большинство таких моделей являются зада-
чами линейного программирования специального вида, наиболее 
распространенной из которых является классическая транспортная 
задача. Следует, однако, отметить, что классическая модель далеко 
не всегда достаточно адекватно отображает реально существующие 
задачи. В качестве такой модели больше подходит транспортная 
задача с ограниченными пропускными способностями, а еще луч-
ше – транспортная задача в сетевой постановке. До настоящего 
времени трудно назвать какую-либо книгу, имеющую характер 
практического руководства к решению задач такого типа. Настоя-
щее пособие поможет восполнить этот пробел. Предполагается, что 
читатель знаком с основами линейного программирования. 
В первой части рассматривается классическая транспортная за-
дача и модифицированный метод потенциалов решения транспорт-
ной задачи с ограничениями на пропускные способности. 
Во второй – оригинальный простой алгоритм решения транс-
портной задачи в сетевой постановке, позволяющий получить оп-
тимальное распределение продукта с указанием объемов и маршру-
тов поставки даже в случае, когда ограничения задачи являются не-
совместными. 
Решение любой реальной оптимизационной задачи немыслимы 
без применения компьютерной техники. Целью пособия является 
дать представление о содержании процесса решения задачи для его 
полной или частичной программной реализации. 
По каждому разделу подобраны контрольные задания для само-
стоятельного решения и решения с помощью ЭВМ. 
Методические указания предназначены для студентов экономи-
ческих и технических специальностей при изучении разделов «Ма-
тематическое программирование», «Прикладная математика» и 
«Математические методы поиска оптимальных решений». А также 
будет полезным для преподавателей, ведущих занятия по соответ-
ствующим разделам. 
5 
1. МОДИФИЦИРОВАННЫЙ МЕТОД 
ПОТЕНЦИАЛОВ РЕШЕНИЯ ТРАНСПОРТНОЙ ЗАДАЧИ 
С ОГРАНИЧЕННЫМИ ПРОПУСКНЫМИ 
СПОСОБНОСТЯМИ 
 
Транспортная задача является математической моделью широко-
го круга задач, которые чаще других встречаются в практических 
приложениях линейного программирования. Ее классическая фор-
мулировка состоит в следующем.  
Имеется m источников однородного продукта или взаимозаме-
няемых продуктов и n пунктов его потребления (или стоков). Зада-
ны объемы продукта ia  у каждого источника (или его мощность) и 
размеры спроса ib  (мощность) каждого стока. Известны также за-
траты ijc , связанные с перемещением единицы продукта из источ-
ника i в сток j. Кроме того, объем перемещаемого продукта из ис-
точника i в сток j не может превышать величины ijd  (пропускной 
способности коммуникации). Требуется составить план перемеще-
ния продукта из источников в стоки, обеспечивающий наиболее 
экономным путем максимальное удовлетворение спроса всех стоков 
(пунктов потребления), т.е. указать объемы , 0ij ij ijx x d  , пере-
мещаемого продукта из каждого источника i в каждый сток j, при 
которых общие затраты, связанные с этим перемещением будут ми-
нимальными.  
Таким образом, исходными данными для транспортной задачи 
являются: вектора    1 2 1 2, , , , , , ,m na a a a b b b b    мощности 
источников и стоков соответственно; матрица затрат ij m nC c   и 
матрица пропускных способностей коммуникаций ij m nD d  . 
Построим математическую модель сформулированной задачи. 
Обозначим через ij m nX x    план перемещения продукта. Тогда 
суммарные затраты , связанные с этим перемещением из всех ис-
точников во все стоки, выражаются суммой 
6 
1 1
m n
ij ij
i j
z c x
 
   .                                         (1) 
 
Если суммарная мощность источников 
1
m
i
i
a

     равна суммарной 
мощности стоков 
1
n
j
j
b

     , то транспортная задача называется замк-
нутой. Тогда условия полного удовлетворения спроса (мощности) 
каждого стока имеют вид 
 
1
, 1, 2, , .
m
ij j
i
x b j n

                                   (2) 
 
Весь продукт из каждого источника должен быть перемещен в 
стоки. Формально это означает, что 
 
1
, 1, 2, , .
n
ij i
j
x a i m

                                 (3) 
 
Кроме того, объемы переносимого продукта – неотрицательные 
числа, которые не могут превышать пропускных способностей со-
ответствующих коммуникаций, т.е. должны выполняться условия: 
 
0 , 1, 2, , ; 1, 2, , .ij ijx d i m j n       (4) 
 
Таким образом, формально, транспортная задача сводится к ми-
нимизации целевой функции (1), при условии, что переменные 
удовлетворяют ограничениям (2)–(4). 
Очевидно, что для любой матрицы ij m nX x  , удовлетворяю-
щей условиям (2) – (4), имеют место неравенства: 
  min , , 1, 2, , ; 1, 2, , .ij i jx a b i m j n     
7 
Поэтому, если  min ,ij i jd a b , для всех 1, 2, , ;i m   
1, 2, ,j n  , то мы имеем классическую транспортную модель. 
Условимся, что если  min ,ij i jd a b , то будем считать пропускную 
способность этой коммуникации равной любому числу большему, 
чем  min ,i ja b . 
Следует отметить, что во многих прикладных задачах суммарная 
мощность источников может превосходить суммарную мощность 
стоков 1
1 1
0
m n
n i j
i j
b a b
 
        и наоборот 1 1 1 0
n m
m j i
j i
a b a
 
       . 
Такая задача называется открытой транспортной моделью. От-
крытую модель можно свести к замкнутой. 
В первом случае вводится фиктивный сток  1n   с мощностью 
1nb  . Размеры остатка продукта , 1i nx   у каждого источника i  можно 
регулировать в зависимости от введенного штрафа за единицу ос-
тавшегося у i -го источника продукта. Часто полагают , 1 0,i nc    
1, 2, ,i m  . Пропускные способности , 1i nd   коммуникаций, веду-
щих в фиктивный сток  неограниченны, т.е. равны любому числу, 
большему, чем  1min ,i na b  , 1, 2, ,i m  . 
Во втором случае вводится фиктивный источник  1m   с мощно-
стью 1ma  . Размер неудовлетворенной мощности 1,m jx   j -го стока 
может регулироваться величиной ущерба 1,m jc  . Если ущерб для всех 
стоков одинаков, то полагают 1, 0m jc   , 1, 2, ,j n  . Пропускные 
1, ,m jd   1, 2, ,j n    неограниченны, т.е. равны любому числу, 
большему, чем величина  1min ,m ja b , 1, 2, ,j n   соответственно. 
В силу выше сказанного, в дальнейшем мы будем рассматривать 
замкнутую транспортную модель, т.е. полагая, что 
 
1 1
m n
i j
i j
a b
 
  .                                           (5) 
8 
Следует, однако, заметить, что если условие (5) является необ-
ходимым и достаточным для разрешимости классической транс-
портной задачи (  min ,ij i jd a b , 1, 2, ,i m  ; 1, 2, ,j n  ), то 
задача (1)–(4) не всегда разрешима при выполненных условиях (5), 
поскольку величины пропускных способностей коммуникаций мо-
гут оказаться недостаточными для перемещения всего имеющегося 
продукта. Однако, если существует допустимое решение, удовле-
творяющее ограничениям (2)–(4), то это гарантирует разрешимость 
задачи (1)–(4), так как линейная функция (1) заведомо ограничена 
на множестве допустимых решений. 
Задача (1)–(4) является задачей линейного программирования 
(ЛП) и может быть решена симплекс-методом (если существует до-
пустимое решение). Но для этого ее необходимо привести к кано-
нической форме, добавив в неравенства (4) неотрицательные сла-
бые переменные ,i jz ; , , , , ,, 0, 0,i j i j i j i j i jx z d x z     1, 2, ,i m  ; 
1, 2, ,j n  . Тогда переменных в задаче ЛП  2m n , а матрица 
ограничений хоть и имеет специфическую структуру (ее элементы 0 
или 1), ее порядок    2m n mn mn    очень велик, что, конечно 
же, нецелесообразно, т.к. вся информация о задаче содержится в 
матрицах ,C D  и векторах ,a b . Поэтому для ее решения использу-
ется модификация симплекс-метода, учитывающая эту специфику, 
которая называется методом потенциалов. 
Численный анализ транспортной задачи, как и любой задачи ЛП, 
существенным образом опирается на критерий оптимальности до-
пустимого решения ij m nX x  , выводить который нет необходимо-
сти, поскольку он является частным случаем соответствующих тео-
рем двойственности задачи ЛП. Приведем его формулировку. 
Теорема. Для оптимальности допустимого решения (плана) 
ij m n
X x   транспортной задачи, необходимо и достаточно суще-
ствование чисел 1 2, , , mu u u  и 1 2, , , nv v v  таких, что 
 
, если 0 ,i j ij ij iju v c x d       (6) 
 
, если 0,i j ij iju v c x       (7) 
9 
, если .i j ij ij iju v c x d       (8) 
 
Заметим, что если речь идет о классической транспортной задаче 
(  min ,ij i jd a b ), то условия (6)  (8) равносильны тому, что 
 
, если 0,i j ij iju v c x      (9) 
 
, если 0.i j ij iju v c x      (10) 
 
Решение любой задачи ЛП симплекс-методом осуществляется  
путем перехода от одного базисного решения к другому, для кото-
рого значение целевой функции уменьшается (в случае отыскания 
ее минимума). Поэтому и для транспортной задачи (ТЗ) базисные 
решения, которые мы будет называть опорными планами, играют 
особую роль. 
Число переменных ТЗ равно n m , а число ограничений  ра-
венств  m n . Переменные ijx  удобно нумеровать с помощью 
двух индексов. Поэтому допустимое решение Х задачи целесооб-
разно записывать в виде матрицы ij m nX x  , а не вектора, как в 
общей задаче ЛП. Однако, при анализе ТЗ бывает полезно записы-
вать условия (2), (3) в векторной форме. 
Обозначим через ijA  вектор, компоненты которого состоят из 
коэффициентов при переменной ijx . Размерность вектора ijA  сов-
падает с числом уравнений (2), (3) и равна  m n . Поскольку пе-
ременная ijx  входит только в i-е уравнение системы (2) и в j-е урав-
нение системы (3), причем коэффициенты при ней в обоих уравне-
ниях равны единице, то вектор ijA  имеет вид (см. ниже), т.е. у 
 n m -мерного вектора ijA  i-я и (m+j)-я компоненты равны еди-
нице, а остальные – нулю. 
10 
0
0
1
0
0
0
0
1
0
0
ijA
                       




 
 
Если обозначить 
1
2
1
2
m
n
a
a
a
B
b
b
b
              


, то система уравнений (2), (3) может 
быть записана в векторной форме 
 
1 1
m n
ij ij
i j
x A B
 
  .                                      (11) 
 
В ряде случаев оказывается удобным графический способ зада-
ния ТЗ. На плоскости отмечаются источники и стоки. Каждый ис-
i
m
m+j 
m+n 
11 
b1 b2 b3 
a1 a2 a3 
точник соединяется с каждым стоком, направленным отрезком 
(коммуникацией). На рис. 1 изображена ТЗ с тремя источниками и 
стоками, мощности которых 1 2 3, ,a a a  и 1 2 3, ,b b b  соответственно, а 
пропускные способности коммуникаций , 1, 2, 3; 1, 2, 3ijd i j  . 
 
 
 
 
 
 
 
                 d12                                                              d32      d33 
       d11                                          d22  
                     d13            d21                      d23           d31 
 
 
 
Рис. 1 
 
Решить задачу (1)(4) – это значит указать объемы ijx  переме-
щаемого продукта по каждой коммуникации  ,i j , связывающей 
i-й источник с j-м стоком, не превыщающие их пропускных способ-
ностей таким образом, чтобы сумма перемещаемого продукта из 
каждого источника и в каждый сток равнялась их мощности. При 
этом значение целевой функции (1) должно быть минимальным. 
Согласно общему определению базисного решения задачи ЛП, 
решение является базисным, если векторы, соответствующие в сис-
теме ограничений положительным переменным, являются линейно-
независимыми. Для ТЗ компоненту  ,i j  допустимого решения 
ij m n
X x   назовем основной, если 0 ij ijx d  . Для классической 
ТЗ правая часть неравенства выполняется автоматически, поэтому 
 ,i j  является основной компонентой, если 0ijx  . Следуя общему 
определению, допустимое решение Х для ТЗ будет базисным (опор-
12 
ным планом), если система векторов ijA  соответствующих основ-
ным компонентам допустимого решения Х, линейно независима. 
В силу специфики ТЗ как задачи ЛП, понятие опорного плана 
имеет наглядный геометрический смысл. Обратимся к графическо-
му способу задания ТЗ. Последовательность коммуникаций вида 
 
           1 1 2 1 2 2 1 1 1, , , , , ,..., , , , , ,k k k k k ki j i j i j i j i j i j      (12) 
 
назовем цепью коммуникаций, связывающей источник 1i  и сток kj . 
Например, цепь          2,1 , 3,1 , 3,2 , 1,2 , 1,3  на рис. 1 связывает 
источник 2 со стоком 3. Цепь коммуникаций характерна тем, что 
любые две ее соседние коммуникации либо исходят из одного ис-
точника, либо заканчиваются в одном стоке. Следует заметить, что 
в процессе движения по цепи коммуникаций часть из них будет 
проходить в противоположном направлении (от стока к источнику). 
Это  относится, например, к коммуникациям    3,1 , 1,2  (рис. 1). 
Цепь (12), к которой добавлена коммуникация  1, ki j  является 
замкнутой цепью или циклом. Так, если к цепи на рис.1 добавить 
коммуникацию  2,3 , то мы получим цикл, который начинается и 
заканчивается в источнике, с номером 2. 
Каждой коммуникации  ,i j  соответствует компонента  ,i j  
матрицы ij m nX x   и вектор ijA  ограничений ТЗ. Приводимое ни-
же утверждение дает возможность охарактеризовать линейно неза-
висимые системы векторов ограничений ТЗ в геометрических тер-
минах. 
Теорема 1. Система  ijA  векторов ограничений ТЗ является 
линейно независимой тогда и только тогда, когда из коммуникации 
соответствующих векторам системы, невозможно составить 
цикл. 
Эта теорема позволяет дать еще одно эквивалентное определе-
ние опорного плана ТЗ, которое имеет понятный геометрический 
смысл. 
13 
План ij m nX x   транспортной задачи является опорным, если из 
его основных компонент невозможно составить цикл. 
Между компонентами  ,i j  матрицы Х, векторами ограничений 
ijA  и коммуникациями  ,i j  в сетевой постановке ТЗ существует 
естественное взаимно однозначное соответствие: вектор ijA  соот-
ветствует компоненте матрицы Х, расположенной в i-й строке и j-м 
столбце и коммуникации  ,i j  в сетевой постановке ТЗ. В рас-
смотренном выше примере ТЗ в сетевой постановке 3m n  , т.е. 
матрица Х имеет порядок 3 3  (рис. 2). 
 
 
                                                0                 0 
 
 
                Х =             0                               
 
 
                                    0               0 
 
 
Рис. 2 
 
Компоненты, соответствующие цепи      2,1 , 3,1 , 3,2 ,  1,2 ,  
 1,3 , отмечены нулями. Из них невозможно составить цикл, следо-
вательно, система векторов 
 
21 31 32 12 13
0 0 0 1 1
1 0 0 0 0
0 1 1 0 0
, , , , ,
1 1 0 0 0
0 0 1 1 0
0 0 0 0 1
A A A A A
                                                                                              
 
 
ограничений является линейно независимой. 
14 
Если к рассматриваемой цепи добавить коммуникацию  2,3  
(компоненту  2,3  в матрице Х, пометив знаком «» (рис.2)), то 
получим цикл. Т.е. добавление в систему векторов ограничений 
вектора 23A  делает ее линейно зависимой. Действительно, легко 
проверить, что 23 13 12 32 31 21A A A A A A     . 
Приведем простой формальный алгоритм (правило вычеркива-
ния), который позволяет установить, образует ли некоторое множе-
ство S компонент матрицы Х цикл, и построить его в случае суще-
ствования, либо убедиться в отсутствии цикла. Последнее означает, 
что компоненты матрицы Х из данного множества S являются ба-
зисными. 
Последовательно просматриваем строки матрицы Х и вычерки-
ваем те из них, которые либо не содержат элементов множества S, 
либо содержат только один такой элемент. Затем просматриваем 
столбцы матрицы Х и вычеркиваем те из них, которые содержат не 
более одного (не вычеркнутого) элемента множества S. Далее по-
вторяем весь процесс, просматривая вначале строки, а затем столб-
цы матрицы Х (точнее, ее подматрицы, полученной в результате 
вычеркивания строк и столбцов на предыдущих шагах). Процесс 
заканчивается одним из двух исходов: 
1. Все строки и столбцы матрицы Х оказались вычеркнутыми. 
Это означает, что из компонент множества S невозможно составить 
цикл и, следовательно, они являются базисными. 
2. Не вычеркнутые элементы матрицы Х образуют ее подматри-
цу, в каждой строке и столбце которой имеется, по крайней мере, 
две компоненты из множества S. Двигаясь от любой компоненты 
множества S к другой строке, затем по столбцу, опять по строке и 
т.д. мы вернемся к начальной компоненте, так как число элементов 
множества S конечно. То есть, будет получен цикл. 
Таким образом, если X – опорный план ТЗ, то из его основных 
(базисных) компонент невозможно составить цикл, а число базис-
ных компонент равно 1m n  . Заметим, что если ТЗ является вы-
рожденной, то некоторые базисные компоненты могут равняться 0 
либо  min ,ij i jd a b . Мы не будем обсуждать вопросы, связанные 
с вырожденностью, ограничив себя случаем невырожденной задачи. 
Заметим только, что если к базисным компонентам опорного плана 
15 
добавить любую другую компоненту, то, как было показано выше, 
мы получим цикл, поскольку соответствующая система векторов 
ограничений ijA  станет линейно зависимой. 
Опишем отдельную итерацию модифицированного метода по-
тенциалов в предположении, что имеется опорный план ij m nX x   
(допустимое базисное решение) ТЗ. Если в ТЗ все  min ,ij i jd a b , 
1,..., ; 1,...i m j n  , то это обычный метод потеницалов. 
Обозначим через     ,B X i j   множество базисных компо-
нент опорного плана Х, 0(Х) – нулевых (небазисных), а D(X) компо-
нент (небазисных), равных  min ,ij i jd a b . 
1. Из системы уравнений    , ,i j iju v c i j B X   , составленных 
для каждой базисной компоненты  ,i j , находим потенциалы 
, 1,..., ; , 1,...i ju i m v j n  . Заметим, что поскольку число перемен-
ных m n  больше числа уравнений 1m n  , то одна переменная 
является заведомо свободной и может быть выбрана произвольно 
(например, равно 0). Это позволяет значительно облегчить процесс 
отыскания потенциалов.  
2. Проверяем опорный план на оптимальность. Вычисляем вели-
чины ij ij i jc u v     для всех небазисных компонент    ,i j B X  
опорного плана.Если 0ij   для    , 0i j X  и 0ij   для 
   ,i j D X , то опорный план Х является решением ТЗ. В против-
ном случае переходим к этапу 3 улучшения опорного плана. 
3. Среди чисел    , , 0ij i j X   и    , ,ij i j D X   есть отри-
цательные, и пусть наименьшее из них соответствует компоненте 
 0 0,i j . Возможны два случая: а)    0 0, 0i j X ; б)    0 0,i j D X . 
Дальнейшее течение этапа 3 определяется тем, какой из этих 
случаев имеет место. 
Замечание. В случае классической ТЗ (  min ,ij i jd a b ), может 
иметь место только случай а). 
16 
а) 
0 0
0i jx  . Улучшение плана Х осуществляется путем увеличе-
ния количества продукта, перемещаемого по коммуникации  0 0,i j  
(увеличения нулевой компоненты 
0 0i jx ). Добавление компоненты 
0 0i jx  к базисным компонентам порождает единственный цикл 
0 0 0 1 1 1 1 2 0
, , , , ...,
ki j i j i j i j i jx x x x x .  (13) 
Определим 
11 1 00,1,...,
min ( )
l li j kl k
x j j    , 2 0,1,...,min ( )l l l li j i jl k d x   , 
и положим 
0 01 2min( , , )i jd   . 
Для получения нового опорного плана с меньшим значением це-
левой функции, нечетные компоненты 
0 0 1 1
, , ...,
k ki j i j i jx x x , цикла 
(13) следует увеличить на  , четные компоненты 
0 1 1
,..., ,
k ki j i jx x   
1k ki jx  , цикла уменьшить на  . При этом будет получен новый 
опорный план. 
б) 
0 0 0 0i j i jx d . Улучшение плана Х осуществляется путем 
уменьшения количества продукта, перемещаемого по коммуника-
ции  0 0,i j  (уменьшения значения компоненты 0 0 0 0i j i jx d ). 
Для цикла (13) определим 1 0,1,...,min l li jl k x  , 
1 12 0,1,...,
min ( )
l l l li j i jl k
d x     1 0( )kj j  , и положим 1 2min( , )   . 
Уменьшим нечетные компоненты 
0 0 1 1
, , ...,
k ki j i j i jx x x  цикла (13) 
на  , и увеличим четные компоненты 
0 1 1 2
, ...,i j i jx x  1 0( )k k ki j i jx x , 
цикла  на величину  . В результате получим новый опорный план. 
Можно проверить, что в случае невырожденности задачи 
( 0)  , значение целевой функции для нового опорного плана бу-
дет меньше, чем для предыдущего. 
Таким образом, если исходный опорный план ТЗ найден, то че-
рез конечное число итераций метод приводит к ее решению (по-
следнее заключение следует, как обычно, из монотонного убывания 
целевой функции и конечности числа опорных планов задачи). 
17 
Как уже отмечалось, в отличие от классической транспортной 
задачи, рассматриваемая задача может не иметь ни одного опорного 
плана (ограничения несовместны). 
Излагаемый ниже способ дает возможность либо построить дос-
таточно экономичный опорный план ТЗ, либо убедиться в ее нераз-
решимости. 
Процесс построения исходного опорного плана складывается из 
предварительного этапа (метод минимального элемента) и ряда 
итераций метода потенциалов, применяемого к так называемой 
расширенной задаче. Предварительный этап разбивается на не-
сколько однотипных шагов.  
На первом шаге, среди элементов матрицы ij m nC c   выбира-
ется минимальный элемент 
1 1 1,...,
1,...,
mini j iji m
j n
c c
 .  
Находим 
1 1 1 1 1 1
min( , , )i j i j i jx a b d . Возможны три случая: 
1 1 1 1 1 1 1 1
, ,i j i i j j i j ijx a x b x d   . 
В первом случае определяем элементы 1i -й строки матрицы 
ij m n
X x  , полагая 1 0i jx   для всех 1j j . Во втором случае оп-
ределяем элементы 1j -ого столбца этой матрицы: 1 0ijx   для всех 
1i i . В последнем случае определяется только один элемент мат-
рицы Х (
1 1 1 1i j i jx d ). Далее вычеркиваем из матрицы С либо 1i -
строку (случай 1), либо 1j -столбец(случай 2), либо элемент 1 1i jc  
(случай 3) и изменяем величины ,i ja b  
1 1 1
1(1)
1
, ,
, ;
i
i
i i j
a i i
a a x i i
   
  
1 1
1(1)
1
, ,
, .
j
j
ij i j
b j j
b
b x j j
   
 
Замечание. Если ТЗ вырождена, то может иметь место одна из 
трех ситуаций 
1 1 1 1 1 1 1
min( , , )i j i j i i ja b d a d  , 1 1 1 1 1 1 1min( , , )i j i j i i ja b d b d   и 
1 1 1 1 1 1 1 1
min( , , )i j i j i j i ja b d a b d   . В первой ситуации поступаем как 
в случае 1, во второй – как в случае 2 и в третьей – произвольно: ли-
бо как в случае 1, либо как в случае 2. 
18 
Элемент 
1 1i jx матрицы Х полученный в случае 1 или 2 помечает-
ся как базисный (компонента 1 1( ; )i j добавляется к множеству В(Х) 
базисных компонент). 
Второй шаг состоит в проведении тех же операций применитель-
но к не вычеркнутым элементам матрицы Х и величинам (1)ia  и (1)jb . 
Шаги предварительного этапа следуют до полного заполнения 
матрицы Х. Заметим, что если  min ,ij i jd a b , для всех 1,..., ;i m  
1,...j n  (классическая транспортная задача), после предваритель-
ного этапа все строки и столбцы матрицы С вычеркнуты, а матрица 
Х является первоначальным опорным планом задачи. 
В общем случае, согласно процессу образования матрицы Х ее 
элементы удовлетворяют условиям: 
1
, 1, 2, , ,
n
ij i
j
x a i m

    
1
, 1, 2, , ,
m
ij j
i
x b j n

    0 ,ij ijx d   
1, 2, , ; 1, 2, ,i m j n    
Положим , 1
1
, 1, , ,
n
i n i ij
j
x a x i m

     
1,
1
, 1, , ,
m
m j j ij
i
x b x j n

     
, 1 1,
1 1
m n
i n m j
i j
x x  
 
   . 
Если 0  , то матрица Х является опорным планом ТЗ. В общем 
случае 0   и для получения опорного плана необходимо провести 
несколько итераций метода потенциалов для расширенной ТЗ. Она 
получается добавлением фиктивного источника ( 1)m   и стока 
( 1)n   с мощностями равными соответственно 1ma    и 1nb   . 
Если положить 1, 1 0m nx    , то полученная в результате предва-
рительного этапа матрица 
( 1) ( 1)ij m n
X x     является опорным пла-
ном расширенной ТЗ. Если положить 1,m jc M  , 1, , ,j n   
, 1i nc M  , 1, , ,i m   а 1, 1 0m nc    , где М сколь угодно большое 
19 
число, и применить к расширенной задаче метод потенциалов, то 
могут представиться следующие два случая. 
1. После ряда итераций получен опорный план X  расширенной 
задачи, для которого 1, 1m nx    . 
2. В оптимальном опорном плане X  1, 1m nx    . 
В первом случае подматрица Х матрицы X  является опорным 
планом исходной задачи, во втором – исходная задача не имеет ни 
одного допустимого решения и, следовательно, неразрешима. 
Приведем численный пример, иллюстрирующий описанный спо-
соб решения ТЗ. 
Вначале рассмотрим ТЗ без ограничений на пропускные способ-
ности коммуникаций (классическую транспортную задачу) с векто-
ром мощностей источников  6,3,3a   , стоков  4,2,4,2b   и мат-
рицей 
1 4 2 5
2 1 4 1
3 2 1 3
C
      
. Процесс решения начинается с предвари-
тельного этапа. 
 
 
 
 
 
 
 
(1) (5) (6)
(2) (4)
(3)
(1) (2) (3) (4) (5) (6)
4 0 1 1 6 2 2 2 2 1
0 2 0 1 3 3 1 1
3 3 30 0 3 0
4 2 4 2
2 4 2 1
4 2 2
1 2 3
1 1 4
51
6
X
       
 
 
20 
1 4 2 5
2 1 4 1 (4)
3 2 1 3 (3)
(1) (2) (5) (6)
C
      
. 
 
Цифры, стоящие в скобках около строк и столбцов матрицы С, 
обозначают номер шага, на котором соответствующие строки и 
столбцы вычеркиваются. Цифры в скобках над элементами матри-
цы Х обозначают номер шага, на котором определяются ее соответ-
ствующие элементы, а над столбцами вектора a  и около строк век-
тора b  – номера шагов, на которых они принимают указанные зна-
чения. Поскольку после 6-го шага в первой строке нет ни одного не 
вычеркнутого элемента, она может быть вычеркнута (правило вы-
черкивания). То есть положительные компоненты матрицы Х не об-
разуют цикл, их число равно 6 (m + n – 1 = 3 + 4 – 1 = 6). Таким об-
разом, в результате предварительного этапа получен исходный 
опорный план ТЗ, множество базисных компонент 
           ( ) { 1,1 , 1,3 , 1,4 , 2,2 , 2,4 , 3,3 }B X  , ( ) , ( )D X O X  все 
остальные компоненты плана Х. 
Итерация 1. Определяем потенциалы, отвечающие исходному 
опорному плану путем решения системы уравнений: 
1 1 1u v  ; 2 2 1u v  ; 1 3 2u v  ; 2 4 1u v  ; 1 4 5u v  ; 3 3 1u v  . 
Полагая 1 0u  , последовательно вычисляем 1 1v  , 3 2v  , 4 5v  , 
2 1 5 4u     , 2 1 ( 4) 5v     , 3 1 2 1u     . Вычисляем величины 
, ( , ) ( )ij i j O X  : 
12 4 0 5 1      ; 21 2 ( 4) 1 5      ; 23 4 ( 4) 2 6      ; 
31 3 ( 1) 1 3      ; 32 2 ( 1) 5 2       ; 34 3 ( 1) 5 1       . 
План не является оптимальным, т.к. 12 32 34, , 0    , 
12 32 34 32min( , , ) 2       . Улучшение плана осуществляется за 
счет увеличения компоненты 32x , добавление ее к базисным компо-
нентам порождает единственный цикл 32x , 22x , 24x , 14x , 13x , 33x . 
Определяем 1 22 14 33min( , , ) 1x x x   . 
21 
Увеличиваем нечетные компоненты цикла (помеченные знаком 
«+») и уменьшаем четные (помеченные знаком «») на величину 
1 1   и получаем новый опорный план (рис. 3) (пустые клетки со-
ответствуют нулевым компонентам плана). 
 
 
 
 
 
 
 
 
 
 
 
Рис. 3 
 
Итерация 2. Множество базисных компонент 
           ( ) { 1,1 , 1,3 , 2,2 , 2,4 , 3,2 , 3,3 }B X  , ( ) , ( )D X O X   все 
остальные компоненты плана. Определяем потенциалы для полу-
ченного опорного плана: 
 
1 1 1u v  ; 1 3 2u v  ; 2 2 1u v  ; 2 4 1u v  ; 3 2 2u v  ; 3 3 1u v  . 
 
Полагая 1 0u  , последовательно вычисляем 1 1v  , 3 2v  , 3 1u   , 
2 3v  , 2 2u   , 4 3v  . Вычисляем величины , ( , ) ( )ij i j O X  : 
 
12 4 0 3 1     ; 14 5 3 0 2     ; 21 2 ( 2) 1 3      ; 
 
23 4 ( 2) 2 4      ; 31 3 ( 1) 1 3      ; 34 3 ( 1) 3 1      . 
 
Поскольку все величины неотрицательны, то план является ре-
шением нашей задачи. 
Решим теперь эту задачу в случае, когда пропускные способно-
сти коммуникаций ограничены и их пропускные способности опре-
деляются матрицей 
3 1 2 1
1 1 1 2
2 1 1 1
D
      
. 
4  2  
 1  2 
 1 2  
( ) ( )
( ) ( )
( ) ( )
4 0 1 1
0 2 0 1 ,
0 0 3 0
X X
 
 
 
           
22 
Предварительный этап. 
Шаг 1. 11,min 1iji j c c  , 11 1 1 11min( , , ) min(6,4,3)x a b d   11 3d  . 
Имеет место случай 3. Вычеркиваем элемент 11c , изменяем компо-
ненты 1a  и 1b  векторов a  и b  уменьшив их на 3. 
Шаг 2. 22,min 1iji j c c  , 22 2 2 22min( , , ) min(3,2,1)x a b d   22 1d  . 
Случай 3, 2 2a  , 2 2b  , вычеркиваем элемент 22c . 
 
(9)
(10) (3)
(7) (6) (8)
(1) (2) (3) (4) (5) (6) (7) (8) (9) (10)
3 2 0 6 3 3 3 3 1 1 1 1 1
1 0 2 3 3 2
3 3 3 3 2 2 1 01 1 1 0
4 2 4 2
1 2 4 2 (1)
1 1 4 2 (2)
1 1 4 0 (3)
1 1 3 0 (4)
1 1 1 0 (5)
1 1 0 (6)
1 0 (7)
1 0 (8)
1 (9)
X
       
 
(1) (5)
(2) (10)
(4)
1 4 2 5
2 1 4 1 (3)
(8)3 2 1 3
(7) (6) (9)
C
       
 . 
23 
Шаг 3. 24,min 1iji j c c  , 24 2 4 24 2min( , , ) min(2,2,2) 2x a b d a    . 
Случай 1: Вычеркиваем вторую строку матрицы С, переменная 24x  
становится базисной, 4 0b  . 
Шаг 4. 33,min 1iji j c c  , 33 3 3 33 33min( , , ) min(3,4,1) 1x a b d d    . 
Случай 3: вычеркиваем элемент 33c , 3 2a  , 3 3b  . 
Шаг 5. 13,min 2iji j c c  , 13 1 3 13 13min( , , ) min(3,3,2) 2x a b d d    . 
Случай 3: вычеркиваем элемент 13c  матрицы С, 1 1a  , 3 1b  . 
Шаг 6. 32,min 2iji j c c  , 32 3 2 32 2min( , , ) min(2,1,1) 1x a b d b    . 
Случай 2: переменная 32x  становится базисной, вычеркиваем вто-
рой столбец матрицы С, 3 1a  . 
Шаг 7. 31,min 3iji j c c  , 31 3 1 31 1min( , , ) min(1,1,2) 1x a b d b    .  
Случай 2, вычеркиваем первый столбец матрицы С, переменная 31x  
становится базисной, 3 0a  . 
Шаг 8. 34,min 3iji j c c  , 34 3 4 34 3min( , , ) min(0,0,1) 0x a b d a    . 
Случай 1: вычеркиваем третью строку матрицы С, переменная 
34 0x   становится базисной. 
Шаг 9. 14,min 5iji j c c  , 14 1 4 14 4min( , , ) min(1,0,1) 0x a b d b    . 
Случай 2: вычеркиваем четвертый столбец матрицы С, переменная 
14 0x   становится базисной. 
Шаг 10. Первая строка и третий столбец остались не вычеркну-
тыми. Единственный не вычеркнутый элемент третьего столбца 
23 0x  , помечаем его как базисный и вычеркиваем третий столбец. 
Согласно правилу вычеркивания, выделенные компоненты обра-
зуют базис, однако построенная матрица Х не является допустимым 
решением задачи, так как 41 15 1x x    . Поэтому необходимо пе-
рейти к решению расширенной ТЗ с матрицей 
 
24 
1 4 2 5
2 1 4 1
3 2 1 3
0
M
M
C
M
M M M M
       
 
 
и векторами  6,3,3,1a  ,  4,2,4,2,1b  . Исходный опорный план 
расширенной ТЗ имеет вид 
 
   
   
     
 
3 0 2 0 1
0 1 0 2 0
1 1 1 0 0
0 0 1 0 0
X
 

 
                  



. 
 
В скобках записаны базисные элементы опорного плана. 
Итерация 1. Определим потенциалы расширенной ТЗ, отвечаю-
щие полученному опорному плану X  путем решения системы 
уравнений 1 4 5u v  ; 3 1 3u v  ; 1 5u v M  ; 3 2 2u v  ; 2 3 4u v  ; 
3 4 3u v  ; 2 4 1u v  ; 4 3u v M  . 
Полагая 4 0v  , последовательно вычисляем 1 5u  , 2 1u  , 
3 3u  , 3 4 1 3v    , 2 1v   , 1 3 3 0v    , 4 3u M  , 5 5v M  . 
Для компонент  ,i j  из множеств 
               ( ) { 1,2 , 2,1 , 2,5 , 3,5 , 4,1 , 4,2 , 4,4 , 4,5 }O X   и 
       ( ) { 1,1 , 1,3 , 2,2 , 3,3 }D X   вычисляем величины 
ij ij i jc u v    : 
12 4 5 1 0     ; 21 2 1 0 1     ; 22 1 1 ( 1) 1      ; 
25 
25 1 ( 5) 4M M      ; 35 3 ( 5) 1 2M M       ; 
41 ( 3) 0 3M M      ; 42 ( 3) ( 1) 4M M       ; 
44 ( 3) 0 3M M      ; 45 0 ( 3) ( 5) 2 8M M M         ; 
11 1 5 0 4      ; 13 2 5 3 6      ; 33 1 3 3 5      . 
Поскольку среди величин , ( , ) ( )ij i j O X   есть отрицательные, 
а среди , ( , ) ( )ij i j D X    положительные, план X  не является 
оптимальным. Минимальное из значений , для ( , ) ( )ij i j O X   и 
, для ( , ) ( )ij i j D X   равно 45 2 8M     (М сколь угодно боль-
шое число). Поэтому, изменяем опорный план увеличивая (вводя в 
базис) переменную 45x (случай а)). Добавление компоненты 45x  к 
базисным порождает единственный цикл 45x , 15x , 14x , 24x , 23x , 43x .  
Определим 
1 15 24 43min( , , ) min(1,2,1) 1x x x    , 
2 45 45 14 14 23 23min( , , ) min( 0,1 0,1 0) 1d x d x d x            
1 2 45min( , , ) min(1,1, ) 1d      . 
Для получения нового опорного плана нечетные компоненты 
45x , 14x  и 23x  увеличиваем на 1, а четные 15x , 24x , 43x  уменьшаем 
на единицу, при этом компонента 15x  или 43x  должна быть выведе-
на из базиса. Исключим из базиса 43x .  
Переходим к новому опорному плану 
   
   
   
 
3 0 2 1 0
0 1 01 1
1 0 01 1
0 0 0 0 1
X
        
. 
26 
Поскольку 45 1x   , то матрица 
 
   
     
3 0 2 1
0 1 1 1
1 1 1 0
X

 
          


 явля-
ется опорным планом исходной задачи. 
Итерация II. Для базисных компонент плана Х составляем сис-
тему уравнений 1 4 5u v  ; 3 1 3u v  ; 1 3 4u v  ; 3 2 2u v  ; 
2 4 1u v  ; 3 4 3u v  , решив которую найдем потенциалы. Полагая 
3 0u  , последовательно вычисляем 1 3v  , 2 2v  , 4 3v  , 2 2u   , 
3 6v  , 1 2u  . 
Для компонент  ,i j  из множеств    ( ) { 1,2 , 2,1 }O X   и 
       ( ) { 1,1 , 1,3 , 2,2 , 3,3 }D X   вычисляем величины ij ij i jc u v    : 
 
12 4 2 2 0     ; 21 2 ( 2) 3 1      ; 11 1 2 3 4      ; 
 
13 2 2 6 6      ; 22 1 ( 2) 2 1      ; 33 1 0 6 5      . 
 
Так как 22 0 ( (2,2) ( ))D X   , план Х не является оптимальным, 
и его улучшение должно производиться за счет уменьшения вели-
чины 22 22 1x d   (случай б)). Добавление компоненты 22x  к базис-
ным порождает единственный цикл 22x , 24x , 34x , 42x . 
Определим 1 22 34min( , ) min(1,0) 0x x    ,  
2 24 24 32 32min( , ) min(1,0) 0d x d x      ,  
1 2 22min( , , ) 0x    .  
Переменная 22x  становится базисной, а 34x  выводится из базиса. 
Новый опорный план отличается от предыдущего только тем, что в 
число базисных переменных включена 22 22 1x d   взамен пере-
менной 34 0x  . 
27 
 
     
   
3 0 2 1
0 1 1 1
1 1 1 0
X

 
          


. 
 
Итерация III. Как и на предыдущих итерациях находим потен-
циалы 1 4u  , 2 0u  , 3 1u  , 1 2v  , 2 1v  , 3 4v  , 4 1v  . Для 
компонент  ,i j  из множеств    ( ) { 1,2 , 2,1 ,(3,4)}O X   и 
     ( ) { 1,1 , 1,3 , 3,3 }D X   вычисляем величины ij ij i jc u v    : 
 
12 4 4 1 1      ; 21 2 0 2 0     ; 11 1 4 2 5       
 
13 2 4 4 6      ; 33 1 1 4 4       34 3 1 1 1     . 
 
Так как 12 1 0, (1,2) ( )O X     , то план Х не является опти-
мальным и его улучшение производится за счет увеличения вели-
чины 12 0x   (случай а)), ее добавление к базисным порождает 
единственный цикл: 12x , 22x , 24x , 14x . 
Находим 1 22 14min( , ) min(1,1) 1x x    ,  
2 12 12 24 24min( , ) min(1 0,2 1) 1d x d x        , 
1 2min( , ) 1    . 
Новый опорный план получается путем увеличения переменных 
12x , 24x  и уменьшения 22x , 14x  на 1. 
 
3 1 2 (0)
0 (0) (1) (2)
(1) (1) 1 0
X
      
. 
 
В число базисных переменных вводится 12x . Поскольку все эле-
менты цикла равны либо 0, либо ijd  ( 12 12 1x d  , 24 24 2x d  , 
28 
22 14 0x x  ), из базиса должна быть исключена одна из переменных 
12x , 24x , 22x , 14x . Исключим из базиса переменную 12x  (т.е. она так и 
не вошла в число базисных). Это облегчит следующую итерацию. 
Итерация IV. Поскольку множество базисных переменных не 
изменилось, то потенциалы и величины  остались прежними. Изме-
няются только множества ( )O X  и ( )D X :  ( ) { 2,1 ,(3,4)}O X  ,  
       ( ) { 1,1 , 1,2 , 1,3 , 3,3 }D X  .  
Так 21 0  , 34 1  , а 11 5   , 12 1   , 13 6   , 33 4   , то 
условия критерия оптимальности выполняются, т.е. полученный 
опорный план является оптимальным. 
 
 
2. ДВОЙСТВЕННЫЙ АЛГОРИТМ РЕШЕНИЯ 
ОБОБЩЕННОЙ ТРАНСПОРТНОЙ ЗАДАЧИ 
 
Как уже отмечалось, в наиболее общей постановке транспортная 
задача может быть сформулированы в следующем виде. 
 
1 1
min,
m n
ij ij
i j
c x
 
      (2.1) 
 
1
, 1, ,
n
ij i
j
x a i m

     (2.2) 
 
1
, 1, ,
m
ij j
i
x b j n

     (2.3) 
 
0 , 1, , 1, .ij ijx d i m j n      (2.4) 
 
Введением фиктивных поставщика или потребителя она легко 
сводится к замкнутой модели с выполненным балансовым соотно-
шением: 
1 1
m n
i j
i j
a b
 
  , которые являются необходимым и достаточ-
29 
ным условием разрешимости классической транспортной задачи.  
Ограничения на пропускные способности коммуникаций сущест-
венно усложняют решение задачи. В этой ситуации возникают про-
блемы не только с применением симплекс-метода или его модифи-
каций к решению задачи, но и с построением первоначального ба-
зисного решения. Условия разрешимости задачи  также непригодны 
для практического применения. 
Как известно, для того, чтобы ТЗ с ограничениями на пропуск-
ные способности коммуникаций имела решение необходимо и дос-
таточно выполнение условий: 
 
 
1
min ( , ) , 1, .
m
i ij j
i j J j J
a d b J n
  
       (2.5) 
 
Понятно, что проверка выполнения условий (2.5) задача более 
трудоемкая, чем ее решение. Поэтому для построения первоначаль-
ного допустимого решения используется метод искусственного ба-
зиса, который в случае несовместимости ограничений позволяет 
установить неразрешимость задачи. Однако, при решении конкрет-
ных прикладных задач, в случае несовместности ограничений, мо-
жет потребоваться составить план перемещения максимально воз-
можного объема продукта с минимальными затратами. При этом, 
естественно, необходим анализ, позволяющий установить «узкое 
место», то есть те коммуникации, пропускные способности которых 
не позволяют осуществить поставки в полном объеме. Такой анализ 
может быть осуществлен, если рассматриваемую задачу сформули-
ровать в терминах теории графов (графический способ задания ТЗ). 
Естественно полагать, что  min , , 1, , 1, .ij i jd a b i m j n     
Рассмотрим ТЗ, заданную векторами мощностей источников 
 1 2, ,..., ma a a a  и стоков  1 2, ,..., nb b b b , матрицами пропускных 
способностей ij m nD d   и стоимостей перемещения единицы про-
дукта ij m nC c  .  
На плоскости отмечаются (кружками) источники (с номерами 1, 
2, …, m) и стоки (с номерами 1, 2,m m m n   ), а также отмечают-
30 
ся фиктивный источник и сток с номерами 1n m   и 2n m   со-
ответственно (рис. 4). 
 
 
                                       1                                           m+1 
                                                                                    
                                                                                    
 
        m+n+1                    i                                             m+j                     m+n+2 
 
                                                                                     
                                                                                     
 
                                      m                                           m+n 
 
Рис. 4 
 
Если определить пропускную способность коммуникации 
( 1,m n i  ) равной ia , коммуникации ( , 2m j m n   ) равной jb , 
а стоимости переноса по ним единицы продукта равными 0, то за-
дача может быть сформулирована следующим образом: построить 
максимальный поток продукта из фиктивного источника ( 1m n  ) 
в фиктивный сток ( 2m n  ), стоимость которого минимальна. По-
нятно, что величина потока 0klx   по любой коммуникации  ,k l  
не может превышать ее пропускной способности kld . Суммарный 
объем продукта, перемещаемого из каждого источника i , равен ве-
личине продукта перемещаемого в i из фиктивного источника 
( 1m n  ), а суммарный объем продукта, перемещаемого в каждый 
сток j, равен величине продукта перемещаемого из j в фиктивный 
сток ( 2m n  ). 
Графическое представление рассмотренного выше численного 
примера представлено на рис. 5, где над каждой коммуникацией (в 
скобках) первое число – стоимость переноса по ней единицы про-
дукта, а второе – ее пропускная способность. 
Графическое представление ТЗ очень удобно для ее анализа, од-
нако алгоритмы решения, связанные с графическим представлени-
ем, трудно реализуемы. Тогда как вся информация о задаче содер-
жится в векторах ,a b  и матрицах иC D . 
31 
                                            (1,3) 
                                       1                                            4 
                                                                                                   (0,4) 
                                     (5,1) 
           (0,6) 
                                        (2,0)             (2,2)            (4,1) 
 
          8        (0,3)           2     (1,1)                                5      (0,2)             9 
 
                                             (1,4) 
                                    (2,1)                                                 (0,4) 
        (0,3) 
                                                                                     6 
                                         (2,3) 
                                                (1,2)                                             (0,2) 
 
                                                               (1,1) 
                                       3                                            7 
                                                 (1,3) 
 
Рис. 5 
 
Введем в рассмотрение векторы модифицированных мощностей    * *1 1 1* ,..., ,..., , ,..., ,n m m na a a a a b b   
   * *1 1 1* ,..., ,..., , ,..., ,n m m nb b b a a b b   
матрицы модифицированных стоимостей ** ijC c  и пропуск-
ных способностей ** ijD d  порядка    1 2m n m n     , опре-
деленных следующим образом: 
 
*
0, 1, 1, ,
0, 1, , 2,
, 1, , 1, ,
, в остальных случаях,
ij
ij
i m n j m
i m m n j m n
c
c i m j m m n
               
 
32 
*
, 1, 1, ,
, 1, , 2,
, 1, , 1, ,
0, в остальных случаях.
j
i
ij
ij
a i m n j m
b i m m n j m nd
d i m j m m n
               
 
 
Опишем алгоритм решения задачи ТЗ. Не уменьшая общности, 
будем предполагать, что  min , ,ij i jd a b если  min ,ij i jd a b  для 
всех 1, , 1, .i m j n   
Предварительный этап. Обозначим ** ijX x   нулевая матри-
ца порядка    2 2 .m n m n      Если i j
i j
a b  , последова-
тельно для каждой строки 1,2,...,i m  матрицы ij m nC c  , находим 
минимальный элемент minil ijjc c . Если при этом 
 min , , 0il i il la d b   , то полагаем: 
 
*
,
* * *
, , , ,
* *
, , , ,
* *
* * * *
, если ,
, если ,
, : , : ,
: : , : : ,
: : , : : ,
: , : .
il il il
i m l
il il
m l i i l i m l il m l i il
i m l i m l il m l i m l i il
m l m l il m l m l il
i i il i i il
c d
c
d
c c x x
d d d d
a a b b
a a b b


 
 
 
 

  
   
   
  
    
   
   
   
 
 
Если после осуществления указанных выше действий получим 
*
1
0
m
i
i
a

 , то задача решена, иначе переходим к общей итерации. В 
случае, когда i j
i j
a b  , последовательно для каждого столбца 
33 
1,2,...,j n  матрицы ij m nC c   находим минимальный элемент 
minlj ijic c . Если  min , , 0lj l lj ja d b   , то для столбца j полагаем: 
 
* *
, ,
* *
, ,
* * * *
, , , ,
* * * * * * * *
,
, если ,
,
, если ,
: , .
: , ,
: , : , : , : .
lj lj
lj lj lj
l m j m j l lj
lj lj
l m j lj m j l lj
l m j l m j lj m j l m j l lj
l l lj m j m j lj m j m j lj l l lj
x
c d
c c c
d
x x
d d d d
a a b b a a b b



 
 
   
 
 
   
   

   
  
   
       
 
 
Если после выполнения этих операций 0j
j
b  , то задача реше-
на. В противном случае переходим к общей итерации. 
Замечание. Предварительный этап не является обязательным, 
т.е. решение может начинаться с общей итерации с нулевой мат-
рицей ** ijX x  порядка    2 2 .m n m n      Однако при ручной 
обработке результатов выполнения тернарных операций на каж-
дой итерации, предварительный этап позволяет уменьшить их 
число. 
Общая итерация. Осуществляем тернарные операции над эле-
ментами матрицы модифицированных стоимостей ** * ijC C c  , 
последовательно по всем 1,2,..., 2k n m   ; полагая 
 
* * * *
*
* * * * *
, если ,
:
, если ,
ij ij ik kj
ij
ik kj ij ik kj
c c c c
c
c c c c c
      
  (2.6) 
 
для всех , 1, 2, 1, 2.i j k i n m j n m         
34 
Одновременно с выполнением операций (2.6) изменяем элемен-
ты вспомогательной матрицы ** ijR r  порядка    2 2m n m n      
(первоначально полагаем * , ,ijr j i  1, 2j n m   ): 
* * **
*
* * **
, если ,
:
, если .
ij ik kjij
ij
ij ik kjik
r c c c
r
r c c c
     
   (2.7) 
 
Если * 1, 2m n m nc         задача решена. В противном случае, с 
помощью вспомогательной матрицы R* определяем множество ин-
дексов 1 21, , ,..., , 2 ,kl m n i i l m n p       где 1 1, 2 ,m n m ni r      
12 , 2,i m ni r    23 , 2..., ,ki m n l pi r p r    и множество       1 1 2, , , ,..., ,kL l i i i i p . 
Находим    ,min , ,i ij ji j L a d b   и вычисляем: 
 
 
*
* *
*
, , ,
: , , ,
в остальных случаях.
ij
ij ij
ij
x i j L
x x j i L
x


    
 
 
 
*
* *
*
, , ,
: , , ,
в остальных случаях.
ij
ij ij
ij
d i j L
d x j i L
d


    
 
* * * * * * * *: , : , : , : .l l p p p p l l ja a b b a a b b            
*
* *
*
, 1, , если 0,
, 1, , если 0,
, в остальных случаях.
i
ij j
ij
j n m a
c i n m b
c
       
 
Переходим к общей итерации. 
После окончания работы алгоритма находим матрицу 
ij m n
X x  , где 
*
, , 1, ,ij i m jx x i m   1,j n , которая является ре-
35 
шением задачи. Если одно из ограничений не выполнено, то это оз-
начает, что исходная задача не имеет допустимых решений. Тем не 
менее, полученный план является оптимальным планом перемеще-
ния максимально возможного количества продукта из источников в 
стоки при данных ограничениях. Отметим, что на каждой итерации 
работы алгоритма увеличение объема перемещаемого продукта пе-
ревозки на величину  осуществляется с минимально возможным 
увеличением значения целевой функции, то есть, получаемый на 
каждой итерации план является оптимальным, но недопустимым. 
На каждой итерации мы получаем оптимальное решение (мини-
мальное значение целевой функции) для данной величины 
1 1
m n
ij
i j
V x
 
   , которое не является допустимым, если maxV V . В 
этом случае, описанный алгоритм естественно трактовать как двой-
ственный. 
Проиллюстрируем работу алгоритма на рассмотренном выше 
примере:    6,3,3 , 4,2,4,2a b  , 
1 4 2 5 3 1 2 1
2 1 4 1 , 1 1 1 2
3 2 1 3 2 1 1 1
C D
                
. 
Формируем матрицы модифицированных стоимостей и пропу-
скных способностей. 
 
 
1 4 2 5
2 1 4 1
3 2 1 3
0
0
0
0
0 0 0
C
                                                                    
,
0 0 0 3 1 2 1 0 0
0 0 0 1 1 1 2 0 0
0 0 0 2 1 1 1 0 0
0 0 0 0 0 0 0 0 4
0 0 0 0 0 0 0 0 2
0 0 0 0 0 0 0 0 4
0 0 0 0 0 0 0 0 2
6 3 3 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
D
               
. 
 
 
Прочерки вместо элементов матрицы означают сколь угодно 
большое число (). 
36 
Предварительный этап. Так как 3 4
1 1
12i j
i j
a b
 
   , то имеют ме-
сто оба случая: 
1 1
m n
i j
i j
a b
 
   и 
1 1
m n
i j
i j
a b
 
  . Находим 11 223, 1,    
24 2,  33 1   и преобразовываем матрицы * * *, , .X C D  
 
 
*
0 0 0 3 0 0 0 3 0
0 0 0 0 1 0 2 3 0
0 0 0 0 0 1 0 1 0
3 0 0 0 0 0 0 0 3
0 1 0 0 0 0 0 0 1
0 0 1 0 0 0 0 0 1
0 2 0 0 0 0 0 0 2
3 3 1 0 0 0 0 0 0
0 0 0 3 1 1 2 0 0
X
                  
, 
 
 
*
4 2 5 0
2 4 0
3 2 3 0
1 0
1 0
1 0
1
0 0
0 0 0 0
C
                                                                   
, 
 
37 
*
0 0 0 0 1 2 1 3 0
0 0 0 1 0 1 0 3 0
0 0 0 2 1 0 1 1 0
3 0 0 0 0 0 0 0 1
0 1 0 0 0 0 0 0 1
0 0 1 0 0 0 0 0 3
0 2 0 0 0 0 0 0 0
3 0 2 0 0 0 0 0 0
0 0 0 3 1 1 2 0 0
D
               
. 
 
Итерация I. После осуществления тернарных операций получа-
ем * *,C R : 
*
1 0 2 2 2 2 0 2
0 0 2 2 2 2 0 2
0 1 2 2 2 2 0 2
1 1 1 0 0 0 1 0
11 1 1 0 0 0 1 0
1 1 1 0 0 0 1 0
1 1 1 1 1 1 1 1
0 1 0 2 2 2 2 2
1 1 0 0 0 0 1
C
                                     
 
 
*
1 8 8 6 8 6 6 8 6
8 2 8 4 8 8 4 8 4
8 5 3 5 5 8 5 8 5
1 9 1 4 9 9 9 1 9
2 2 2 9 5 9 9 2 9
3 9 3 9 9 6 9 3 9
2 2 2 2 2 2 7 2 2
1 3 3 3 3 1 3 8 3
4 5 6 4 5 6 7 4 9
R
                
. 
38 
*
89 2C  , с помощью матрицы *R  находим * * *89 39 593, 5, 9,r r r    
      8,3 , 3,5 5,9L   и изменяем матрицы * * *, ,X C D : 
 
*
0 0 0 3 0 0 0 3 0
0 0 0 0 1 0 2 3 0
0 0 0 0 1 1 0 2 0
3 0 0 0 0 0 0 0 3
0 1 1 0 0 0 0 0 2
0 0 1 0 0 0 0 0 1
0 2 0 0 0 0 0 0 2
3 3 2 0 0 0 0 0 0
0 0 0 3 2 1 2 0 0
X
                    
, 
 
*
4 2 5 0
2 4 0
3 3 0
1 0
1 2
1 0
1
0 0
0 0 0 0
C
                                                                      
, 
 
*
0 0 0 0 1 2 1 3 0
0 0 0 1 0 1 0 3 0
0 0 0 2 0 0 1 2 0
3 0 0 0 0 0 0 0 1
0 0 1 0 0 0 0 0 3
0 2 0 0 0 0 0 0 0
0 2 0 0 0 0 0 0 0
3 0 1 0 0 0 0 0 0
0 0 0 3 2 1 2 0 0
D
                
. 
39 
После осуществления над этими матрицами еще трех итераций 
получаем матрицы * *,C R . 
 
*
3 2 5 4 7 5 0 7
1 1 2 3 4 2 1 4
0 2 3 4 6 3 0 6
3 1 3 1 3 0 3 3
,2 1 2 1 3 1 2 3
3 1 3 0 0 0 3 0
2 1 2 1 2 3 2 3
0 3 2 5 4 7 5 7
3 1 3 0 0 0 0 3
C
                                      
 
 
*
1 5 5 5 5 5 7 8 5
4 2 4 4 4 6 4 4 6
8 7 3 4 8 7 7 8 7
3 3 3 4 3 3 3 3 3
3 2 3 2 5 2 3 3 2
9 9 9 9 9 6 9 9 9
2 2 2 2 2 2 7 2 2
1 1 1 1 1 1 1 8 1
4 5 4 4 5 6 7 4 9
R
               
. 
 
Так как *89 7C  , с помощью матрицы *R  определяем множест-
во индексов *89 191, 5,r r  59 29 692, 6, 67r r r   , т.е. 
          8,1 , 1,5 , 5,2 , 2,6 , 6,9L  . Находим 1   и вычисляем 
* *
81 15 51 52 25 26 62 696, 1, 1, 1, 0, 1, 1, 2.x x x x x x x x           
Новые матрицы * * *, , .X C D  
40 
*
0 0 0 3 1 2 0 6 0
0 0 0 0 0 1 2 3 0
0 0 0 1 1 1 0 3 0
3 0 1 0 0 0 0 0 4
1 0 1 0 0 0 0 0 2
2 1 1 0 0 0 0 0 4
0 2 0 0 0 0 0 0 2
6 3 3 0 0 0 0 0 0
0 0 0 4 2 4 2 0 0
X
                      
, 
 
*
5 0
2 0
3 3 0
1 3
4 2
2 4 1
1
C
                                                             
, 
 
*
0 0 0 0 0 0 1 6 0
0 0 0 1 1 0 0 3 0
0 0 0 1 0 0 1 3 0
3 0 1 0 0 0 0 0 0
1 0 1 0 0 0 0 0 0
2 1 1 0 0 0 0 0 0
0 2 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 4 2 4 2 0 0
D
               
. 
 
После осуществления тернарных операций над матрицей *C  по-
лучим *89C   , т.е. задача решена, оптимальное решение  
3 1 2 0
0 0 1 2
1 1 1 0
X
      
, при значении целевой функции min 23.z   
41 
ЗАДАЧИ ДЛЯ САМОСТОЯТЕЛЬНОГО РЕШЕНИЯ 
 
В а р и а н т ы 
 
1.  35,25,45a  ,  30, 25,10,20b  . 
 
2 7 5 8 15 20 10 10
7 3 8 2 , 10 5 5 6 .
7 11 8 6 10 10 20 10
C D
                
 
Ответ. 
15 16 0 4
10 5 4 6 , 490.
5 4 6 10
X z
      
 
 
2.  70,20,50a  ,  40, 30,30,25b  . 
 
2 7 6 4 10 20 20 25
7 4 6 8 , 20 10 10 15 .
6 9 11 5 15 5 5 30
C D
                
 
Ответ. Задача не имеет решения. Максимальный объем пере-
мещаемого продукта 120 ед., план 
10 20 20 20
10 5 5 0 , 695.
15 5 5 5
X z
      
 
 
3.  35,30,40a  ,  30, 45,15,30b  . 
 
4 8 7 5 5 5 20 10
8 6 5 10 , 15 10 20 5 .
4 7 6 2 15 35 10 20
C D
                
 
Ответ. 
5 5 15 10
15 10 0 5 , 620.
10 15 0 15
X z
      
 
 
4.  20,50,35a  ,  30, 10,40,10b  . 
42 
 
2 6 3 5 5 5 15 5
8 7 10 5 , 15 20 5 15 .
2 7 5 3 15 15 25 5
C D
                
 
Ответ. 
5 0 15 0
10 10 5 10 , 435.
15 0 20 0
X z
      
 
 
5.  40,25,35a  ,  20, 25,40,20b  . 
 
7 5 9 4 10 5 20 10
6 2 5 5 , 10 5 10 5 .
8 12 10 7 5 15 15 10
C D
                
 
Ответ. 
10 5 15 10
5 5 10 5 , 730.
5 10 15 5
X z
      
 
 
6.  30,70,40a  ,  35, 10, 55, 45b  . 
 
2 6 9 7 10 5 15 5
5 8 2 3 , 20 30 10 15 .
3 7 5 9 10 20 35 30
C D
                
 
Ответ. Задача не имеет решения. Максимальный объем пере-
мещаемого продукта 125 ед., план 
10 0 15 5
20 10 10 15 , 675.
5 0 30 5
X z
      
 
 
7.  30,65,25a  ,  30, 10,15,45b  . 
 
6 11 5 7 10 10 5 10
8 9 11 10 , 20 30 10 10 .
2 6 5 3 10 20 10 30
C D
                
 
43 
Ответ. 
10 0 5 10
20 10 10 10 , 690.
0 0 0 25
X z
      
 
 
8.  25,45,30a  ,  20, 40,10,25b  . 
 
4 5 9 3 10 10 15 10
5 2 5 6 , 10 10 20 10 .
8 9 5 4 20 25 15 10
C D
                
 
Ответ. 
10 10 0 5
10 10 10 10 , 505.
0 20 0 10
X z
      
 
 
9.  60,80,10a  ,  30, 55, 15, 30b  . 
 
8 8 9 5 10 10 30 20
7 2 3 8 , 25 15 20 20 .
5 8 6 7 10 30 20 10
C D
                
 
Ответ. Задача не имеет решения. Максимальный объем пере-
мещаемого продукта 110 ед., план 
5 10 0 20
25 15 15 10 , 630.
0 10 0 0
X z
      
 
 
10.  45,25,60a  ,  20, 20,35,25b  . 
 
5 9 4 8 15 10 20 10
9 2 7 5 , 20 10 10 5 .
5 7 6 4 25 10 10 15
C D
                
 
Ответ. 
15 0 20 5
0 10 5 5 , 445.
5 10 10 15
X z
      
 
 
 ЛИТЕРАТУРА 
 
1. Кузнецов, А. В. Математическое программирование / А. В. Куз-
нецов, Н. И. Холод. – Минск: Вышэйшая школа, 2000. 
2. Кузнецов, А. В. Руководство к решению задач по математи-
ческому программированию: учебное пособие / А. В. Кузнецов, 
Н. И. Холод, Л. С. Костевич. – Минск, 2001. – 448 с. 
3. Гольштейн, Е. Г. Задачи линейного программирования транс-
портного типа / Е. Г. Гольштейн, Д. Б. Юдин. – М.: Наука, 1969. 
  
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Учебное издание 
 
РЕШЕНИЕ ЗАДАЧ ОПТИМИЗАЦИИ 
ТРАНСПОРТНОГО ТИПА 
 
Методические указания и контрольные задания 
для студентов инженерных и инженерно-экономических 
специальностей 
 
Составитель  
КОРЗНИКОВ  Александр Дмитриевич 
 
 
Технический редактор  Д. А. Исаев 
 
 
Подписано в печать 05.03.2014. Формат 6084 1/16. Бумага офсетная. Ризография. 
Усл. печ. л. 2,56. Уч.-изд. л. 2,0. Тираж 100. Заказ 1007. 
Издатель и полиграфическое исполнение: Белорусский национальный технический университет. 
Свидетельство о государственной регистрации издателя, изготовителя, распространителя 
печатных изданий № 1/173 от 12.02.2014. Пр. Независимости, 65.  220013, г. Минск.