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

Основные понятия, определения и теоремы линейного программирования. Свойства решений задач ЛП и их графическая интерпретация. Пример решения задачи линейного программирования тремя способами: графическим, методом перебора вершин и симплексным методом. Пример решения транспортной задачи методом потенциалов.

Задача линейного программирования

Линейное программирование (ЛП)

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

Общая задача линейного программирования

– это задача на отыскание экстремума линейной функции с линейной системой ограничений.

Переменные задачи часто записывают в виде n-мерного вектора:
X = (x₁ ,  x₂ ,  . . . ,  x_n ) .

Линейная функция (1.1) называется целевой функцией. В задаче нужно найти такие значения переменных x₁ ,  x₂ ,  . . . ,  x_n , которые удовлетворяют системе ограничений (1.2) – (1.3), и при которых целевая функция F имеет наибольшее (или наименьшее) значение.

Система ограничений (1.2) может состоять из равенств
a_i1 x₁  + a_i2 x₂  + ⋅ ⋅ ⋅ + a_in x_n  = b_i ,
и неравенств обоих знаков:
a_i1 x₁  + a_i2 x₂  + ⋅ ⋅ ⋅ + a_in x_n  ≤ b_i , или
a_i1 x₁  + a_i2 x₂  + ⋅ ⋅ ⋅ + a_in x_n  ≥ b_i .

В системе ограничений особо выделяют ограничения, связанные с не отрицательностью некоторых переменных (1.3), которые являются следствием физических свойств величин, описываемых этими переменными.

Допустимое решение (план)

задачи линейного программирования – это такие значения переменных x₁ ,  x₂ ,  . . . ,  x_n , которые удовлетворяют системе ограничений (1.2) и условиям не отрицательности (1.3). Допустимое решение также называют планом.

Область допустимых решений (ОДР)

– это множество всех допустимых решений.

Оптимальное решение (оптимальный план)

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

Различные формы задач ЛП

Каноническая форма задачи линейного программирования

– это общая задача линейного программирования, в которой система ограничений состоит из равенств и условий не отрицательности для всех переменных:
            F = c₁ x₁  + c₂ x₂  + ⋅ ⋅ ⋅ + c_n x_n  → max (min )

(1.4)  

