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

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

Таким образом, симплекс-метод  предполагает следующие процедуры:

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

 Выбрать свободные  (небазисные) и базисные (несвободные)  переменные. Выразить базисные через свободные переменные.

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

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

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

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

6. Найти новое базисное  решение, соответствующее новым  составам небазисных и базисных  переменных. Перейти к пункту 4.

 

Пример 3

Решим симплекс-методом задачу, изложенную в примере 1 раздела 2.1.

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

 

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

Изменим задачу максимизации на задачу минимизации, приняв целевую  функцию в виде

Примем переменные в качестве базисных и выразим их через свободные переменные Получим

В качестве начального допустимого  базисного решения возьмем такое, которое соответствует нулевым  значениям свободных переменных, т. е. Тогда Этому решению соответствует нулевое значение целевой функции Z=0 и точка О в начале координат на рис. 2.

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

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

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

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

Величина  из третьего уравнения выражается по формуле

Подставляя величину в первое и второе уравнения, получаем

Таким образом, новое базисное решение:

.

Значение целевой функции  выразим через свободные переменные, заменив  , получим

При и величина Z=-600.

Новое решение лучше предыдущего, поскольку значение целевой функции  уменьшилось с 0 до -600. Этому решению соответствует точка A на рис. 2.

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

Следующий шаг начинается с выбора нового базиса. Быстрее  всех нулевого значения достигнет переменная при Дальнейшее увеличение поэтому невозможно. Величина определяется по аналогии с определением величины на предыдущем шаге и будет равна:

Тогда переменные и определяются из уравнений:

Следовательно, получаем новое  решение, соответствующее значениям  и определяемое соотношениями:

Значение целевой функции  определим из выражения

,

т. е. Z=-640.

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

Таким образом, для получения  максимальной прибыли при заданных ресурсах необходимо запланировать  изготовление изделий А в количестве 20 штук и изделий Б в количестве 40 штук. Суммарная прибыль равна 640 единицам.