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

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

Содержание

См. также:

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

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

Общая задача линейного программирования формулируется следующим образом.
Найти максимум (или минимум) линейной функции n переменных :
(1.1)
при ограничениях вида
(1.2) $\left\{\begin{aligned}a_{11}x_1+a_{12}x_2+\cdots+a_{1n}x_n&=b_1\\............................&....\\a_{p1}x_1+a_{p2}x_2+\cdots+a_{pn}x_n&=b_p\\a_{p+1,1}x_1+a_{p+1,2}x_2+\cdots+a_{p+1,n}x_n&\leqslant b_{p+1}\\.....................................&.......\\a_{p+q,1}x_1+a_{p+q,2}x_2+\cdots+a_{p+q,n}x_n&\leqslant b_{p+q}\\a_{p+q+1,1}x_1+a_{p+q+1,2}x_2+\cdots+a_{p+q+1,n}x_n&\geqslant b_{p+q+1}\\..........................................&.........\\a_{p+q+s,1}x_1+a_{p+q+s,2}x_2+\cdots+a_{p+q+s,n}x_n&\geqslant b_{p+q+s}\end{aligned}\right.$
(1.3) .

Переменные задачи часто записывают в виде n-мерного вектора:
.

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

Система ограничений (1.2) может состоять из равенств
,
и неравенств обоих знаков:
, или
.

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

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

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

Каноническая форма задачи линейного программирования: – это общая задача линейного программирования, в которой система ограничений состоит из равенств и условий не отрицательности для всех переменных:

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

(1.5)
.
Или

(1.6)
.

Теорема о канонической форме задачи ЛП

Любую общую задачу линейного программирования (1.1) – (1.3)
можно привести к каноническому виду (1.4).
А любую задачу в канонической форме
можно привести к любой из задач в симметричной форме (1.5) или (1.6).

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

Дополнительная переменная (вспомогательная переменная): – это переменная, которая вводится для преобразования неравенства в равенство. Дополнительную переменную также называют вспомогательной переменной. Например, неравенство

переводится в равенство, введением дополнительной неотрицательной переменной :
.

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

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

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

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

Решим графическим способом следующую задачу.
(2.1)
(2.2)
(2.3) .

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

Теперь рассмотрим целевую функцию (2.1). Построим ее линию уровня, приравняв F к любому значению, например :
(2.4) .
Строим прямую . С левой стороны от этой прямой . С правой стороны, . И чем больше мы удаляемся вправо и вверх, тем больше значение целевой функции F. Проводим прямую, параллельную прямой (2.4), так, чтобы она была максимально удалена в сторону увеличения значений F, то есть вправо, и при этом проходила хотя бы через одну точку ОДР. Такая прямая проходит через точку B с координатами . Это точка имеет наибольшее значение F среди всех точек ОДР. Поэтому является оптимальным планом с максимальным значением целевой функции:
.

Ответ

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

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

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

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

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

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

Теорема о выпуклости ОДР

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

Теорема об оптимальном решении задачи ЛП

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

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

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

Лемма об оптимальном плане задачи ЛП

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

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

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

Теорема об угловой точке

Угловая точка ОДР (1.2) – (1.3) является решением системы из n уравнений, полученной из (1.2) – (1.3), вычеркиванием части неравенств, и заменой оставшихся неравенств равенствами.

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

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

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

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

Свободные переменные: – это переменные задачи ЛП в канонической форме, на которые, в рассматриваемом опорном плане, наложено условие их равенства нулю: .
Базисные переменные: – это переменные задачи ЛП в канонической форме, которые в рассматриваемом опорном плане, не являются свободными. Они имеют неотрицательные значения, которые определяются из решения системы уравнений (1.4).
Невырожденный план (невырожденное решение): – это опорный план, в котором все базисные переменные отличны от нуля.
Вырожденный план (вырожденное решение): – это опорный план, в котором есть одна или несколько базисных переменных, равных нулю.
Векторы условий: – это n векторов, которые являются столбцами матрицы коэффициентов системы (1.4).
Вектор ограничений: – это вектор, который являются столбцом правой части матрицы коэффициентов системы (1.4). То есть это вектор .
Базис: – это r векторов, которые являются столбцами матрицы коэффициентов системы (1.4) при базисных переменных. То есть базис – это векторы условий при базисных переменных.

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

Теорема о числе базисных переменных

При решении задачи линейного программирования в канонической форме ⇑,
в любом опорном плане имеется r базисных переменных ⇑.
Отсюда следует, что в опорном плане как минимум

переменных равны нулю. Здесь n – число переменных; r – ранг матрицы системы ограничений (1.4), из которой определяются значения базисных переменных.

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

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

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

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

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

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

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

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

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

Для этого приведем задачу к канонической форме, вводя три дополнительные неотрицательные переменные :
(П.1)
(П.2)
(П.3) .

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

1) В качестве свободных переменных возьмем и . Приравниваем их к нулю, и подставляем в (П.2); получаем: . Поскольку все , то мы нашли угловую точку ОДР или, что тоже самое, вершину многогранника ОДР: . На построении ⇑ ей соответствует точка O.