{ 

a11 x1  + a12 x2  + ⋅ ⋅ ⋅ + a1n xn	= b1
a21 x1  + a22 x2  + ⋅ ⋅ ⋅ + a2n xn	= b2
............................	....
am1 x1  + am2 x2  + ⋅ ⋅ ⋅ + amn xn	= bm

 

            x_j  ≥ 0,  j = 1,  2,  . . . ,  n .

Симметричная форма задачи линейного программирования

– это общая задача линейного программирования, в которой система ограничений состоит из неравенств одного знака и условий не отрицательности для всех переменных. Она имеет один из следующих двух видов:
            F = c₁ x₁  + c₂ x₂  + ⋅ ⋅ ⋅ + c_n x_n  → max

(1.5)  

{ 

a11 x1  + a12 x2  + ⋅ ⋅ ⋅ + a1n xn	≤ b1
a21 x1  + a22 x2  + ⋅ ⋅ ⋅ + a2n xn	≤ b2
............................	....
am1 x1  + am2 x2  + ⋅ ⋅ ⋅ + amn xn	≤ bm

 

            x_j  ≥ 0,  j = 1,  2,  . . . ,  n .
Или
            F = c₁ x₁  + c₂ x₂  + ⋅ ⋅ ⋅ + c_n x_n  → min

(1.6)  

{ 

a11 x1  + a12 x2  + ⋅ ⋅ ⋅ + a1n xn	≥ b1
a21 x1  + a22 x2  + ⋅ ⋅ ⋅ + a2n xn	≥ b2
............................	....
am1 x1  + am2 x2  + ⋅ ⋅ ⋅ + amn xn	≥ bm

 

            x_j  ≥ 0,  j = 1,  2,  . . . ,  n .

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

Дополнительная переменная (вспомогательная переменная)

– это переменная, которая вводится для преобразования неравенства в равенство. Дополнительную переменную также называют вспомогательной переменной. Например, неравенство
a_i,1 x₁  + a_i,2 x₂  + ⋅ ⋅ ⋅ + a_i,n x_n  ≤ b_i
переводится в равенство, введением дополнительной неотрицательной переменной x_n + 1  ≥ 0 :
a_i,1 x₁  + a_i,2 x₂  + ⋅ ⋅ ⋅ + a_i,n x_n  + x_n + 1  = b_i .

Графический метод решения задач

Свойства решений задач линейного программирования (ЛП) наглядно демонстрирует графический метод решения.

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

Сначала проводим оси x₁ ,  x₂ системы координат, и построим область допустимых решений (ОДР), которая определяется системой неравенств (2.2) и условиями не отрицательности переменных (2.3). Для построения ОДР, строим прямые, проходящие через границы неравенств:
– x₁  + 3x₂  = 12;  2x₁  – 3x₂  = 4;  3x₁  + 2x₂  = 19 .
С одной стороны каждой из построенных прямых соответствующее неравенство выполняется, а с другой стороны – нет. Поэтому ОДР ограничена этими прямыми. Также ОДР может быть ограничена осями координат, в силу неравенств x₁  ≥ 0,  x₂  ≥ 0 . Замечаем, что точка x₁  = 3,  x₂  = 3 удовлетворяет всем неравенствам (2.2)  и  (2.3). Поэтому она принадлежит ОДР. Заштриховываем область по границам прямых и осям координат, чтобы в нее вошла точка x₁  = 3,  x₂  = 3 . Получаем, что ОДР является множеством точек внутри многоугольника OABCD вместе с его границей.

Теперь рассмотрим целевую функцию (2.1). Построим ее линию уровня, приравняв F к любому значению, например F = 6 :
(2.4)   F = 2x₁  + x₂  = 6 .
Строим прямую 2x₁  + x₂  = 6 . С левой стороны от этой прямой F < 6 . С правой стороны, F > 6 . И чем больше мы удаляемся вправо и вверх, тем больше значение целевой функции F . Проводим прямую, параллельную прямой (2.4), так, чтобы она была максимально удалена в сторону увеличения значений F , то есть вправо, и при этом проходила хотя бы через одну точку ОДР. Такая прямая проходит через точку B с координатами (5,  2 ) . Это точка имеет наибольшее значение F среди всех точек ОДР. Поэтому x₁  = 5,  x₂  = 2 является оптимальным планом с максимальным значением целевой функции:
F_max  = 2x₁  + x₂  = 2 ⋅ 5 +  ⋅ 2 = 12 .

Ответ

Решение задачи: F_max  = 12,  x₁  = 5,  x₂  = 2 .

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

Свойства решений задач ЛП

Графический метод иллюстрирует основные свойства решений задач ЛП. Мы увидели, что поскольку ОДР ограничена конечным числом прямых, то она является выпуклым многоугольником. Далее, целевая функция не может иметь экстремума во внутренней точке ОДР, а достигает экстремума только на границе. Причем экстремум достигается в одной из вершин многоугольника ОДР. Если взять целевую функцию F = 3x₁  + 2x₂ , то экстремум будет на отрезке BC . То есть экстремум может достигаться в двух вершинах, и во всех точках отрезка между ними.

Эти свойства имеют место и в более общем случае, когда число переменных больше двух. Только вместо плоскостей будут гиперплоскости, а вместо многоугольников – многогранники. Так, если рассмотреть задачу ЛП в симметричной форме ⇑, то ОДР является выпуклым многогранником, ограниченным гиперплоскостями a_i1 x₁  + a_i2 x₂  + ⋅ ⋅ ⋅ + a_in x_n  = b_i и x_j  = 0 . Целевая функция может достигать экстремум только на границе ОДР. При этом экстремум достигается обязательно на одной из вершин многогранника ОДР. Если экстремум достигается на нескольких вершинах, то оптимальными планами являются также все точки выпуклого многогранника, построенного на этих вершинах.

Далее приводим более строгую трактовку этих рассуждений.

Выпуклое множество

Возьмем две произвольные точки, принадлежащие некоторому множеству. Если все точки отрезка, соединяющего эти точки, принадлежат этому множеству, то такое множество называется выпуклым.

Угловая (крайняя) точка выпуклого множества

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

Опорный план

– это план (допустимое решение), который является угловой точкой (вершиной многогранника) области допустимых решений.

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

Выпуклая линейная комбинация точек

M₁ ,  M₂ ,  . . . ,  M_k – это множество точек M , векторы которых, относительно начала системы координат, определяются по формуле:
^→M = ^kΣ_i = 1 λ_i ^→M_i , где λ_j  ≥ 0,  j = 1 ÷ k;  ^kΣ_i = 1 λ_i  = 1 .

Для двух точек, выпуклая линейная комбинация M₁ и M₂ является отрезком с концами M₁ и M₂ . Для трех точек, если M₁ ,  M₂ и M₃ не лежат на одной прямой, выпуклая линейная комбинация этих точек является треугольником с вершинами M₁ ,  M₂ и M₃ . Если же эти точки лежат на одной прямой, то их выпуклая линейная комбинация является отрезком, концы которого совпадают с двумя из этих точек. При этом одна из точек будет внутренней точкой отрезка.

Задачи линейного программирования в канонической форме

Рассмотрим задачу линейного программирования, записанную в канонической форме ⇑. В произвольном случае, не все строки матрицы коэффициентов a_ij , могут быть линейно независимыми. Пусть r – ранг матрицы коэффициентов, то есть число линейно независимых строк. Это означает, что линейными преобразованиями, систему уравнений (1.4) можно привести к эквивалентной системе, содержащей r линейно независимых строк.

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

Для задачи в канонической форме это сводится к тому, что мы должны добавить к системе уравнений еще n – r уравнений вида x_j  = 0 . Полученное решение такой системы уравнений является опорным планом.

Свободные переменные

– это переменные задачи ЛП в канонической форме, на которые, в рассматриваемом опорном плане, наложено условие их равенства нулю: x_j  = 0 .

Базисные переменные

– это переменные задачи ЛП в канонической форме, которые в рассматриваемом опорном плане, не являются свободными. Они имеют неотрицательные значения, которые определяются из решения системы уравнений (1.4).

Невырожденный план (невырожденное решение)

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

Вырожденный план (вырожденное решение)

– это опорный план, в котором есть одна или несколько базисных переменных, равных нулю.

Векторы условий

– это n векторов, которые являются столбцами матрицы коэффициентов системы (1.4).

Вектор ограничений

– это вектор, который являются столбцом правой части матрицы коэффициентов системы (1.4). То есть это вектор (b₁ , b₂ , . . ., b_m ) .

Базис

– это r векторов, которые являются столбцами матрицы коэффициентов системы (1.4) при базисных переменных. То есть базис – это векторы условий при базисных переменных.

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

Методы решения задач

Графический метод

Решение задачи графическим методом мы рассмотрели выше ⇑. Он применим, если в задаче имеются две переменные. Также он применим, если имеется n переменных и система ограничений содержит n – 2 линейно независимых уравнения. Тогда, решая систему ограничений, мы можем выразить n – 2 переменных через x₁ и x₂ , или через две другие переменные. В результате получим задачу с двумя переменными, которую можно решить графическим методом.

Метод перебора вершин

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

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

Решение задачи

Решим задачу (2.1) – (2.3) методом перебора вершин. При этом мы можем использовать результаты, полученные при решении графическим методом ⇑. Там мы нашли, что ОДЗ является многоугольником OABCD . И мы нашли координаты его вершин. Для каждой вершины мы можем вычислить значение целевой функции (2.1). Сравнивая их, можно определить наибольшее значение.

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

В этой задаче n = 5 переменных. Система ограничений (П.2) содержит 3 линейно независимых уравнения. Поэтому в произвольной угловой точке имеется 5 – 3 = 2 свободные переменные, и 3 базисные. Перебираем все возможные сочетания свободных переменных, приравниваем их к нулю, и, решая систему (П.2), определяем значения базисных переменных.

1) В качестве свободных переменных возьмем x₁ и x₂ . Приравниваем их к нулю, и подставляем в (П.2); получаем: x₃  = 12;  x₄  = 4;  x₅  = 19 . Поскольку все x_j  ≥ 0 , то мы нашли угловую точку ОДР или, что тоже самое, вершину многогранника ОДР: x₁  = 0;  x₂  = 0;  x₃  = 12;  x₄  = 4;  x₅  = 19 . На построении ⇑ ей соответствует точка O .

3) Возьмем свободные переменные x₁ и x₄ . Подставляем их нулевые значения в (П.2). Решая систему, получаем: x₁  = 0;  x₂  = – 4 / 3;  x₃  = 16;  x₄  = 0;  x₅  = 65 / 3 . Поскольку x₂  < 0 , то эта точка не принадлежит ОДЗ. Поэтому она не может быть планом задачи. Отбрасываем ее. На рисунке ⇑ ей соответствует точка пересечения прямой AB с осью x₂ .

4) Свободные переменные x₁  = x₅  = 0 . Подставляя их нулевые значения в (П.2), находим: x₁  = 0;  x₂  = 19 / 2;  x₃  = – 7;  x₄  = 65 / 2;  x₅  = 0 . Здесь также есть отрицательная переменная x₃  < – 7 . Эта точка также не принадлежит ОДЗ. Отбрасываем ее. Это точка пересечения прямой BC с осью x₂ .

5) Свободные переменные x₂  = x₃  = 0 . Подставляя в (П.2), находим решение системы: x₁  = – 12;  x₂  = 0;  x₃  = 0;  x₄  = 28;  x₅  = 55 . Поскольку x₁  < 0 , то и эта точка не принадлежит ОДЗ. Отбрасываем ее. Это точка пересечения прямой DC с осью x₁ .

6) x₂  = x₄  = 0 . Решение системы: x₁  = 2;  x₂  = 0;  x₃  = 14;  x₄  = 0;  x₅  = 13 . Поскольку все x_j  ≥ 0 , то мы нашли угловую точку, которой на построении ⇑ соответствует точка A .

7) x₂  = x₅  = 0 . Решение системы: x₁  = 19 / 3;  x₂  = 0;  x₃  = 55 / 3;  x₄  = – 26 / 3;  x₅  = 0 . x₄  < 0 , точка не принадлежит ОДЗ. На рисунке ей соответствует точка пересечения прямой BC с осью x₁ .

8) x₃  = x₄  = 0 . Решение системы: x₁  = 16;  x₂  = 28 / 3;  x₃  = 0;  x₄  = 0;  x₅  = – 143 / 3 . x₅  < 0 , точка не принадлежит ОДЗ. Это точка пересечения прямых AB и DC.

