Тема 2. Основы линейного программирования

Вопросы:

1. Постановка одноиндексной задачи линейного программирования

2. Графический метод решения одноиндексных задач линейного программирования

3. Симплекс-метод решения задач линейного программирования

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

5. Построение первоначального опорного плана транспортной задачи методом северо-западного угла

6. Решение транспортной задачи методом потенциалов

1. Постановка одноиндексной задачи линейного программирования

Линейное программирование (ЛП) – раздел математического программирования, разрабатывающий теорию и численные методы решения задач нахождения экстремума (максимума или минимума) линейной функции многих переменных при наличии линейных ограничений, т.е. линейных равенств или неравенств, связывающих эти переменные. Кроме того вводится дополни­тельное ограничение - значения переменных должны быть неотрицательны, так как они представляют собой экономические показатели.

К задачам ЛП приводится широкий круг вопросов планирования экономических и технико-экономических процессов, где ставится задача поиска наилучшего (оптимального) решения. Само возникновение и развитие ЛП непосредственно связано с экономической проблематикой. В настоящее время ЛП является наиболее простым и лучше всего изученным разделом математического программирования.

Общая форма записи модели задачи ЛП может быть представлена следующим образом:

найти значения переменных Х₁, Х₂,…,Хn, максимизирущих (минимизирующих) значение целевой функции (ЦФ):

(2.1)

при ограничениях (условиях):

, i= 1,…,m₁ (m₁m) (2.2)

, i=m₁+1,…,m (2.3)

x_j 0, j=1,…,p (pn), (2.4)

где a_{i j}, в_i , с_j - заданные постоянные величины;

x_j - переменные.

Основной задачей ЛП называется задача, которая состоит в определении максимального (минимального) значения ЦФ (2.1) при выполнении условий (2.2) и (2.4).

Канонический задачей ЛП назначается задача, состоящая в определении максимального (минимального) значения ЦФ (2.1) при выполнении условий (2.3) и (2.4).

Совокупность чисел ^*= (x₁, x_2,…,x _n), удовлетворяющих ограничениям задачи называется допустимым решением (планом).

План ^*= (x₁,^* x₂^*_,…,.x _n^*), при котором ЦФ принимает максимальное (минимальное) значение называется оптимальным.

Любую задачу ЛП можно привести к каноническому виду, используя следующие правила:

а) максимизация целевой функции = c₁x₁+…+c_nx_n равносильна минимизации целевой функции - =-c₁x₁ -…-c_nx_n;

б) если некоторая переменная Х_k может принимать любые значения, а требуется, чтобы она была неотрицательная, ее можно привести к виду , где 0 и 0;

в) Ограничение – неравенство исходной задачи ЛП имеющее вид «≤» преобразуется в ограничение – равенство с добавлением к левой части дополнительной неотрицательной переменой. Ограничение – неравенство типа «≥» преобразуется в ограничение равенство путем вычитания из левой части дополнительной неотрицательной переменой. Если ограничения задачи отрицательной наличие или расход производственных ресурсов то числовое значение дополнительной переменной в оптимальном плане задачи равно объему неиспользованного ресурса.

Пример 2.1. Записать в форме канонической задачи линейного программирования следующую задачу:

f ( ) =3х₁ -2х₂ -5х₄+ х₅

Решение:

В соответствии с приведенным выше правилом (в) получим

f ( ) =3х₁ -2х₂ -5х₄+ х₅

2. Графический метод решения одноиндексных задач линейного программирования

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

Алгоритм графического метода:

1. Получить уравнения прямых путем замены в ограничениях задачи знаков неравенств на знаки точных равенств и построить это прямые.

2. Найти и заштриховать полуплоскости, определяемые и разрешаемые каждым из ограничений-неравенств задачи. Ограничения-равенства разрешают только те точки, которые лежат на соответствующей прямой.

Для этого необходимо подставить в конкретное неравенство координаты какой-либо точки, например, (0;0) и после этого проверить истинность полученного неравенства.

Если  неравенство истинное

то    заштриховать полуплоскость, содержащую точку (0;0);

иначе (неравенство ложное) заштриховать полуплоскость, не содержащую точку (0;0).

