Реферат: Графический метод и симплекс-метод решения задач линейного программирования
Мы не будем проводить вторую итерацию по схеме первой, поскольку все вычисления симплекс-метода удобнее проводить в табличном виде.
2.3 Табличная реализация простого симплекс-метода
Табличную реализацию продемонстрируем на том же примере (2.2)–(2.5).
Шаг 0 . Решение начинается с построения начальной симплекс-таблицы. Сначала заполняется правая часть таблицы с третьей колонки. В двух верхних строках записываются имена переменных задачи (x 1, ...,x 4 ) и коэффициенты целевой функции при этих переменных. Ниже записываются коэффициенты уравнений – элементы матрицы условий А , так что под переменной x 1 располагаетсястолбец A 1 , под переменной x 2 – столбец A 2 и т.д. В правый столбец заносятся правые части ограничений (числа bi > 0).
Затем находим столбцы матрицы условий, образующие единичный базис – в нашем примере это A 3 и A 4 и соответствующие им базисные переменные x 3, x 4 записываем во вторую колонку. Наконец, в первом столбце записываем коэффициенты целевой функции при базисных переменных.
Таблица 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 | |
Так как задача имеет предпочтительный вид, то значения базисных переменных равны правым частям уравнений, расположенным в последнем столбце. Поскольку небазисные переменные равны нулю, то начальный базисный план равен
x o = (0, 0, x 3 , x 4) = (0, 0, 4, 12).
Шаг 1. Для проверки плана x o на оптимальность подсчитаем симплексные оценки для небазисных переменных x 1 и x 2 по формуле
j =< cБ , Aj > – cj .
1 = < cБ , A 1 > – c 1 = 0 ·(–1) + 0 ·3 – 1 = –1.
При табличной реализации для подсчета оценки 1 надо найти сумму произведений элементов первого столбца (cБ) на соответствующие элементы столбца A 1 при небазисной переменной x 1 . Аналогично подсчитывается оценка 2 , как скалярное произведение первого столбца (cБ) на столбец при переменной x2 .
2 = < cБ , A 2 > – c 2 = 0 ·2 + 0 · 2 – 2 = –2.
Симплексные оценки записываются в последней строке симплекс-таблицы, которая называется дельта-строкой. При этом заполняются не только клетки при небазисных переменных, но и базисные клетки. Легко проверить, что для базисных единичных столбцов матрицы условий симплексные оценки равны нулю. В последней клетке строки оценок записываем значение целевой функции в точке xo . Заметим, что, так как небазисные координаты базисного плана равны нулю, то подсчет целевой функции удобно производить по формуле
f (x )= < cБ , xБ >,
перемножая скалярно первый и последний столбцы таблицы.
Так как среди оценок j естьотрицательные, то план x o – не оптимальный, и надо найти новый базисный план, заменив одну из базисных переменных на новую из числа небазисных.
Шаг 2. Поскольку обе оценки 1 и 2 < 0,то в базис можно включить любую из переменных x 1, x2 . Введем в базис переменную с наибольшей по модулю отрицательной оценкой, то есть x 2 .
Столбец симплекс-таблицы, в котором находится вводимая в базис переменная называется ведущим столбцом .
В примере ведущим будет столбец при x2 .
Шаг 3. Если в ведущем столбце все элементы отрицательны, то решения задачи не существует и max f (x ) . В примере все элементы ведущего столбца положительны, следовательно, можно найти максимальное значение x 2 , при котором одна из старых базисных переменных обратится в ноль. Напомним, что максимальное значение x2 = min{4/2, 12/2}=2.
По таблице это значение вычисляется как наименьшее из отношений компонент базисного плана (из последнего столбца) к соответствующим положительным элементам ведущего столбца.
Наименьшее отношение находится в строке с базисной переменной x3. Значит переменная x3 исключается из состава базисных переменных (x 3 = 0).
Строка, содержащая переменную, исключаемую из базиса, называется ведущей строкой.
В примере ведущей стро?