5066

22

5. МЕТОД ИСКУССТВЕННОГО БАЗИСА (М-задача)

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

Рассмотрим задачу в общем виде:

Пусть система (1) не является системой с базисом. Прибавим к левой части каждого уравнения системы (1) переменную уi ≥ 0, которую назовем искусственной. Система примет вид:

n

j1

(3)– система с базисом.

23

Составим новую целевую функцию:

Задача нахождения максимума функции (4) при ограничениях (3) называется М-задачей.

Замечание 1. Если исходная задача решается на минимум, то целевая функция М-задачи составляется так:

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

Замечание 2. Искусственные неизвестные следует вводить только в те ограничения, которые не содержат базисных неизвестных.

Связь между решениями исходной и М-задачей устанавливается следующими теоремами.

Теорема 1. Если в оптимальном плане Y 1 , 2 ,..., n , 0,...,0 М-задачи все искусственные переменные равны нулю, то соответствующее решение X 1 , 2 ,..., n исходной задачи также является оптимальным.

Теорема 2. Если в оптимальном плане М-задачи хотя бы одна из искусственных переменных отлична от нуля, то исходная задача решения не имеет.

Алгоритм метода искусственного базиса имеет свои особенности:

1)симплексная таблица имеет две оценочные строки: М-строку и Z- строку. Оценка в М-задаче имеет вид: а + bМ, где М > 0 сколь угодно большое число. Следовательно, знак оценки определяется знаком коэффициента b. Число а записываем в Z-строку (первую строку оценки), а коэффициент b – в М-строку (вторую строку);

2)разрешающий столбец выбирается по оценкам М-строки;

3)если все искусственные переменные вышли из базиса, задача решается дальше обычным симплекс-методом;

4)если М-задача решена, но искусственные переменные не вышли из базиса, то исходная задача решения не имеет.

24

Пример 1.

Преобразуем систему ограничений к системе уравнений:

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

Целевая функция М-задачи:

28

Обозначим соответственно, через y1 и y2 цену единицы сырья А и Б. Производство продукции вида I приносит предприятию доход 12

денежных единиц. При этом расходуется 4 единицы сырья А и 0 единиц сырья Б. Выручка от продажи сырья, расходуемого на единицу продукции I по ценам y1 и y2 , составит

4 y1 0 y2 .

Эта величина должна быть не меньше тех доходов, которые предприятие получит от реализации продукции вида I, следовательно,

4 y1 0 y2 12.

Аналогичные рассуждения в отношении единицы продукции вида II, III, IV приводят к следующим неравенствам:

Общая стоимость всех запасов сырья, приобретаемого организацией, составит W 160y1 900y2 .

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

Получим задачу:

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

1)число неизвестных в двойственной задаче равно числу ограничений в исходной;

2)неравенства в системе ограничений двойственной задачи будут противоположного смысла, чем неравенства в системе ограничений исходной задачи; сохраняется неотрицательность переменных;

3)свободные члены ограничений исходной задачи становятся коэффициентами целевой функции двойственной задачи, а коэффициенты целевой функции исходной задачи превращаются в свободные члены двойственной задачи;

4)в исходной задаче целевая функция минимизируется, а в двойственной – максимизируется.

29

По решению одной из задач можно сразу определить решение другой.

Решим исходную задачу симплекс-методом:

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

Пример 2. В двойственной задаче к основной переменные могут иметь любой знак. Составим двойственную задачу к основной:

Z 3x1 x2 x3 max

30

Двойственная задача имеет следующий вид:

W 6 y1 4 y2 min

Решим двойственную задачу графически

n

y1

1

Координаты точки А дают значения неизвестных y1 и y2 , при которых функция W принимает минимальное значение.

Найдем координаты этой точки:

По решению двойственной задачи найдем решение исходной по второй