Поскольку x₁ и x₂ должны быть неотрицательными, то их допустимые значения всегда будут находится выше оси 0x₁ и правее оси 0x₂, т.е. в 1-м квадранте.

3. Определить область допустимых решений (ОДР) как часть плоскости, принадлежащую одновременно всем разрешенным областям, и заштриховать ее. ОДР всегда представляет собой выпуклую фигуру, т.е. обладающую следующим свойством: если две точки А и В принадлежат этой фигуре, то и весь отрезок АВ принадлежит ей.

4. Построить целевую прямую c₁x₁ + c₂x₂ = L, проходящую через ОДР. Для этого надо построить прямую, произвольно выбрав L (удобно использовать в качестве L число, кратное коэффициентам целевой функции).

Произвольный выбор L связан с тем, что, придавая L различные значения, мы будем получать различные прямые, параллельные друг другу. При этом будет изменяться лишь длина отрезка, отсекаемого прямой на оси 0x₂ (начальная ордината), а угловой коэффициент прямой, равный –c₁/c₂ будет оставаться постоянным (см. рис.2.1).

5. Построить вектор , который начинается в точке (0;0) и заканчивается в точке (c₁;c₂).

Вектор показывает направление возрастания значений ЦФ, а значит и значений L целевой прямой.

6. Передвигать целевую прямую

• в направлении вектора при поиске max ЦФ;

• или в направлении противоположном вектору при поиске min ЦФ.

В результате этого передвижения

• найти точку (или точки), в которой ЦФ принимает max (или min) значение;

• или установить, что ЦФ неограничена на множестве планов сверху или снизу.

Оптимальное решение не может находиться внутри ОДР, а только на ее границе, а именно, в последней вершине многоугольника, через которую пройдет целевая прямая, или на всей его стороне. Допустимое решение, лежащее в вершине ОДР, называется опорным решением (планом).

Рис.2.1 - Расположение целевой функции

7. Определить координаты точки максимума (минимума) ЦФ и вычислить значение ЦФ.

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

Пример 2.7. Решить графическим методом задачу, представленную в примере 2.2.

Решение:

1) Построим прямые ограничений, для чего вычислим координаты точек пересечения этих прямых с осями координат (рис.2.2).

(1) – (2) – (3) –

Прямая (4) проходит через точку параллельно оси .

2) Определим ОДР. Например, подставим точку (0;0) в исходное ограничение (3), получим , что является истинным неравенством, поэтому стрелкой (или штрихованием) обозначим полуплоскость, содержащую точку (0;0), т.е. расположенную правее и ниже прямой (3). Аналогично определим допустимые полуплоскости для остальных ограничений и укажем их стрелками у соответствующих прямых ограничений (см. рис.2.2).

3) После проведения штриховки допустимых полуплоскостей определяем, что ОДР - это многоугольник ABCDEF.

4)  Целевую прямую можно построить по уравнению

,

5) Строим вектор из точки (0;0) в точку (3;2). Если целевая прямая и вектор построены верно, то они будут перпендикулярны.

6) Точка Е – это последняя вершина многоугольника допустимых решений ABCDEF, через которую проходит целевая прямая, двигаясь по направлению вектора . Поэтому Е – это точка максимума ЦФ.

f(x)

Рис.2.2 - График решения задачи

7) Определим координаты точки Е из системы уравнений прямых ограничений (1) и (2)

,

т/сутки.

Максимальное значение ЦФ равно тыс. руб./сутки. Таким образом, наилучшим режимом работы фирмы является ежесуточное производство краски 1-го вида в объеме   т и краски 2-го вида в объеме  т. Доход от продажи красок составит тыс. руб. в сутки.

3. Симплекс-метод решения задач линейного программирования

Впервые симплексный метод был предложен американским ученым Дж. Данцингом в 1949 г., однако еще в 1939 г. идеи метода были разработаны российским математиком Л.В. Канторовичем.

Симплексный метод — это итерационный процесс, который начинается с одного решения и в поисках лучшего варианта дви­жется по угловым точкам области возможных решений до тех пор, пока не достигнет оптимального значения, в частности по угловым точкам многоугольника решений, полученного геометрическим ме­тодом.

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

1. Выберем т переменных, задающих допустимое пробное ре­шение, и исключим эти переменные из целевой функции.

2. Проверим, нельзя ли за счет одной из переменных, приравненной вначале к нулю, улучшить значение целевой функции, при­давая ей отличные от нуля (причем положительные) значения. Если это возможно, перейдем к третьему этапу, в противном случае пре­кратим вычисления.

3. Найдем предельное значение переменной, за счет которой можно улучшить значение целевой функции. Увеличение значения этой переменной допустимо до тех пор, пока одна из т переменных, вошедших в пробное решение, не обратится в нуль. Исключим из выражения для целевой функции только что упомянутую переменную и введем в пробное решение ту переменную, за счет которой результат может быть улучшен.

4. Разрешим систему m уравнений относительно переменной, вошедшей в новое пробное решение. Исключим эту переменную из выражения для целевой функции. Вернемся ко второму этапу.

Важно отметить, что при однозначном понимании данного предписания предложенный алгоритм действительно приводит к оптимальному решению для любой модели линейного программи­рования за конечное число итераций, если система ограничений за­дачи совместна.

Симплексный метод основан на последовательном переходе от одного опорного плана задачи линейного программирования к другому, при этом значение целевой функции изменяется.

Рассмотрим алгоритм симплексного метода на примере задачи планирования товарооборота.

Коммерческое предприятие реализует “n” товарных групп, располагая “m” ограниченными материально-денежными ресурсами в_i 0 (i= 1, 2, …..m). Известны расходы ресурсов каждого i–го вида на реализацию единицы товара по каждой группе, представленной в виде матрицы А=(а_ij), и прибыль “Cj”, получаемая предприятием от реализации единицы товара “j” группы. Надо определить объем и структуру товарооборота “х_j” (j = 1, 2, … ,n), при которых прибыль коммерческого предприятия была бы максимальной.

Пример 2.8. Коммерческое предприятие, располагающее материально-денежными ресурсами, реализует три группы товара А, В и С. Плановые нормативы затрат ресурсов на единицу товара, доход от его продажи, а также объем ресурсов заданы в следующей таблице 2.5.

Таблица 2.5

Затраты материально-денежных ресурсов на единицу товара

Виды материально-денежных ресурсов	Норма затрат ресурсов на единицу товара			Объем ресурсов (вi)
	группы А	группы В	группы С
Рабочее время продавцов, чел-ч	0,1	0,2	0,4	1 100
Площадь торговых залов, м2	0,05	0,02	0,02	120
Площадь складских помещений, м2	3	1	2	8 000
Доход, тыс. руб. (Сj)	3	5	4	mах

Определить плановый объем продажи товаров так, чтобы доход торгового предприятия был максимальный.

Переменные:

х₁ – количество товаров группы А, ед.

х₂ – количество товаров группы В, ед.

х₃ – количество товаров группы С, ед.

Целевая функция:

Максимальное значение целевой функции, тыс. руб.

f(х) = 3х₁+5х₂+4х₃ mах

Ограничения:

1. По использованию рабочего времени продавцов, чел-ч. 0,1х₁+0,2х₂+0,4х₃ 1100

2. По использованию площадей торговых залов, м² 0,05х₁+0,02х₂+0,02х₃ 120

3. По использованию площадей складских помещений, м² 3х₁+х₂+2х₃ 8000

4. Условие не отрицательности переменных х₁ 0, х₂ 0, х₃ 0.

Алгоритм симплексного метода включает следующие этапы:

1.Составление первого опорного плана

Система ограничений задачи, решаемой симплексным методом задана в виде неравенств смысла “ ” , правые части которых в_i 0. Перейдем от системы неравенств к системе уравнений путем введения неотрицательных дополнительных переменных х₄; х₅; х₆; которые образуют базис и называются базисными переменными и определяют объемы неиспользованных ресурсов:

0,1х₁+0,2х₂+0,4х₃ + х₄ = 1100

0,05х₁+0,02х₂+0,02х₃+х₅ = 120

3х₁+х₂+2х₃+х₆ = 8000

Матрица коэффициентов А=(а_ij) этой системы уравнений имеет вид:

А = 0,1	0,2	0,4	1	0	0
0,05	0,02	0,02	0	1	0
3	1	2	0	0	1

Решим систему уравнений относительно базисных переменных:

х ₄ = 1100 – (0,1х₁+0,2х₂+0,4х₃)

х₅ = 120 – (0,05х₁+0,02х₂+0,02х₃)

х₆ = 8000 – (3х₁+х₂+3х₃)

Функцию цели запишем в виде уравнения f(х) = 0 – (-3х₁ – 5х₂ – 4х₃). Полагая что основные переменные х₁=0 х₂=0 х₃=0, получим первый опорный план, х₄=в₁; х₅=в₂; х₆=в₃ f(x) =0; который заносим в симплексную таблицу 2.6. Она состоит из коэффициентов системы ограничений и свободных членов. Последняя строка таблицы называется индексной и заполняется коэффициентами функции цели, взятыми с противоположным знаком:

Таблица 2.6

Первый план симплексной таблицы

План	Базисные переменные	Свободные члены	Основн. перемен.			Допол. перем.			i
			х1	х2	х3	х6	х5	х6
I	х4	1100	0,1	0,2	0,4	1	0	0	5500
	х5	120	0,05	0,02	0,02	0	1	0	6000
	х6	8000	3	1	2	0	0	1	8000
Индексная строка	f(x)	0	-3	-5	-4	0	0	0

2. Проверка плана на оптимальность

Если все коэффициенты индексной строки симплексной таблицы при решении задачи на максимум неотрицательны ( 0), то план является оптимальным.

Если найдется хотя бы один коэффициент индексной строки меньше нуля, то план неоптимальный и его можно улучшить.

Первый опорный план, представленный в первой симплексной таблице неоптимальный, т.к. в индексной строке находятся отрицательные коэффициенты: -3; -5; -4.

Полагая что основные переменные х₁=0; х₂=0;х₃=0, а дополнительные переменные х₄=1100; х₅=120; х₆=800; f(x)=0. Следовательно, товары не продаются, а ресурсы не используются, доход равен нулю. В этом случае переходим к следующему этапу алгоритма.

2. Определение ведущих столбца и строки

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

Затем элементы столбца свободных членов симплексной таблицы делим на положительные элементы ведущего столбца. Результаты заносим в отдельный столбец( _i). При этом всегда _i 0. В других случаях ставится прочерк. Строка симплексной таблицы соответствующая минимальному значению _i, является ведущей. Она определяет переменную х_i, которая на следующей итерации выйдет из базиса и станет свободной.

Элемент симплексной таблицы, находящийся на пересечении ведущих столбцов, называют разрешающим и выделяют кружком.

За ведущий столбец выберем столбец, соответствующий переменной х_2, т.к. сравнивания по модулю [-5] >[-3]; [-4].

Вычислим значения _i по строкам и выберем наименование 1100/0,2 = 5500(min); 120/0,02=6000; 8000/1=8000; следовательно, строка х₄ является ведущей.

Разрешающий элемент равен 0,2 и находится на пересечении ведущего столбца и ведущей строки.

4. Построение нового плана.

Переход к новому плану осуществляется в результате пересчета симплексной таблицы методом Жордана-Гаусса. Сначала заменим переменные в базисе, т.е. вместо (х_i) (х₄) в базис войдет переменная (х_j) (х₂) соответствующая ведущему столбцу.

1. Разделим все элементы ведущей строки предыдущей симплексной таблицы на разрешающий элемент и результаты деления занесем в начальную строку следующей симплексной таблицы, т.е.

(х₂) 1100/0,2=5500; 0,1/0,2=0,5; 0,2/0,2=1;0,4/0,2=2;1/0,2=5.

2. Все остальные других строк определяются по формуле:

Новый элемент = соответствует коэффициент предыдущего плана – (коэффициент ведущего столбца предыдущей таблицы * коэффициент начальной строки нового плана): 120-0,02*5500=10

Выполняя последовательно все этапы алгоритма, составляем план 2 (таблица 2.7).

Таблица 2.7

Второй план симплексной таблицы

План	Базисные переменные	Свободные члены	Основн. перемен.			Допол. перем.			2
			х1	х2	х3	х4	х5	х6
II	х2	5500	0,5	1	2	5	0	0	11000
	х5	10	0,04	0	-0,02	-0,1	1	0	250
	х6	2500	2,5	0	0	-5	0	1	1000
