Решение задачи линейного программирования симплексным методом
Алгоритм симплекс-метода рассчитан на каноническое представление задачи. Прежде чем строить исходную симплекс-таблицу, в каждом условии выявляют базисную переменную.
Задача представлена в каноническом виде, если
- критерий стремиться к максимуму,
- все условия представлены в виде равенств,
- все переменные неотрицательные.
Приведем задачу к каноническому виду:
f = 12x1+ 15x2+ 0x3+ 0x4+ 0x5® max
x1 + x2 + x3 = 6
2x1 + x2 + x4 = 10
x1 + 2x2 + x5 = 10
xi ≥ 0, i = 1, 5
Базисной называется такая переменная, которая входит только в одно из уравнений системы условий с коэффициентом +1.
Переменные x3, x4, x5 – базисные.
Таблица 2.1 – Исходная симплекс-таблица
| Базис | Св.чл. | -x1 | -х2 | -x3 | -x4 | -x5 | Q |
 x3 |  6 |  1 | 6/1 | ||||
| x4 | 10/1 | ||||||
| x5 | 10 |  10/2 | |||||
| f | -12 | -15 |
Таблица является оптимальной и последней, если все элементы строки f не отрицательны. Т.к. в таблице в строке f есть отрицательные элементы, то необходимо продолжить решение и выполнить пересчет таблицы.
Таблица 2.2 – Вторая симплекс-таблица
| Базис | Св.чл. | -x1 | -x2 | -x3 | -x4 | -x5 | Q |
 х3 | 1/2 | -1/2 | |||||
| х4 | 3/2 | -1/2 | 10/3 | ||||
| х2 | 1/2 | 1/2 | |||||
| f | -9/2 | 15/2 |
Вторая таблица тоже не оптимальная.
Таблица 2.3 – Третья симплекс-таблица
| Базис | Св.чл. | -x1 | -x2 | -x3 | -x4 | -x5 | Q |
| x1 | -1 | ||||||
| x4 | -3 | ||||||
| x2 | -1 | ||||||
| f |
В строке f все элементы положительные, следовательно, данная таблица оптимальная и последняя.
х1* = 2, x2* = 4, f * = 84.
Вывод: для получения максимальной стоимости продукции в размере 84 денежные единицы необходимо выпустить 2 машины и 4 мотоцикла.
Графическое решение задачи линейного программирования (геометрическая интерпретация процесса решения задачи симплексным методом).
Модель задачи имеет вид:
f = 12x1+ 15x2® max
x1 + x2 ≤ 6
2x1 + x2 ≤ 10
x1 + 2x2 ≤ 10
x1,2 ≥ 0
Ограничения x1,2 ≥ 0 образуют первую четверть системы координат, то есть угол х10х2, за пределы которого допустимое множество выходить не может.
Определим полуплоскости каждого условия. Берем первое условие:
x1 + x2 ≤ 6.
Заменяем на равенство: x1 + x2 = 6.
Чтобы построить эту прямую, подбором выбираем две точки:
х1 = 0 х1 = 6
х2 = 6 х2 = 0
Аналогично строим две другие прямые:
2x1 + x2 ≤ 10 x1 + 2x2 ≤ 10
2x1 + x2 = 10 x1 + 2x2 = 10
х1 = 2 х1 = 5 х1 = 0 х1 = 6
х2 = 6 х2 = 0 х2 = 5 х2 = 2
х2
 |
С
 | |||
 | |||
f * (3)
х1
f (2) (1)
Рисунок 1 – Графическое решение задачи
Допустимым множеством будет выпуклый многогранник, любая точка которого удовлетворяет всем условиям задачи и может быть ее решением. Чтобы найти оптимальное решение, нужно построить линию критерия. Для этого сначала строят вектор 
, начало которого лежит в точке (0;0), а конец – в точке (12;15) или (4;5). Перпендикулярно этому вектору в точке (0;0) проводим прямую критерия f.
В сторону вектора критерий всегда увеличивается.
Координаты точки, через которую проходит прямая f * и будут оптимальными значениями х1* и х2*:
х1* = 2, х2* = 4.
f * = 12 · 2 + 15 · 4 = 84.
Таким образом, для получения максимальной стоимости продукции в размере 84 денежные единицы необходимо выпустить 2 машины и 4 мотоцикла.
Связь итераций симплекс-метода с графиком можно наблюдать, если из каждой симплекс-таблицы взять значения переменных и найти соответствующие точки на графике.