2) Возьмем свободные переменные и . Подставляя их нулевые значения в (П.2), получаем систему:

Решаем ее: . Поскольку все , то это угловая точка: , На построении ⇑ ей соответствует точка D.

3) Возьмем свободные переменные и . Подставляем их нулевые значения в (П.2). Решая систему, получаем: . Поскольку , то эта точка не принадлежит ОДЗ. Поэтому она не может быть планом задачи. Отбрасываем ее. На рисунке ⇑ ей соответствует точка пересечения прямой AB с осью .

4) Свободные переменные . Подставляя их нулевые значения в (П.2), находим: . Здесь также есть отрицательная переменная . Эта точка также не принадлежит ОДЗ. Отбрасываем ее. Это точка пересечения прямой BC с осью .

5) Свободные переменные . Подставляя в (П.2), находим решение системы: . Поскольку , то и эта точка не принадлежит ОДЗ. Отбрасываем ее. Это точка пересечения прямой DC с осью .

6) . Решение системы: . Поскольку все , то мы нашли угловую точку, которой на построении ⇑ соответствует точка A.

7) . Решение системы: . , точка не принадлежит ОДЗ. На рисунке ей соответствует точка пересечения прямой BC с осью .

8) . Решение системы: . , точка не принадлежит ОДЗ. Это точка пересечения прямых AB и DC.

9) . Решение системы: . Все . Это угловая точка – точка C.

10) . Решение системы: . Все . Это угловая точка. На построении ⇑ ей соответствует точка B.

Итак, мы нашли все угловые точки ОДР. Находим в них значения целевой функции.
;
;
;
;
.

Ответ

Наибольшим является значение целевой функции в точке B. Решение задачи: .

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

См. также: Решение задач симплекс методом – онлайн калькулятор

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

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

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

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

Рассмотрим задачу (2.1) – (2.3). Как и при решении методом перебора вершин, вводим три дополнительных неотрицательных переменных . Получаем задачу в канонической форме:
(С.1)
(С.2)
(С.3) .
Решаем задачу симплексным методом.

1. Вначале нам нужно найти любой опорный план, удовлетворяющий системе ограничений (С.2) – (С.3). Самый простой способ – это взять в качестве базиса дополнительные переменные . При этом из системы (С.2) мы сразу можем выразить базисные переменные через свободные:
(С.4)
Приравнивая свободные переменные и к нулю, получаем первый опорный план, который мы обозначим буквой O: , или в сокращенной форме . Значение целевой функции: .
На рисунке ⇑, этому плану соответствует точка .

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

2.1. Проверим, как изменится целевая функция, если свободной переменной вместо нулевого, присвоить положительное значение . При этом считаем, что мало отличается от нуля. То есть сделаем оценку свободной переменной . Положим, . Тогда, чтобы выполнялась система ограничений (С.4), необходимо также изменить базисные переменные:
.
Свободная переменная по прежнему равняется нулю. Подставляя в (С.4), и удаляя равные слагаемые в обеих частях равенств, получаем:
(С.5)
Обозначим эту новую точку как . Найдем разность значений целевой функции в точках и :

.
Таким образом, если переменной присвоить положительное значение , то целевая функция увеличится на .

2.2. Проделаем тоже самое с переменной . То есть сделаем оценку для свободной переменной . Положим, . Чтобы выполнялась система ограничений (С.4), также изменим базисные переменные. Положим . Свободная переменная при этом равняется нулю. Подставляя в (С.4), и удаляя равные слагаемые в обеих частях равенств, получаем:
(С.6)
Обозначим эту новую точку как . Найдем разность значений целевой функции в точках и :

.
Если переменной присвоить положительное значение , то целевая функция увеличится на .

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

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

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

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

