Метод искусственных переменных

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

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

Пример 2.5.

Минимизировать

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

Сначала задача преобразуется к стандартной форме:

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

В уравнении (2.12) дополнительная переменная - базисная, поскольку

а) она не присутствует в других уравнениях;

б) правая часть уравнения положительная (11>0), следовательно, обнулив значения небазисных переменных , получим , что не противоречит условию неотрицательности переменных.

Так как в других уравнениях нет базисных переменных, вводятся искусственные переменные и , являющиеся базисными для уравнений (2.13) и (2.14) соответственно. Для сохранения стандартной формы задачи переменные и предполагаются неотрицательными. Тогда получается следующая вспомогательная система:

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

Двухэтапный симплекс-метод.

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

Так, для рассмотренного выше примера на первом этапе решается вспомогательная задача вида:

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

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

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

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

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

Постановка задачи. Основные понятия

Общая постановка транспортной задачи состоит в определении оптимального плана перевозок некоторого однородного груза из пунктов отправления в пунктов назначения . При этом в качестве критерия оптимальности обычно берется либо минимальная стоимость перевозок всего груза, либо минимальное время его доставки. Рассмотрим задачу, в которой минимизируется стоимость перевозок. Обозначим через тарифы перевозки единицы груза из -го пункта отправления в -й пункт назначения. Через -запасы груза в -м пункте отправления, через -потребности в грузе -го пункта назначения, а через - количество единиц груза, перевозимого из -го пункта отправления в ‑й пункт назначения. Тогда математическая постановка задачи имеет вид:

(3.1)