9) x₃  = x₅  = 0 . Решение системы: x₁  = 3;  x₂  = 5;  x₃  = 0;  x₄  = 13;  x₅  = 0 . Все x_j  ≥ 0 . Это угловая точка – точка C .

10) x₄  = x₅  = 0 . Решение системы: x₁  = 5;  x₂  = 2;  x₃  = 11;  x₄  = 0;  x₅  = 0 . Все x_j  ≥ 0 . Это угловая точка. На построении ⇑ ей соответствует точка B .

Итак, мы нашли все угловые точки ОДР. Находим в них значения целевой функции.
O(0,  0,  12,  4,  19 ),  F_O  = 2 ⋅ x₁  + 1 ⋅ x₂  = 2 ⋅ 0 + 1 ⋅ 0 = 0 ;
D(0,  4,  0,  16,  11 ),  F_D  = 2 ⋅ x₁  + 1 ⋅ x₂  = 2 ⋅ 0 + 1 ⋅ 4 = 4 ;
A(2,  0,  14,  0,  13 ),  F_A  = 2 ⋅ x₁  + 1 ⋅ x₂  = 2 ⋅ 2 + 1 ⋅ 0 = 4 ;
C(3,  5,  0,  13,  0 ),  F_C  = 2 ⋅ x₁  + 1 ⋅ x₂  = 2 ⋅ 3 + 1 ⋅ 5 = 11 ;
B(5,  2,  11,  0,  0 ),  F_B  = 2 ⋅ x₁  + 1 ⋅ x₂  = 2 ⋅ 5 + 1 ⋅ 2 = 12 .

