Мат_модели

−3x1 + 2x2 + x3 = 4, 21. z = 2x1 − 2x2 − x3 − x5 −13 → min при x ≥ 0 и −5x1 −3x2 − x4 = −25,

2x1 −3x2 + x5 = 6.

§4. Метод искусственного базиса

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

Пусть исходная система нетривиальных ограничений задана в общем виде

где bi ≥ 0,i =1,K, m. Выполнения последнего условия всегда можно до-

биться, умножив уравнения на −1. Введем в систему новые (искусственные) переменные y1, y2 ,K, ym

20

так что новая система имеет допустимое базисное решение (0,0,K,0;b1,b2 ,K,bm ) Rn+m . Рассмотрим вспомогательную целевую функ-

Если последняя задача имеет решение, то возможны два случая:

1. Если min F > 0 , то система ограничений не имеет допустимого базиса и задача не имеет решений.

2. Если min F = 0 , то система ограничений имеет неотрицательное базисное решение. Чтобы получить систему ограничений, эквивалентную исходной, но с выделенным допустимым базисом, необходимо, чтобы в заключительной симплекс-таблице все искусственные переменные были свободными.

Пример 9. Рассмотрим задачу из примера 6 § 3:

z = 3x1 − x2 − 2x3 + 6x4 −10 → min

x1 +3x2 + 7x3 − x4 = 6,x1 − x2 − x3 +3x4 = 2,

x ≥ 0.

и выделим допустимый базис с помощью вспомогательной задачи. Итак, рассмотрим задачу

В системе выделен допустимый (искусственный) базис y1, y2 , поэтому выражаем из уравнений базисные переменные

21

y1 = 6 − x1 −3x2 −7x3 + x4 ,y2 = 2 − x1 + x2 + x3 −3x4

Данная симплекс-таблица – заключительная, искусственные переменные y1, y2 стали свободными и мы, опуская последнюю строку и столбцы, им соответствующие, получаем таблицу

22

т.е. получаем систему ограничений с выделенным допустимым базисным решением, которая равносильна исходной системе ограничений и совпадает с системой, полученной (другим способом) в примере 6 §3.

Пример 10. Решить задачу

z = x1 +3x2 +8 → min− x1 + x2 + x3 =1,

x1 +3x2 − x4 =19,

3x1 + x2 + x5 = 33,

x ≥ 0

симплекс-методом.

Решение. В данной задаче допустимый базис выделен лишь частично (переменные x3 , x5 ), поэтому ограничимся лишь введением одной

Сделаем шаг симплекс-метода с выделенным разрешающим элементом

23

Выводим из базиса переменную y и вводим в базис x1 .

Вспомогательная задача F → min решена и искусственная переменная y –

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

Более того, данная симплекс-таблица – заключительная, поэтому решением задачи является X1 = (4,5,0,0,16) , а так как имеется свободный стол-

бец x3 с нулевой оценкой, то имеется альтернативное решение. Выводим из базиса переменную x5 и вводим в базис x3 :

24

получаем альтернативное решение X 2 = (10,3,8,0,0) . Как и в примере 7

убеждаемся, что альтернатив больше нет, поэтому общее решение задачи

X = (1−t)X1 +tX 2 = (1−t)(4,5,0,0,16)+t(10,3,8,0,0)= (4 +6t,5 −2t,8t,0,16 −16t),t [0,1]. Ответ. zmin = 27 при X = (4 +6t,5 −2t,8t,0,16 −16t),t [0,1].

Пример 11. Решить задачу

z = x1 + 2x2 +9 → maxx1 + x2 − x3 = 2,

x1 + 4x2 + x4 =1,− x1 + x2 − x5 = 3,

x ≥ 0.

симплекс-методом.

Решение. Вводим две искусственные переменные y1, y2 и решим следующую задачу

F = y1 + y2 → minx1 + x2 − x3 + y1 = 2,x1 + 4x2 + x4 =1,

− x1 + x2 − x5 + y2 = 3,

x ≥ 0, y ≥ 0.

25

В строке оценок есть единственный положительный элемент, поэтому вводим в базис x2 и выводим из базиса x5 :

Все элементы строки оценок для задачи F → min отрицательны, поэтому симплекс-таблица – заключительная, но, так как min F = 9 / 2 > 0 , то исходная задача не имеет ни одного допустимого базиса и решений не имеет.

Задачи для самостоятельного решения

Решить задачи линейного программирования, используя метод искусственного базиса

26

− x1 + x2 + x3 = 2, 29. z = 7x1 + 2x3 − x4 + x5 + 24 → max при x ≥ 0 и 3x1 − x2 + x4 = 3,

5x1 + 2x2 + x3 + x4 + x5 =11.

− x1 + 2x2 + x3 = 2,

30. z = 7x2 + x3 − x4 − x5 +17 → min при x ≥ 0 и 9x1 + x2 + x3 + x4 + 2x5 = 26,

3x1 − 2x2 + x5 = 3.

x1 − x2 + x3 =1, 31. z = x1 + x3 + x4 + x5 + 29 → max при x ≥ 0 и 3x1 + x2 + x5 = 7.

5x1 + 2x2 + 2x3 + x4 +3x5 =17.

27

ВЗАИМНО ДВОЙСТВЕННЫЕ ЗАДАЧИ

§1. Основные определения и теоремы

Рассмотрим пару двойственных задач линейного программирова-

ния

виальные ограничения налагаются лишь на часть координат векторов X ,Y ). Нетривиальные ограничения в обеих задачах могут быть как типа неравенств (со знаком « ≤» или « ≥»), так и типа уравнений. Чтобы понять связь между этими задачами, построим расширенные матрицы

и

28

обеих задач. Таким образом,

1.Матрица нетривиальных ограничений двойственной задачи получается из соответствующей матрицы исходной задачи транспонированием.

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

3.Если исходная задача является задачей на максимум (на минимум), то двойственная задача будет задачей на минимум (на максимум),

истрока тривиальных ограничений переходит в столбец нетривиальных ограничений без изменения знака неравенства с « ≤» на « ≥» и наоборот (соответственно, с изменением знака). Если на переменную в исходной задаче тривиальное ограничение отсутствует, то соответствующее ограничение в двойственной задаче будет типа уравнения; иными словами, «~» переходит в «=». Столбец нетривиальных ограничений переходит в строку тривиальных ограничений с изменением знака неравенства с « ≤» на « ≥» и наоборот (соответственно, без изменения знака), а «=» переходит в «~».

Пример 1. Для задачи

29