Индексная строка	f(x2)	27 500	-0,5	0	6	25	0	0

Анализ второго плана:

План не оптимальный т.к. в индексной строке имеется отрицательный коэффициент (-0,5). Максимальный доход в размере 25.500 руб. торговое предприятие получит от продажи товаров второй группы В 5500 ед. (х₂). Среди базисных переменных находится дополнительные переменные х₅и х₆. Это указывает на то, что ресурсы второго вида (площадь торговых залов) недоиспользована на 10 м² и ресурсы третьего вида (площадь складских помещений) недоиспользованы на 2500 м² .

На третьей итерации получаем план 3 (таблица 2.8), который является оптимальным т.к. все коэффициенты в индексной строке 0.

Анализ третьего плана:

Необходимо продавать товаров первой группы А 250 ед., а второй группы В 5375 ед. При этом торговое предприятие получает максимальный доход в размере 27625 тыс. руб. Товары группы С не реализуются.

В оптимальном плане среди базисных переменных находится дополнительная переменная х₆. Это указывает, что ресурсы третьего вида (площадь складских помещений) недоиспользована на 1875 м², т.к. переменная х₆ была введена в третье ограничение задачи, характеризующее собой использование складских помещений этого ресурса.

Таблица 2.8

Третий план симплексной таблицы

План	Базисные переменные	Свободные члены	Основн. перемен.			Допол. перем.			2
			х1	х2	х3	х4	х5	х6
III	х2	5375	0	1	2.25	6,25	12,5	0
	х1	1250	1	0	0,5	-2,5	25	0
	х6	1875	0	0	1,25	1,25	62,5	1
Индексная строка	F(x3)	27 625	0	0	5,75	23,75	12,5	0

При решении задачи ЛП на min ЦФ признаком оптимальности плана являются отрицательные значения всех коэффициентов индексной строки. Однако перед решением задачи можно перейти от min ЦФ к ее max, путем замены знаков коэффициентов ЦФ на противоположные.

Если в ведущем столбце все коэффициенты меньше или равны 0, то ЦФ неограниченна на множестве допустимых планов, т.е. f(x)→∞ и задача не имеет решения.

Если в столбце i содержится два или несколько одинаковых наименьших значения, то новый опорный план будет вырожденным и может привести к зацикливанию в решении. В данном случае, для выбора ведущей строки используют метод Креко.

Если ограничения задачи записаны в виде неравенств «≥» или строгих равенств, то вводят искусственные переменные Y_i =0. Полученный базис называют искусственным, а метод решения – методом искусственного базиса.

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

Примером двухиндексной задачи линейного программирования служит транспортная задача. Ее общая постановка состоит в определении оптимального плана перевозок некоторого однородного груза из пунктов отправления (производства) в пунктов назначения (потребления) . При этом в качестве критерия оптимальности обычно берется либо минимальная стоимость перевозок всего груза, либо минимальное время его доставки. Рассмотрим транспортную задачу, в качестве критерия оптимальности которой взята минимальная стоимость перевозок всего груза. Обозначим через тарифы перевозки единицы груза из -го пункта отправления в -й пункт назначения, через - запасы груза в -м пункте отправления, через - потребности в грузе в -м пункте назначения, а через - количество единиц груза, перевозимого из -го пункта отправления в -й пункт назначения. Обычно исходные данные транспортной задачи записывают в виде таблицы.

Таблица 2.9

Общий вид транспортной матрицы

Пункты производства	Пункты потребления				Объемы производства
Объемы потребителя

Составим математическую модель задачи.

(2.5)

при ограничениях

(2.6)

(2.7)

(2.8)

План , при котором функция (2.5) принимает своё минимальное значение, называется оптимальным планом транспортной задачи.

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

. (2.9)

Модель такой транспортной задачи называется закрытой, или замкнутой, или сбалансированной, в противном случае модель называется открытой.

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

Число переменных в транспортной задаче с пунктами отправления и пунктами назначения равно , а число уравнений в системе (2)-(4) - . Так как мы предполагаем выполнение условия (5), то число линейно независимых уравнений равно . Следовательно, опорный план может иметь не более отличных от нуля неизвестных. Если в опорном плане число отличных от нуля компонент равно в точности , то план называется невырожденным, а если меньше - то вырожденным.