Ответ

Наибольшим является значение целевой функции F = 12 в точке B . Решение задачи: F_max  = 12,  x₁  = 5,  x₂  = 2 .

Симплексный метод

Симплексный метод

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

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

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

Решение задачи

2. Теперь попробуем найти смежную вершину многогранника ОДР, в которой значение целевой функции было бы больше F_O . Для этого нужно переместиться из вершины O вдоль одного из ребра многогранника на небольшое расстояние по направлению к смежной вершине и посмотреть, увеличилась ли при этом целевая функция?

2.3. Итак, мы нашли, что если переменной x₁ или x₂ присвоить положительное значение, то целевая функция увеличится. Это означает, что первый опорный план (0,  0,  0,  0,  0 ) не оптимален. Целевую функцию можно увеличить введением в базис x₁ или x₂ . При увеличении x₁ на единицу, целевая функция увеличится на 2 ⋅ Δx₁  = 2 ⋅ 1 = 2 . При увеличении x₂ на единицу, целевая функция увеличится на 1 ⋅ Δx₁  = 1 . В первом случае увеличение больше. Поэтому вводим в базис переменную x₁ . То есть считаем, что она может принимать отличные от нуля положительные значения.

Поскольку x₁  ≥ 0 , то переменная x₃ всегда будет положительной. Переменная x₄ обращается в нуль при x₁  = 4 / 2 = 2 . Переменная x₅ – при x₁  = 19 / 3 = 6,333(3 ) . Минимальное из этих величин x₁  = 2 . При этом значении, x₄  = 0,  x₅  = 19 – 3 ⋅ 2 = 13 > 0 . Если положить x₁  > 2 , то переменная x₄ станет отрицательной, что не допустимо.

4. Повторяем шаги 2 и 3.

Итак, если ввести в базис x₂ , то целевая функция увеличится. А если x₄ – уменьшится. Поэтому вводим в базис x₂ .

6. Повторяем шаги 4 и 5.

Ответ

Решение задачи:
x₁  = 5,  x₂  = 2,  F_max  = 12 .

Транспортная задача

Транспортная задача

– это задача линейного программирования следующего вида:
(Т.1)   F = ^mΣ_i = 1 ⁿΣ_j = 1 c_ij x_ij  → min
(Т.2)   ⁿΣ_j = 1 x_ij  = a_i ,  (i = 1 ÷ m )
(Т.3)   ^mΣ_i = 1 x_ij  = b_j ,  (j = 1 ÷ n )
(Т.4)   x_ij  ≥ 0 ,
где a_i  > 0,  b_j  > 0  (i = 1 ÷ m,  j = 1 ÷ n ) .
В транспортной задаче требуется определить количество груза x_ij , которое нужно перевезти от i-го поставщика к j-му потребителю, чтобы суммарные затраты F на перевозки были минимальны. Здесь c_ij – стоимость перевозки единицы груза от i-го поставщика к j-му потребителю; a_i – мощность i-го поставщика, то есть максимальное количество груза, которое может отправить поставщик; b_j – мощность j-го потребителя, то есть максимальное количество груза, которое может принять потребитель.

Транспортную задачу можно решить симплексным методом. Однако имеются методы, которые позволяют получить решение другими, как правило, более легкими способами, используя специфичный вид системы ограничений (Т.2) – (Т.3). Одним из таких методов является метод потенциалов. В нем, как и в симплексном методе ⇑, используется метод последовательного улучшения плана. Мы кратко рассмотрим применение этого метода на примере решения простой транспортной задачи.

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

