12.5. СИМПЛЕКС-МЕТОД РЕШЕНИЯ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ С МНОЖЕСТВОМ ПЕРЕМЕННЫХ

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

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

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

Базовую модель, с которой мы будем работать в дальнейшем, формально можно представить следующим образом:

Максимизировать

Здесь С - константы. Данная функция максимизируется в условиях системы линейных ограничений:

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

Пример 12.8. Некоторая фирма производит два вида продуктов X и Y в условиях ограничений на три вида сырья: Целью фирмы является выбор такого ассортиментного набора, при котором достигается максимум прибыли в неделю. Задача линейного программирования имеет вид:

1. Выпускается х единиц продукта X в неделю и у единиц продукта Y в неделю.

2. Максимизируется еженедельная прибыль Р (ф. ст.), где .

3. Максимизация осуществляется в условиях ограничений:

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

Решение

Графический метод. В каждое ограничение модели вводятся остаточные переменные Максимизировать:

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

Изобразим систему ограничений графически (см. рис. 12.23)

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

В качестве типичной линии уровня прибыли выберем прямую

Рис. 12.23. Задача линейного программирования для объемов выпуска продуктов X и Y в неделю

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

Подставив это значение во второе уравнение системы, получим:

Оптимальным ассортиментным набором является производство 9 единиц продукта X и 11 единиц продукта Y в неделю. Таким образом, максимальная прибыль, получаемая за неделю, составит:

Сырье типа 1 и 3 используется полностью, однако существует свободный запас сырья типа 2, т.е.

следовательно, кг в неделю.

Решение

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

Таблица 12.2. Первая симплекс-таблица (см. скан)

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

Таблица 12.3. Первая симплекс-таблица с учетом отношений (см. скан)

Шаг 3. Выберем среди полученных отношений наименьшее положительное отношение. В нашем случае оно равно 9. Соответствующая ему строка является

ведущей. Пересечение ведущего столбца и ведущей строки дает ведущий элемент 3, в приведенной выше табл. 12.3 он отмечен знаком

Шаг 4. Разделим все элементы ведущей строки на ведущий элемент 3. Заменим все элементы ведущей строки на полученные новые значения (табл. 12.4). Обозначение ведущей строки заменим на обозначение ведущего столбца х. Новые переменные, соответствующие обозначениям строк, — это базисные переменные второго базисного решения.

Таблица 12 4. Вторая симплекс-таблица (см. скан)

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

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

Шаг 6. Шаги 2-5 повторяются до тех пор, пока не будет достигнута неотрицательность всех элементов в строке целевой функции.

Таблица 12.5. Вторая симплекс-таблица с отношениями (см. скан)

Таблица 12.6. Третья, итоговая, симплекс-таблица (см. скан)

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

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

Таблица 12.7. Интерпретация итоговой симплекс-таблицы (см. скан)

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

а значение остаточной переменной для сырья 2 составило 8 кг в неделю.

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

найденным ранее. Элементы, стоящие на пересечении строки целевой функции и столбцов остаточных переменных, соответствуют, как показано в табл. 12.7, теневым ценам ресурсов. Теневая цена для ограничения 1, т.е. цена ресурса составляет ст. за 1 кг, а теневая цена для ограничения ст. за 1 кг. Это означает, что если реализуется 1 кг ресурса сверх нормативного запаса, прибыль за неделю возрастает на 33 пенса (минус любые издержки сверх обычной стоимости Аналогичным образом, если используется сверхнормативное количество ресурса в 1 кг, рост прибыли за неделю составит ст. (минус любые дополнительные издержки). Найденные значения теневых цен можно проверить, вычислив их с помощью графического метода. Чтобы проиллюстрировать эту процедуру, обратимся к ограничению 1.

Ограничение 1, соответствующее сырью 1, имеет вид: кг в неделю. Снизив жесткость этого ограничения на 1 кг, получим: Оптимальная крайняя точка по-прежнему будет находиться на пересечении линий ограничений 1 и 3. Чтобы убедиться в справедливости этого положения, достаточно взглянуть на соответствующий график. Новая точка оптимума имеет следующие координаты:

а соотношение

приводит к тому, что

Новое максимальное значение прибыли за неделю составит:

Увеличение прибыли на 33 пенса произошло в результате использования 1 кг ресурса дополнительно. Следовательно, теневая цена ресурса равна 33 пенсам за 1 кг.

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

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

Таблица 12.8. Модификация итоговой таблицы

Оптимальный ассортиментный набор для этого решения — это выпуск только продукта X в количестве 9 единиц. Если по тем или иным причинам некоторое количество продукта У все же необходимо произвести, значение целевой функции уменьшится на 0,5 ф. ст., приходящихся на каждую производимую единицу продукта У.