183441 (743571), страница 3
Текст из файла (страница 3)
∆3 = < сБ, A3 > – c3 = 1∙0 + 0∙1 + 2∙0 – 0= 0,
∆4 = < сБ, A4 > – c4 = 1∙(-1) + 0∙5 + 2∙1 – 4= -3,
∆5 = < сБ, A5 > – c5 = 1∙0 + 0∙0 + 2∙1 – 2= 0.
Так как оценка ∆4 < 0, то базисный план x0 не оптимален. Заметим, что симплексные оценки, соответствующие базисным переменным, всегда равны нулю, так что достаточно проверять только небазисные оценки.
2.2 Реализация симплекс-метода на примере
Продемонстрируем применение симплекс-метода на примере. Рассмотрим каноническую задачу ЛП
| f(x) = x1+ 2x2 +0 x3 + 0 x4→ max | (2.2) |
| –x1+ 2x2+ x3 = 4, | (2.3) |
| 3 x1 +2x2 + x4 = 12, | (2.4) |
| xj ≥ 0, j = 1,2,3,4. | (2.5) |
Матрица условий A = (A1, A2, A3, A4), где
Целевой вектор c =(c1, c2, c3, c4) = (1, 2, 0, 0); вектор правых частей b=(b1, b2) = (4, 12).
Шаг 0. Нахождение начальной угловой точки (базисного плана).
Задача имеет предпочтительный вид, так как правые части уравнений положительны, а столбцы матрицы условий A3, A4 образуют единичную подматрицу. Значит начальная базисная матрица 
= (A3, A4); x3 и x4 – базисные переменные, x1 и x2 - небазисные переменные, cБ = (c3, c4) = = (0, 0).
Начальный базисный план имеет вид x0 = (0, 0, x3, x4) = (0, 0, 4, 12); f(xo) = 0.
Шаг 1. Проверка базисного плана на оптимальность.
Подсчитаем симплексные оценки для небазисных переменных по формуле (5.1)
1 = < cБ, A1 > – c1 = 0 ·(–1) + 0 ·3 – 1 = –1.
2 = < cБ, A2 > – c2 = 0 ·2 + 0 · 2 – 2 = –2.
Так как оценки отрицательны, то план x – не оптимален. Будем искать новый базисный план (смежную угловую точку) с большим значением целевой функции.
Шаг 2. Нахождение переменной вводимой в базис.
Целевую функцию можно увеличить, если ввести в состав базисных переменных (сделать положительной) одну из небазисных переменных x1 или x2, поскольку обе оценки j < 0. Обычно в состав базисных вводят небазисную переменную с наибольшей по модулю отрицательной оценкой, поэтому будем вводить в базис переменную x2.
Шаг 3. Определение переменной выводимой из базиса.
После ввода в базис переменной x2 новый план будет иметь вид
x' = (0, x2, x3, x4).
Этот план не является базисным, так как он содержит только одну нулевую координату, значит надо сделать нулевой (исключить из базиса) одну из переменных x3 или x4. Подставим координаты плана x' = (0, x2, x3, x4) в ограничения задачи. Получим
2x2+ x3 = 4,
2x2 + x4 = 12.
Выразим отсюда базисные переменные x3 и x4 через переменную x2, вводимую в базис.
| x3 = 4 – 2x2, | (2.6) |
| x4 = 12 – 2x2. | (2.7) |
Так переменные x3 и x4 должны быть неотрицательны, получим систему неравенств
| 4 – 2x2 ≥ 0, | (2.8) |
| 12 – 2x2 ≥ 0. | (2.9) |
Чем больше значение x2, тем больше возрастает целевая функция. Найдем максимальное значение новой базисной переменной, не нарушающее ограничения задачи, то есть удовлетворяющее условиям (2.8), (2.9).
Перепишем последние неравенства в виде
2x2 ≤ 4,
2x2 ≤ 12,
откуда максимальное значение x2 = min { 4/2, 12/2 } = 2. Подставляя это значение в выражения (2.6), (2.7) для x3 и x4, получаем x3 = 0. Следовательно x3 выводится из базиса.
Шаг 4. Определение координат нового базисного плана.
Новый базисный план (смежная угловая точка) имеет вид
x' = (0, x2, 0, x4)
Базис этой точки состоит из столбцов A2 и A4, так что 
= (A2, A4). Этот базис не является единичным, так как вектор A2 = (2,2), и следовательно задача (2.2)–(2.5) не имеет предпочтительного вида относительно нового базиса. Преобразуем условия задачи (2.3), (2.4) таким образом, чтобы она приняла предпочтительный вид относительно новых базисных переменных x2, x4, то есть чтобы переменная x2 входила в первое уравнение с коэффициентом, равным единице, и не присутствовала во втором уравнении. Перепишем уравнения задачи
– x1+ 2 x2+ x3 = 4, (p1)
3x1 +2 x2 + x4 = 12. (p2)
Поделим первое уравнение на коэффициент при x2. Получим новое уравнение 
= p1 / 2, эквивалентное исходному
– 1/2 x1+ x2+ 1/2 x3 = 2. ( )
Используем это уравнение, которое назовем разрешающим, для исключения переменной x2 из второго уравнения. Для этого надо уравнение умножить на 2 и вычесть из p2. Получим 
= p2 – 2 = p2 – p1:
4 x1 – x3 + x4 = 8. ( )
В итоге получили новое "предпочтительное" представление исходной задачи относительно новых базисных переменных x2, x4:
f(x) = x1 + 2 x2 + 0 x3 + 0 x4 max
– 1/2 x1+ x2+ 1/2 x3 = 2 ( )
4 x1 – x3 + x4 = 8 ( )
xj 0, j = 1,2,3,4
Подставляя сюда представление нового базисного плана x1 = (0, x2, 0, x4), сразу найдем его координаты, так как значения базисных переменных равны правым частям уравнений
x' = (0, 2, 0, 8); f(x1)=4.
На этом завершается первая итерация простого симплекс-метода. Далее процесс решения задачи продолжается с шага 1, состоящем в проверке найденного плана на оптимальность. Решение заканчивается тогда, когда все симплексные оценки текущего базисного плана окажутся неотрицательными.
Мы не будем проводить вторую итерацию по схеме первой, поскольку все вычисления симплекс-метода удобнее проводить в табличном виде.
2.3 Табличная реализация простого симплекс-метода
Табличную реализацию продемонстрируем на том же примере (2.2)–(2.5).
Шаг 0. Решение начинается с построения начальной симплекс-таблицы. Сначала заполняется правая часть таблицы с третьей колонки. В двух верхних строках записываются имена переменных задачи (x1,...,x4) и коэффициенты целевой функции при этих переменных. Ниже записываются коэффициенты уравнений – элементы матрицы условий А, так что под переменной x1 располагается столбец A1, под переменной x2 – столбец A2 и т.д. В правый столбец заносятся правые части ограничений (числа bi > 0).
Затем находим столбцы матрицы условий, образующие единичный базис – в нашем примере это A3 и A4 – и соответствующие им базисные переменные x3, x4 записываем во вторую колонку. Наконец, в первом столбце записываем коэффициенты целевой функции при базисных переменных.
Таблица 1 - Начальная симплекс-таблица
| СБ | Базисные переменные | с1=1 | с2=2 | с3=0 | с4=0 | Значения базисных перем. (xБ=b) | |||
| x1 | x2 | x3 | x 4 | ||||||
| c3=0 | x3 | a11=-1 | a12=2 | a13=1 | a14=0 | b1=4 | |||
| c4=0 | x4 | a21=3 | a22=2 | a23=0 | a24=1 | b2=12 | |||
| Строка оценок j | 1= -1 | 2= -2 | 3= 0 | 4= 0 | f(x)= 0 | ||||
Так как задача имеет предпочтительный вид, то значения базисных переменных равны правым частям уравнений, расположенным в последнем столбце. Поскольку небазисные переменные равны нулю, то начальный базисный план равен
xo = (0, 0, x3, x4) = (0, 0, 4, 12).
Шаг 1. Для проверки плана xo на оптимальность подсчитаем симплексные оценки для небазисных переменных x1 и x2 по формуле
j=< cБ, Aj > – cj.
1 = < cБ, A1 > – c1 = 0 ·(–1) + 0 ·3 – 1 = –1.
При табличной реализации для подсчета оценки 1 надо найти сумму произведений элементов первого столбца (cБ) на соответствующие элементы столбца A1 при небазисной переменной x1. Аналогично подсчитывается оценка 2, как скалярное произведение первого столбца (cБ) на столбец при переменной x2.
2 = < cБ, A2 > – c2 = 0 ·2 + 0 · 2 – 2 = –2.
Симплексные оценки записываются в последней строке симплекс-таблицы, которая называется дельта-строкой. При этом заполняются не только клетки при небазисных переменных, но и базисные клетки. Легко проверить, что для базисных единичных столбцов матрицы условий симплексные оценки равны нулю. В последней клетке строки оценок записываем значение целевой функции в точке xo. Заметим, что, так как небазисные координаты базисного плана равны нулю, то подсчет целевой функции удобно производить по формуле
f(x)= < cБ, xБ >,
перемножая скалярно первый и последний столбцы таблицы.
Так как среди оценок j есть отрицательные, то план xo – не оптимальный, и надо найти новый базисный план, заменив одну из базисных переменных на новую из числа небазисных.
Шаг 2. Поскольку обе оценки 1 и 2 < 0, то в базис можно включить любую из переменных x1, x2. Введем в базис переменную с наибольшей по модулю отрицательной оценкой, то есть x2.
Столбец симплекс-таблицы, в котором находится вводимая в базис переменная называется ведущим столбцом.
В примере ведущим будет столбец при x2.
Шаг 3. Если в ведущем столбце все элементы отрицательны, то решения задачи не существует и max f(x) . В примере все элементы ведущего столбца положительны, следовательно, можно найти максимальное значение x2, при котором одна из старых базисных переменных обратится в ноль. Напомним, что максимальное значение x2 = min{4/2, 12/2}=2.
По таблице это значение вычисляется как наименьшее из отношений компонент базисного плана (из последнего столбца) к соответствующим положительным элементам ведущего столбца.
Наименьшее отношение находится в строке с базисной переменной x3. Значит переменная x3 исключается из состава базисных переменных (x3 = 0).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
