Лекция: Алгоритм симплекс-метода
1. В последней строке исходной симплекс-таблицы выбираем наименьший отрицательный элемент. Он отмечен знаком *. Столбец, соответствующий этому элементу, называется ведущим. Он определяет переменную, которая будет введена в базис на данном этапе. Это — переменная х3.
2. Вычисляют отношения свободных членов к элементам ведущего столбца (симплекс-отношение): q1=12/2=6, q1=18/2=9. Находят наименьшее неотрицательное из этих симплекс-отношений. Оно соответствует ведущей строке, которая определяет переменную, выводимую из базиса. Это — переменная х4.
3. Если все симплекс-отношения окажутся отрицательными, то задача не имеет решений (оптимум целевой функции не достигается).
4. На пересечении ведущей строки и ведущего столбца находится ведущий элемент.
5. Если имеется несколько одинаковых по величине симплекс-отношений, то выбирают любое из них. То же самое относится к отрицательным элементам последней строки симплекс-таблицы.
После нахождения ведущего элемента переходят к следующей таблице (табл. 1.3). Для этого вначале заполняем первый столбец, записывая новые базисные элементы: х3 и х5.
Далее, элементы ведущей строки табл. 1.2, за исключением симплекс-отношения, делим на ведущий элемент.
Остальные элементы ведущего столбца делаем равными нулю.
8. Оставшиеся элементы симплекс-таблицы вычисляются по правилу прямоугольника: мысленно вычерчиваем прямоугольник в табл. 1.2, одна вершина которого совпадает с разрешающим элементом, а другая — с элементом, образ которого мы ищем; остальные две вершины определяются однозначно. Тогда искомый элемент из табл. 1.3 будет равен соответствующему элементу табл. 1.2 минус дробь, в знаменателе которой стоит разрешающий элемент, а в числителе — произведение элементов из двух неиспользованных вершин прямоугольника.
Таблица 1.3.
| Базис | x1 | х2 | х3 | x4 | х5 | Свободные члены | Симплекс-отношения |
| х3 | 2,5 | 0,5 | |||||
| х5 | -4 | -1 |
Например, элемент, стоящий на пересечении строки х3 и столбца x1 находим так: 7-2×2/2=5; свободный член в строке х5: 18-2×12/2=6; первый элемент последней строки: -3-2×(-6)/2=3 и т.д.
9. Записываем соответствующий опорный план:
и снова проверяем условие оптимальности. На этот раз условие выполнено: в последней строке все элементы неотрицательны. Значит найденный опорный план оптимален. Чтобы получить оптимальный план исходной, стандартной задачи, нужно отбросить последние два элемента из: .
10. Вычисляем оптимальное значение целевой функции: L*=3×0+4×0+6×6=36.