При помощи метода искусственного базиса

⇐ ПредыдущаяСтр 6 из 10Следующая ⇒

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

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

(7.1)

, (7.2)

где , , причем . Условие неотрицательности можно добиться путем умножения -го уравнения на число , если . Наряду с ЗЛП (7.1) – (7.2) рассмотрим ЗЛП

(7.3)

, (7.4)

где , , .

Определение 7.1. ЗЛП (7.3) – (7.4) будем называть М-задачей. Неизвестными в М-задаче являются , . Переменные принято называть искусственными переменными, а вектор – вектор-столбцом искусственных переменных.

Так как в системе (7.3) , то она имеет допустимый вид с допустимым базисом из искусственных переменных . Для решения М-задачи (7.3) – (7.4) можно воспользоваться симплекс-методом.

Замечание 7.1. В систему ограничений (7.3) мы ввели искусственных переменных . Однако на практике при решении ЗЛП М-методом искусственных переменных может понадобиться меньше, чем количество ограничений (см. пример 7.1).

Следующие теоремы устанавливают связь между решениями исходной задачи (7.1) – (7.2) и соответствующей М-задачи (7.3) – (7.4).

Теорема 7.1. Пусть набор , есть оптимальное решение М-задачи (7.3) – (7.4) при каком-то значении . Если при этом все значения искусственных переменных равны нулю, то вектор является оптимальным решением исходной задачи (7.1) – (7.2).

□ Пусть , . Тогда значения удовлетворяют системе ограничений (7.1). Предположим, что вектор есть какое-нибудь другое решение системы (7.1). Покажем, что (этим будет показано, что есть оптимальное решение ЗЛП (7.1) – (7.2)). Дополнив значения числами , получим, что вектор

удовлетворяет системе (7.3). Ввиду оптимальности вектора имеем

Учитывая, что , находим

Тогда, так как , то .

Заметим, что так как , то

■

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

Теорема 7.2. Пусть набор , есть оптимальное решение М-задачи (7.3) – (7.4) при всех значениях . Если при этом хотя бы одно из значений искусственных переменных отлично от нуля, то вектор система ограничений (7.1) несовместна (ЗЛП (7.1) – (7.2) не имеет допустимого решения).

□ Доказательство проведем методом от противного. Предположим, что система (7.1) совместна и имеет допустимое (не обязательно оптимальное) решение . Тогда вектор является решением системы ограничений (7.3). Так как набор , является оптимальным решением М-задачи (7.3) – (7.4), то

что равносильно неравенству

Итак, при всех значениях получили неравенство

. (7.5)

Так как среди значений существует хотя бы одно положительное, то число можно выбрать таким большим, что неравенство (7.5) не выполнится. Полученное противоречие доказывает теорему. ■

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

Теорема 7.3. Если М-задача (7.3) – (7.4) не имеет оптимального решения ( ), то ЗЛП (7.1) – (7.2) также не имеет оптимального решения (либо , либо система (7.1) несовместна).

Пример 7.1. Решить М-методом ЗЛП

Решение. Приведем ЗЛП к каноническому виду и составим для ЗЛП соответствующую М-задачу. Для этого в первое и третье ограничения системы сначала введем балансовые переменные , (целевая функция при этом не изменится):

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

Для получения допустимого базиса переменных во второе и третье уравнения последней системы введем искусственные переменные , . В результате получим М-задачу ( , , ) с допустимым базисом , системой ограничений

(7.6)

и целевой функцией

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

Итак, целевая функция М-задачи имеет вид

Приведем целевую функцию к каноническому виду:

. (7.7)

По системе ограничений (7.6) и целевой функции (7.7) построим начальную симплекс-таблицу (табл. 7.1).

Табл. 7.1

БП	СЧ					Преобразования
				– 1
				– 3
		– 1	– 4		– 1

Базисное решение имеет вид

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

На первом шаге симплекс-метода происходит смена базиса с соответствующими преобразованиями в табл. 7.1. В результате получаем табл. 7.2.

Табл. 7.2

БП	СЧ			Преобразования


		– 3	– 1

Базисное решение имеет вид

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

Табл. 7.3

БП	СЧ				Преобразования
				– 1
		– 8	– 3
		– 6	– 2

Базисное решение имеет вид

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

Табл. 7.4

БП	СЧ
		– 1

Базисное решение имеет вид

Построенное базисное решение удовлетворяет условию оптимальности, так как в -строке среди коэффициентов при переменных , , нет ни одного положительного (числа , отрицательны). Итак, М-задача имеет оптимальное решение . Согласно теореме 7.1, так как значения искусственных переменных , в оптимальном решении равны нулю, то исходная ЗЛП также имеет оптимальное решение , причем .

⇐ Предыдущая 1 2 3 4 567 8 9 10 Следующая ⇒