Для определения первоначального опорного плана существует несколько методов: метод северо-западного угла (диагональный метод), метод наименьшей стоимости (минимального элемента), метод двойного предпочтения и метод аппроксимации Фогеля.

Кратко рассмотрим каждый из них.

1.Метод северо-западного угла. При нахождении опорного плана на каждом шаге рассматривают первый из оставшихся пунктов отправления и первый из оставшихся пунктов назначения. Заполнение клеток таблицы условий начинается с левой верхней клетки для неизвестного («северо-западный угол») и заканчивается клеткой для неизвестного , т.е. как бы по диагонали таблицы.

2. Метод наименьшей стоимости. Суть метода заключается в том, что из всей таблицы стоимостей выбирают наименьшую и в клетку , которая ей соответствует, помещают меньшее из чисел и , затем из рассмотрения исключают либо строку, соответствующую поставщику, запасы которого полностью израсходованы, либо столбец, соответствующий потребителю, потребности которого полностью удовлетворены, либо и строку и столбец, если израсходованы запасы поставщика и удовлетворены потребности потребителя. Из оставшейся части таблицы стоимостей снова выбирают наименьшую стоимость, и процесс размещения запасов продолжают, пока все запасы не будут распределены, а потребности удовлетворены.

3. Метод двойного предпочтения. Суть метода заключается в следующем. В каждом столбце отмечают знаком «√» клетку с наименьшей стоимостью. Затем то же проделывают в каждой строке. В результате некоторые клетки имеют отметку «√√». В них находится минимальная стоимость, как по столбцу, так и по строке. В эти клетки помещают максимально возможные объемы перевозок, каждый раз исключая из рассмотрения соответствующие столбцы или строки. Затем распределяют перевозки по клеткам, отмеченным знаком «√». В оставшейся части таблицы перевозки распределяют по наименьшей стоимости.

4. Метод аппроксимации Фогеля. При определении опорного плана данным методом на каждой итерации по всем столбцам и всем строкам находят разность между двумя записанными в них минимальными тарифами. Эти разности заносят в специально отведенных для этого строке и столбце в таблице условий задачи. Среди указанных разностей выбирают максимальную. В строке (или столбце), который данная разность соответствует, определяют минимальный тариф. Клетку, в которой он записан, заполняют на данной итерации.

С помощью рассмотренных методов построения первоначального опорного плана можно получить вырожденный или невырожденный опор­ный план. Построенный план транспортной задачи как задачи линейного программирования можно было бы довести до оптимального с помощью симплексного метода. Однако из-за громоздкости симплексных таблиц, со­держащих тп неизвестных, и большого объема вычислительных работ для получения оптимального плана используют более простые методы. Наиболее часто применяются метод потенциалов (модифицированный распредели­тельный метод).

Метод потенциалов позволяет определить отправляясь от некоторого опорного плана перевозок построить решение транспортной задачи за конечное число шагов (итераций).

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

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

если , (2.10)

если . (2.11)

числа и называются потенциалами пунктов отправления и назначения соответственно.

Сформулированная теорема позволяет построить алгоритм нахождения решения транспортной задачи. Он состоит в следующем. Пусть одним из рассмотренных выше методов найден опорный план. Для этого плана, в ко­тором базисных клеток, можно определить потенциалы и так, чтобы выполнялось условие (2.10). Поскольку система (2.6)-(2.8) содержит уравнений и неизвестных, то одну из них можно задать произвольно (например, приравнять к нулю). После этого из уравнений (2.10) определяются остальные потенциалы и для каждой из свободных клеток вы­числяются величины . Если оказалось, что , то план оп­тимален. Если же хотя бы в одной свободной клетке , то план не яв­ляется оптимальным и может быть улучшен путем переноса по циклу, соот­ветствующему данной свободной клетке.

Циклом в таблице условий транспортной задачи, называется ломаная линия, вершины которой расположены в занятых клетках таблицы, а звенья - вдоль строк и столбцов, причем в каждой вершине цикла встречается ровно два звена, одно из которых находится в строке, а другое - в столбце. Если ломанная линия, образующая цикл, пересекается, то точки самопересечения не являются вершинами.