Выводим , и вводим в состав базисных переменных. Для этого над системой (С.4) выполняем линейные преобразования, чтобы выразить базисные переменные через свободные . В результате линейных преобразований получаем эквивалентную систему:
(С.7)
Приравнивая свободные переменные к нулю, получаем второй опорный план. Обозначим его буквой A: . Значение целевой функции:
.
На рисунке ⇑, этому плану соответствует точка . То есть в результате мы перешли из вершины в вершину многогранника ОДР.

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

4.1. Попробуем ввести в базис. Положим . Подставляем в (С.7):

Изменение целевой функции:
.

4.2. Попробуем ввести в базис . Положим . Подставляем в (С.7):

Изменение целевой функции:
.

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

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

Переменная положительна при любых значениях . Переменная обращается в нуль при ; переменная – при . Наименьшее: . При этом переменная принимает нулевое значение и выходит из базиса.

Выводим из базиса. Для этого выражаем базисные переменные через свободные , преобразовав систему (С.7):
(С.8)
Приравнивая свободные переменные и , получаем третий опорный план, который обозначим буквой B: . Значение целевой функции:
.
На рисунке ⇑, этому плану соответствует точка .

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

6.1. Попробуем ввести в базис . Положим . Подставляем в (С.8):

Изменение целевой функции:

.
. Введение в базис не приведет к увеличению значения целевой функции.

6.2. Попробуем ввести в базис . Положим . Подставляем в (С.8):

Изменение целевой функции:

.
И здесь . Введение в базис также не приведет к увеличению значения целевой функции. Поэтому последний план B оптимален.

Ответ

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

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

См. также: Решение транспортной задачи – онлайн калькулятор

Транспортная задача: – это задача линейного программирования следующего вида:
(Т.1)
(Т.2)
(Т.3)
(Т.4) ,
где .
В транспортной задаче требуется определить количество груза , которое нужно перевезти от -го поставщика к -му потребителю, чтобы суммарные затраты на перевозки были минимальны. Здесь – стоимость перевозки единицы груза от -го поставщика к -му потребителю; – мощность -го поставщика, то есть максимальное количество груза, которое может отправить поставщик; – мощность -го потребителя, то есть максимальное количество груза, которое может принять потребитель.

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

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

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

Пусть у нас имеется поставщика с мощностями , и потребителя с мощностями . Стоимость перевозки единицы груза от -го поставщика к -му потребителю задана в таблице:
(Т.5)
Требуется найти план перевозок, при котором суммарные затраты на перевозки минимальны.

Решение

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

Задача имеет неотрицательных переменных:
.

Задача (Т.1) – (Т.4) имеет канонический вид. Подсчитаем число базисных переменных. Система ограничений (Т.2) – (Т.3) содержит уравнений:
(Т.6)
Существует теорема, согласно которой, ранг r системы ограничений транспортной задачи равен . То есть система (Т.6) имеет линейно независимых уравнения. Тогда по теореме о числе базисных переменных ⇑, угловая точка ОДР имеет r = 4 базисных переменных, и свободных.

Поясним, почему ранг системы равен . Это означает, что эти уравнения имеют одну линейную зависимость. Найдем ее. Поскольку модель закрытая, то . Подставим (Т.2) и (Т.3):
;
.
Отсюда видно, что если сложить первые два уравнения (Т.6), и вычесть последние три, то получим тождество . Что означает, что система (Т.6) имеет линейную зависимость.

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

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

Заполняем верхнюю левую ячейку, и вычеркиваем первую строку.

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

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

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

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

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

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

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

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

В результате мы получили первый опорный план. Базисные переменные: . Свободные переменные: . Значение целевой функции:
.

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

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

Запишем уравнения (Т.7) для заполненных клеток:
(Т.8)
Здесь 4 уравнения и 5 неизвестных. Поэтому одной переменной можно присвоить произвольное значение. Полагаем . Решаем систему (Т.8).
.

Находим оценки свободных клеток (то есть оценки свободных переменных) по формуле:
.

.

Поскольку есть отрицательная оценка , то план не оптимален. Вводим переменную с отрицательной оценкой в базис.

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

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

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

Строим цикл для клетки . Пронумеруем его вершины, начиная со свободной клетки.

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

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

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

Определяем потенциалы для нового опорного плана. Запишем уравнения (Т.7) для заполненных клеток:
(Т.9)
Полагаем . Решаем систему (Т.9).
.

Находим оценки свободных клеток по формуле:
.

.

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

Ответ

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

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

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

См. также: