Методичка по курсовым и лабораторным работам (1085639), страница 10
Текст из файла (страница 10)
x3 = 2 – x1 – x2,
x4 = 1 – x1 + x2.
Полагая свободные переменные равными нулю, получим базисное решение x0 = (0, 0, 2, 1). Очевидно, оно является допустимым базисным решением или угловой точкой допустимого множества решений. Так как целевая функция (3.21) зависит лишь от свободных переменных, то выражения (3.21) представляют собой канонический вид ЗЛП для допустимого решения x0. Поэтому симплекс-таблица имеет вид:
| x1 x2 | ||
| x3 x4 | 1 1 1 –1 | 2 1 |
| –1 –2 | 0 |
3.4. Симплекс-метод
Симплекс-метод решения ЗЛП основан на следующих трех теоремах (приводятся без доказательства).
Теорема 3.1. Если все коэффициенты целевой функции (3.21) неотрицательны, т. е. pj ? 0, j = m + 1, m + 2, …, n, то в точке x0 = (b1, b2, …, bm, 0, …, 0) достигается минимум целевой функции f(x1, x2, …, xn) на множестве допустимых решений.
Теорема 3.2. Если не все коэффициенты pj ? 0, и среди отрицательных коэффициентов pj есть такой, например, pk, что все aIk ? 0, i =1,…, m, то минимум целевой функции на множестве допустимых решений не достигается, т. е. ЗЛП не имеет решения.
Теорема 3.3. Пусть x0 = (b1, b2, …, bm, 0, …, 0) является невырожденным допустимым базовым решением, т.е. bI > 0,, i =1,…, m. Тогда, если хотя бы один из коэффициентов pj, например, pk, отрицателен и при этом среди коэффициентов aIk есть положительные, то существует допустимое базовое решение x1 ? x0, для которого f(x1) < f(x0).
Идея симплекс-метода решения ЗЛП заключается в следующем.
Если для точки x0 = (b1, b2, …, bm, 0, …, 0) выполняются условия теоремы 3.1, то решение найдено: точка x0 является решением ЗЛП.
Если для точки x0 выполняются условия теоремы 3.2, то решение завершается с выводом: функция неограниченно убывает и ЗЛП не имеет решения.
Если для точки x0 выполняются условия теоремы 3.3, то совершается переход от x0 к новому допустимому базисному решению x1, для которого значение целевой функции меньше, f(x1) < f(x0). Затем в точке x1 анализ коэффициентов повторяется, и на основании теорем 3.1 – 3.3 делается одно из трех возможных заключений и т.д.
Так как число допустимых базовых решений не превосходит C
, то лишь конечное число раз может возникнуть ситуация, описываемая теоремой 3.1, которая требует перехода к новому допустимому базисному решению. Поэтому в результате конечного числа шагов задача линейного программирования будет решена, или же будет установлена ее неразрешимость.
Таким образом, симплекс-метод представляет собой направленный перебор допустимых базовых решений ЗЛП с последовательным уменьшением целевой функции.
Рассмотрим подробнее процедуру перехода к новому допустимому базисному решению в условиях теоремы 3.1.
Пусть x0 = (b1, b2, …, bm, 0, …, 0) – невырожденное допустимое базовое решение. По условию теоремы 3.3 среди коэффициентов aIk есть положительные. В соответствии с (3.19) xi = bi – 
, i =1,…, m. Поэтому условие положительности aIk приведет к тому, что при увеличении xk может произойти нарушение условия неотрицательности соответствующих переменных xi. Найдем ту из них, xq, которая раньше всех обратится в нуль при возрастании xk. С учетом (3.19) номер q находится из условия:
(3.25)
Найдем канонический вид задачи, соответствующий новому базисному решению.
Пусть x1 = (x11, … , xq1, …, xm1, 0, …, xk1, …, 0) – новое базисное решение.
Базисная переменная xq станет свободной, а свободная переменная xk – базисной. Перепишем q-ое уравнение системы (3.22) следующим образом:
xq + aqk xk + 
= bq. (3.26)
Разделим это уравнение на aqk:
xk + 
xq +
= 
. (3.27)
Выразим из равенства (3.27) переменную xk:
xk = – xq – . (3.28)
Остальные уравнения системы (3.22) перепишем аналогично (3.26)
xi + aik xk + = bI, i =1,…, m, i ? q. (3.29)
Подставим в (3.29) выражение для xk (3.28):
xi + aik ( – xq – ) + = bI, i =1,…, m, i ? q.
или
xi – 
xq +
= bI – 
, i =1,…, m, i ? q. (3.30)
Подставим (3.28) в формулу (3.21) для целевой функции. В результате получим:
f(x1, x2, …, xn) = f(x1, x2, …, xn) = f(x0) + 
= f(x0) + pkxk + = f(x0) + pk( – xq – ) + = f(x0) +
+
Итак, получен следующий канонический вид задачи, соответствующий новому базисному решению x1:
f(x0) + + ® min, (3.31)
xi – xq + = bI – , i =1,…, m, i ? q, (3.32)
xj ? 0, j = 1, 2, …, n.
Задача линейного программирования с допустимым базисным решением x1 так же, как и задача с допустимым базисным решением x0 может быть записана с помощью симплекс-таблицы.
Пусть нам требуется вывести из числа свободных переменных какую-нибудь переменную, например, xk, и перевести ее в базисные, а взамен ее ввести в число свободных какую-то базисную переменную, например, xq; короче, мы хотим обменять переменные xk и xq. Номера переменных k и q и элемент aqk определяется по правилу (3.25). Элемент aqk, а также q-ую строку и k-ый столбец, на пересечении которых он стоит, называют разрешающими или опорными. Следующий алгоритм преобразования симплекс-таблицы реализует расчет по формулам (3.31) и (3.32).
Алгоритм 3.1. (Преобразование симплекс-таблицы)
Пусть есть симплекс-таблица для допустимого базисного решения x0. Пусть разрешающий элемент aqk выбран по правилу (3.25).
Шаг 1. Поменять местами обозначения переменных xk и xq в новой симплекс–таблице.
Шаг 2. Разрешающий элемент заменяется на обратную ему величину.
Шаг 3. Все остальные элементы разрешающей строки делятся на разрешающий элемент.
Шаг 4. Все элементы разрешающего столбца (кроме самого разрешающего элемента) меняют знак и делятся на разрешающий элемент.
Шаг 5. На оставшиеся свободные места элементов aij , bI, pj в новой симплекс-таблице записать числа 
, 
, 
, которые определяются следующим образом:
= (aijaqk – aqjaik), = (biaqk – bqaik), = (pjaqk – pqaqj).
Для упрощения вычислений по этим формулам можно воспользоваться правилом прямоугольника, представленного на рис. 3.1 соответственно для вычисления , , .
|
|
|
|
Это правило заключается в следующем. Элементы, стоящие на диагоналях прямоугольника, перемножаются, причем произведение, не содержащее опорного элемента aqk, берется со знаком минус и полученные произведения складываются и делятся на опорнqk.
Пример 3.6.
Преобразовать симплекс-таблицу из примера 3.5.
| x1 x2 | ||
| x3 x4 | 1 1 1 –1 | 2 1 |
| –1 –2 | 0 |
Выберем в качестве опорного элемент, стоящий на пересечении строки, соответствующей переменной x3 и столбца, соответствующего переменной x2 (он выделен жирным шрифтом). Таким образом, переменную x2 из свободной переведем в базисные, а переменную x4 из базисной переведем в свободную. Будем формировать новую таблицу в соответствии с алгоритмом.
Шаг 1.
| x1 x3 | ||
| x2 x4 | 1 | |
Шаг 2 не меняет таблицы, т. к. обратный элемент для единицы есть единица.
Шаг 3.
| x1 x3 | ||
| x2 x4 | 1 1 | 2 |
Шаг 4.
| x1 x3 | ||
| x2 x4 | 1 1 1 | 2 |
| 2 |
Шаг 5.
| x1 x3 | ||
| x2 x4 | 2 1 2 1 | 2 3 |
| 1 2 | 4 |
Опишем теперь алгоритм симплекс-метода, в основе которого лежит вышеизложенный алгоритм преобразования симплекс-таблицы.
Алгоритм 3.2. (Симплекс-метод)
Шаг 1. Записать начальную симплекс-таблицу, соответствующую некоторому допустимому базисному решению x.
Шаг 2. Анализ существования решения (на основании теорем 3.1 – 3.3).
Просмотреть элементы pj последней строки:
а) если все pj > 0, то решение найдено. Положить x* = x, f* = f(x*) и закончить вычисления;
б) если существует коэффициент pj < 0, причем все aij ? 0 (т.е. все элементы j-го столбца неположительны), то задача не имеет решения и вычисления прекратить;
в) если найдется коэффициент pj < 0, причем не все aij ? 0, то найти разрешающий элемент по правилу (3.25) и перейти к шагу 3.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