Процесс улучшения плана продолжается до тех пор, пока не будут выполнены условия если (2.11).

Пример 2.9. На четыре базы A₁, A₂, A₃, A₄ поступил однородный груз в следующем количестве: а₁ тонн - на базу А₁, а₂ тонн - на базу А₂, а₃ тонн - на базу А₃, а₄ тонн - на базу А₄. Полученный груз требуется перевезти в пять пунктов: b₁ тонн - на базу B₁, b₂ тонн - на базу B₂, b₃ тонн - на базу B₃, b₄ тонн - на базу B₄, b₅ тонн - на базу B₅. Расстояния между пунктами назначений указаны в матрице расстояний.

Таблица 2.9

Транспортная матрица примера 2.9

Пункты отправления	Пункты назначения					Запасы
	B1	B2	B3	B4	B5
A1	30	24	11	12	25	21
A2	26	4	29	20	24	19
A3	27	14	14	10	18	15
A4	6	14	28	8	2	25
Потребности	15	15	15	15	20

Стоимость перевозок пропорциональна количеству груза и расстоянию, на которое этот груз перевозится. Спланировать перевозки так, чтобы их общая стоимость была минимальной.

Решение. Проверим сбалансированность транспортной задачи, для этого необходимо чтобы

,    .

1. Решим задачу методом северо-западного угла.

Процесс получения плана можно оформить в виде таблицы 2.10.

Таблица 2.10

Распределение перевозок по методу северо-западного угла

Пункты отправления	B1	B2	B3	B4	B5	Запасы
A1	15	6	―	―	―	21
A2	―	9	10	―	―	19
A3	―	―	5	10	―	15
A4	―	―	―	5	20	25
Потребности	15	15	15	15	20

Получен следующий план:

	15	6	0	0	0
X0=	0	9	10	0	0
	0	0	5	10	0
	0	0	0	5	20

Данный план невырожденный.

F(X₀)=15·30+6·24+9·4+10·29+5·14+10·10+5·8+20·2=1170.

2. Метод наименьшей стоимости реализован в таблице 2.11.

Таблица 2.11

Распределение перевозок по методу наименьшей стоимости

Пункты отправления	B1		B2		B3		B4		B5		Запасы
A1	6	30	×	24	15	11	×	12	×	25	21
A2	4	26	15	4	×	29	×	20	×	24	19
A3	×	27	×	14	×	14	15	10	×	18	15
A4	5	6	×	14	×	28	×	8	20	2	25
Потребности	15		15		15		15		20

Получили вырожденный опорный план

	6	0	15	0	0
X0=	4	15	0	0	0
	0	0	0	15	0
	5	0	0	0	20

F(X₀)=6·30+15·11+4·26+15·4+15·10+5·6+20·2=729.

3. Воспользуемся методом двойного предпочтения (таблица 2.12).

Таблица 2.12

Распределение перевозок по методу двойного предпочтения

Пункты отправления	B1		B2		B3		B4		B5		Запасы
A1	6	30	×	24	15	11	×	12	×	25	21
A2	4	26	15	4	×	29	×	20	×	24	19
A3	×	27	×	14	×	14	15	10	×	18	15
A4	5	6	×	14	×	28	×	8	20	2	25
Потребности	15		15		15		15		20

Получили вырожденный опорный план

	6	0	15	0	0
X0=	4	15	0	0	0
	0	0	0	15	0
	5	0	0	0	20

F(X₀)=6·30+15·11+4·26+15·4+15·10+5·6+20·2=729.

4. Применим метод аппроксимации Фогеля (2.13).

Таблица 2.13

Распределение перевозок по методу аппроксимации Фогеля

Пункты отправления	B1		B2		B3		B4		B5		Запасы	Столбец-разность
A1	×	30	×	24	15	11	6	12	×	25	21	1		1		1			1	1	1	1
A2	×	26	15	4	×	29	4	20	×	24	19	16		16		4			4	9	к	к
A3	×	27	×	14	×	14	5	10	10	18	15	4		4		4			4	4	4	к
A4	15	6	×	14	×	28	×	8	10	2	25	4		6		6			к	к	к	к
потребности	15		15		15		15		20
строка-разность	20		10		3		2		16
	к		10		3		2		16
	к		к		3		2		16
	к		к		3		2		6
	к		к		3		2		к
	к		к		3		2		к
	к		к		к		к		к