Условие задачи

Решение

Вначале нужно подсчитать суммы мощностей поставщиков и потребителей. Если сумма мощностей поставщиков равна сумме мощностей потребителей, то такая задача называется задачей с правильным балансом, или задачей с закрытой моделью. Задача, в которой суммы мощностей поставщиков и потребителей не совпадают, называется задачей с неправильным балансом, или задачей с открытой моделью. Если у задачи открытая модель, то ее сначала нужно привести к закрытой модели, добавлением фиктивного поставщика или потребителя с нулевыми стоимостями перевозок. В нашем случае, сумма мощностей поставщиков равна сумме мощностей потребителей:
^mΣ_i = 1 a_i  = 5 + 10 = 15;  ⁿΣ_j = 1 b_j  = 5 + 6 + 4 = 15 .
Модель закрытая, задачу можно решать методом потенциалов.

Задача имеет m ⋅ n = 2 ⋅ 3 = 6 неотрицательных переменных:
x₁₁ ,  x₁₂ ,  x₁₃ ,  x₂₁ ,  x₂₂ ,  x₂₃ .

Поясним, почему ранг системы равен r = n + m – 1 . Это означает, что эти уравнения имеют одну линейную зависимость. Найдем ее. Поскольку модель закрытая, то ^mΣ_i = 1 a_i  – ⁿΣ_j = 1 b_j  = 0 . Подставим (Т.2) и (Т.3):
^mΣ_i = i ⁿΣ_j = 1 x_ij  – ⁿΣ_j = 1 ^mΣ_i = 1 x_ij  = 0 ;
x₁₁  + x₁₂  + x₁₃  + x₂₁  + x₂₂  + x₂₃  – (x₁₁  + x₂₁ ) – (x₁₂  + x₂₂ ) – (x₁₃  + x₂₃ ) = 0 .
Отсюда видно, что если сложить первые два уравнения (Т.6), и вычесть последние три, то получим тождество 0 = 0 . Что означает, что система (Т.6) имеет линейную зависимость.

Применяем метод последовательного улучшения плана.

Метод северо-западного угла

1. Вначале нам нужно найти любой опорный план, удовлетворяющий системе ограничений (Т.6) и условию не отрицательности переменных. Существует несколько методов, позволяющих это сделать. Мы применим метод северо-западного угла.

Заносим исходные данные в таблицу и даем максимально возможную поставку в левую верхнюю клетку (1, 1 ) . В ней находится объем перевозки от 1-го поставщика к 1-му потребителю. В общем случае, максимально возможная поставка в клетку (1, 1 ) равна x₁₁  = min (a₁ , b₁ ) . В нашем случае, мощность первого поставщика a₁  = 5 равна мощности первого потребителя b₁  = 5 . Поэтому наибольшая поставка в клетку (1, 1 ) равна 5. Заносим 5 в клетку (1, 1 ) .

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

Далее заполняем левую верхнюю клетку в оставшейся части таблицы, среди не зачеркнутых клеток. Это клетка (2, 1 ) . В ней находится объем перевозки x₂₁ от 2-го поставщика к 1-му потребителю. Нам нужно дать в нее максимально возможную поставку. Но потребности первого потребителя уже полностью удовлетворены первым поставщиком. Поэтому наибольшая поставка в клетку (2, 1 ) равна нулю. Заносим 0 в клетку (2, 1 ) . Здесь возник случай, когда переменная x₂₁ является базисной, но ее значение равно нулю.

Далее нам нужно вычеркнуть либо строку, либо столбец, содержащий заполненную клетку (2, 1 ) . Поскольку потребности первого потребителя удовлетворены, то вычеркиваем первый столбец.

Снова заполняем левую верхнюю клетку в оставшейся части таблицы, среди не зачеркнутых клеток. Это клетка (2, 2 ) . Мощность второго потребителя равна 6, неизрасходованная мощность второго поставщика: 10. Минимальное из этих чисел: 6. Даем в клетку (2, 2 ) поставку 6, и вычеркиваем 2-го потребителя, поскольку его потребности удовлетворены.

