Аналитическое решение задачи линейного программирования
Методом искусственного базиса (симплекс-методом) решить ЗЛП:
.
Переходим к канонической форме задачи, вводя в каждое ограничение- неравенство дополнительные балансовые переменные (чтобы можно было заменить знаки неравенства знаками =).
Так как в первом и четвертом ограничении нет базисных переменных, то в эти уравнения вводим фиктивные (искусственные) переменные 
. Эти же переменные войдут и в целевую функцию 
с коэффициентами - 
. Получим расширенную - задачу:
Заполняем расчётную таблицу (симплекс) метода и подсчитываем значение индексных строк (пункт 3)
.Расчётная таблица (симплекс) метода. Нулевая итерация.
| № итерации | № строки | 
| 
| 
| 
| 
| 
| 
| 
| 
| 
|
| 
| |
| 
| 
| 
| 
| 
| 
| 
| |||||||
|
| 
| -1 | ||||||||||||
|
| ||||||||||||||
|
| ||||||||||||||
|
|
| -1 | ||||||||||||
| Индексные строки | -24 M | -3M | -3M | M | M | |||||||||
| -4 | -2 | |||||||||||||
Так как наиболее отрицательное значение показателя 
расположено в столбце , то переменную вводим в базис и исключаем из базиса ту переменную, для которой критерий 
будет минимальным. Критерий минимальный для четвёртой строки расчётной таблицы, базисная переменная которой . Эту переменную выводим из базиса. Таким образом, у нас разрешающим столбцом является первый столбец ( по индексу ), а разрешающей строкой- четвёртая строка. (p=1; q=4).
Т.к. коэффициент при разрешающем элементе 
, разрешающая строка остаётся без изменения. Чтобы получить нули в первой, второй и третьей строке первого столбца, от первой строки отнимем удвоенное значение четвёртой строки, а от второй и третей строки отнимем четвёртую. При исключении из состава базисных вектора условной переменной , из расчётной таблицы исключаем и столбец 
.Пересчёт коэффициентов 
можно проводить и по правилу прямоугольника. Заполняем расчётную таблицу первой итерации
Расчётная таблица (симплекс) метода. Первая итерация
| № ите ра ции | № ст ро ки |
|
|
|
| 
| 
| 
| 
| 
|
|
|
|
|
|
|
|
|
| |||||
|
|
| -18 | -3 | -1 | |||||||
|
| |||||||||||
|
| -1 | ||||||||||
|
| --1 | ||||||||||
| Индексные строки | 18М | 3М | М | -2М | |||||||
| +56 | +6 | -4 |
В состав базисных вводим вектор 
и из базиса выводим вектор 
фиктивной переменной. Столбец также исключаем из расчётной таблицы. Новое значение разрешающей (первой ) строки получим путём деления на два всех её членов. Новые значения второй и четвёртой строк получим путём вычитания из старых значений преобразованной разрешающей строки. К третьей строке прибавляем новую разрешающую строку. (Пересчёт коэффициентов можно производить и по правилу прямоугольника.) Получим:
Расчётная таблица симплекс-метода. Вторая итерация.
| № ите ра ции | № ст ро ки |
|
|
|
|
|
|
|
|
| 
|
|
|
|
|
|
|
| ||||||
|
| -9 | -3/2 | -1/2 | ||||||||
|
| 3/2 | ½ | |||||||||
|
| ½ | ½ | |||||||||
|
| ½ | -1/2 | ----- | ||||||||
| Индексная строка | -2 |
Расчётная таблица симплекс-метода. Третья итерация.
| № ите а ции | № ст ро ки |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| ||||||
|
| -2 | ---- | |||||||||
|
| |||||||||||
|
| -1 | ||||||||||
|
| -1 | ----- | |||||||||
| Индексная строка | -4 |
Т.к. в индексной строке третьей итерации имеется отрицательный критерий 
, то полученный план не является оптимальным и его можно улучшать. В базис вводим вектор и выводим из базиса вектор 
. Разрешающая третья строка остаётся без изменений, т.к. разрешающий элемент равен 1. Первая строка преобразуется путем прибавления к её членам элементов третьей строки, умноженным на 2, от второй строки отнимаем третью строку, а к элементам четвёртой строки прибавляем элементы третьей строки. Получаем новый план (четвёртая итерация)
Расчётная таблица симплекс-метода. Четвёртая итерация.
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| ||||
|
| |||||||||
|
| -1 | ||||||||
|
| -1 | ||||||||
|
| |||||||||
| Индексная строка |
Индексная строка последней симплекс- таблицы не содержит отрицательных критериев. Получен оптимальный план. 
. Максимальное значение целевой функции 
Экономическое истолкование решения задачи может быть таким: производится 14 единиц продукции первого вида и не производится продукция второго вида. Неиспользованные остатки сырья первого, второго, третьего и четвёртого видов составляют соответственно 18; 6; 0 и 0 единиц. Максимальная прибыль от реализации продукции составляет 56 (денежных) единиц.☻