Получили невырожденный опорный план

	0	0	15	6	0
X0=	0	15	0	4	0
	0	0	0	5	10
	15	0	0	0	10

F(X₀)=15·6+15·4+15·11+5·10+4·20+6·12+10·18+10·2=717.

5. Для проверки оптимальности плана используем метод потенциалов. В качестве примера возьмем опорный план, полученный методом двойного предпочтения.

Так как взятый нами план является вырожденным, то вводим ε - некоторое число близкое к 0.

 

 

 

 

 

 

Составим систему уравнений:

u1

+

v1

=

30

Пусть

u1

=

0

v1

=

30

u1

+

v2

=

8

<

c12

=

24

u1

+

v3

=

11

u2

=

-4

v2

=

8

u1

+

v4

=

24

>

c14

=

12

u2

+

v1

=

26

u3

=

-14

v3

=

11

u1

+

v5

=

26

>

c15

=

25

u2

+

v2

=

4

u4

=

-24

v4

=

24

u2

+

v3

=

7

<

c23

=

29

u2

+

v4

=

20

v5

=

26

u2

+

v5

=

22

<

c25

=

24

u3

+

v4

=

10

u3

+

v1

=

16

<

c31

=

27

u4

+

v1

=

6

u3

+

v2

=

-6

<

c32

=

14

u4

+

v5

=

2

u3

+

v3

=

3

<

c33

=

14

u3

+

v5

=

12

<

c35

=

18

u4

+

v2

=

-16

<

c42

=

14

u4

+

v3

=

-13

<

c43

=

28

u4

+

v4

=

0

<

c44

=

8

Так как существуют суммы больше c_ij, то план не оптимален. Введем в базис переменную (1,4) (так как разность здесь максимальна).

u1

+

v1

=

30

Пусть

u1

=

0

v1

=

30

u1

+

v5

=

26

>

c15

=

25

u1

+

v3

=

11

u2

=

-4

v2

=

8

u2

+

v4

=

8

<

c24

=

20

u1

+

v4

=

12

u3

=

-2

v3

=

11

u3

+

v1

=

28

>

c31

=

27

u2

+

v1

=

26

u4

=

-24

v4

=

12

u3

+

v2

=

6

<

c32

=

14

u2

+

v2

=

4

v5

=

26

u3

+

v3

=

9

<

c33

=

14

u3

+

v4

=

10

u3

+

v5

=

24

>

c35

=

18

u4

+

v1

=

6

u4

+

v4

=

-12

<

c44

=

8

u4

+

v5

=

2

Так как существуют суммы больше c_ij, то план не оптимален. Введем в базис переменную (3,5) (так как разность здесь максимальна).

F(X₁)=6·30-30ε+15·11+12ε+4·26-26ε+15·4+15·10+5·6+20·2=729-46ε.

u1

+

v3

=

11

Пусть

u1

=

0

v1

=

24

u1

+

v1

=

24

<

c11

=

30

u1

+

v4

=

12

u2

=

2

v2

=

2

u1

+

v2

=

12

<

c12

=

24

u2

+

v1

=

26

u3

=

-2

v3

=

11

u1

+

v5

=

20

<

c15

=

25

u2

+

v2

=

4

u4

=

-18

v4

=

12

u2

+

v3

=

13

<

c23

=

29

u3

+

v4

=

10

v5

=

20

u2

+

v4

=

14

<

c24

=

20

u3

+

v5

=

18

u2

+

v5

=

22

<

c25

=

24

u4

+

v1

=

6

u3

+

v1

=

22

<

c31

=

27

u4

+

v5

=

2

u3

+

v2

=

0

<

c32

=

14

u4

+

v2

=

-16

<

c42

=

14

u4

+

v3

=

-7

<

c43

=

28

u4

+

v4

=

-6

<

c44

=

8

Так как все суммы больше c_ij, то план оптимален. Число ε близко к 0, следовательно план примет вид

F(X)=15·11+6·12+4·26+4·15+9·10+6·18+11·6+2·14=165+72+104+60+90+

+108+28+66=693.