Остается клетка (2, 3 ) , которую можно заполнить единственно возможным значением 4.

В результате мы получили первый опорный план. Базисные переменные: x₁₁  = 5,  x₂₁  = 0,  x₂₂  = 6,  x₂₃  = 4 . Свободные переменные: x₁₂  = x₁₃  = 0 . Значение целевой функции:
F₁  = Σ_ij c_ij x_ij  = 4 ⋅ 5 + 5 ⋅ 0 + 1 ⋅ 0 + 3 ⋅ 0 + 3 ⋅ 6 + 8 ⋅ 4 = 70 .

Определение потенциалов

Определяем потенциалы u_i ,  v_j . Для этого нужно найти любое решение системы уравнений, используя только заполненные клетки таблицы, то есть базисные переменные:
(Т.7)   u_i  + v_j  = c_ij .

Находим оценки свободных клеток (то есть оценки свободных переменных) по формуле:
Δ_ij  = c_ij  – u_i  – v_j .
Δ₁₂  = c₁₂  – u₁  – v₂  = 5 – 0 – 4 = 1; 
 Δ₁₃  = c₁₃  – u₁  – v₃  = 1 – 0 – 9 = – 8 .

Поскольку есть отрицательная оценка Δ₁₃  = – 8 , то план не оптимален. Вводим переменную с отрицательной оценкой x₁₃ в базис.

Переход к новому базису

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

Цикл

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

Строим цикл для клетки (1, 3 ) . Пронумеруем его вершины, начиная со свободной клетки. 1 ) (1, 3 );  2 ) (1, 1 );  3 ) (2, 1 );  4 ) (2, 3 ).

Переходим к новому базису, выполняя перераспределение поставок. Для этого находим минимальное значение поставки среди четных вершин цикла. В нашем случае это поставка 4 в клетке (2, 3 ) . В четных клетках уменьшаем поставки на 4, а в нечетных – увеличиваем на 4. Такое перераспределение поставок называют сдвигом по циклу. При этом поставка в клетке (2, 3 ) становится равной нулю. Ее мы выводим из базиса, а клетка (1, 3 ) становится заполненной, то есть входит в базис.

В результате получаем второй опорный план. Базисные переменные: x₁₁  = 1,  x₁₃  = 4,  x₂₁  = 4,  x₂₂  = 6 . Свободные переменные: x₁₂  = x₂₃  = 0 . Значение целевой функции:
F₂  = Σ_ij c_ij x_ij  = 4 ⋅ 1 + 5 ⋅ 0 + 1 ⋅ 4 + 3 ⋅ 4 + 3 ⋅ 6 + 8 ⋅ 0 = 38 .
Для первого опорного плана было F₁  = 70 . Мы видим, что значение целевой функции стало меньше.

Определение потенциалов нового плана

Находим оценки свободных клеток по формуле:
Δ_ij  = c_ij  – u_i  – v_j .
Δ₁₂  = c₁₂  – u₁  – v₂  = 5 – 0 – 4 = 1; 
 Δ₂₃  = c₂₃  – u₂  – v₃  = 8 – (– 1 ) – 1 = 8 .

Поскольку отрицательных оценок нет, то план оптимален.

Ответ

Наименьшее значение целевой функции F = 38 . Оптимальный план показан в таблице 2 ⇑.

Использованная литература:
С. Гасс. Линейное программирование (методы и приложения). Москва, «Государственное издательство физико-математической литературы», 1961.
Общий курс высшей математики для экономистов. Под общей редакцией В. И. Ермакова. Москва, «ИНФРА-М», 2007.
К. Н. Лунгу. Линейное программирование. Руководство к решению задач. Москва, «ФИЗМАТЛИТ», 2005.
Д. Б. Юдин, Е. Г. Гольштейн. Задачи и методы линейного программирования. Москва, «Советское радио», 1961.

Автор: Олег Одинцов.     Опубликовано: 08-04-2021