Линейное программирование 2 3 (стр. 3 из 6)
Тогда любая точка минимума
представима в виде 
где
. Минимальное значение целевой функции 
Ответ: бесконечное множество решений
, где и 
.Задача 7 (16.216)
Решить задачу линейного программирования симплекс - методом, находя начальную угловую точку методом искусственного базиса.
Решение:
Матрица системы имеет вид
.Ее ранг равен 3. Введем дополнительные переменные
и запишем условие вспомогательной задачи линейного программирования для рассматриваемого случая:
Считая дополнительные переменные
базисными, запишем симплекс таблицу этой задачи, соответствующую угловой точке 
:  |  |  |  | ||
 | 3 | -2 | 3 | 2 | 9 |
 | 1 | 2 | -1 | 1 | 0 |
 | -1 | -1 | 2 | 1 | 6 |
| -3 | 1 | -4 | -4 | -15 |
Произведем преобразования исходной симплекс-таблицы симплекс-методом следующим образом:
1) смотрим на нижнюю строку – выбираем тот столбец, в котором нижний элемент отрицательный, если таких столбцов несколько, то выбираем любой (в нашем случае выбираем первый столбец
);2) далее смотрим на последний и выбранный столбцы – сравниваем отношения элементов последнего и выбранного столбцов (в выбранном столбце берем только положительные числа), и выбираем тот элемент выбранного столбца, где отношение элементов будет наименьшим (в нашем случае 9/3 и 0/1, так как второе отношение наименьшее, следовательно, опорным элементом будет 1);
3) меняем местами переменные
и 
, остальные переменные оставляем на своих местах;4) на место опорного элемента ставим отношение 1/(опорный элемент);
5) на остальных местах разрешающей строки записываем соответствующие элементы исходной таблицы, деленные на опорный элемент;
6) на свободные места разрешающего столбца ставим со знаком минус соответствующие элементы исходной таблицы, деленные на опорный элемент;
7) оставшиеся свободные места в новой симплекс-таблице заполняем построчно следующим образом: из строки элементов исходной таблицы вычитаем произведение ее элемента из разрешающего столбца на уже заполненную разрешающую строку новой таблицы.
Производя преобразования симплекс-метода, получим такую последовательность симплекс-таблиц:
| |  |  |  | ||
 | -3 | -8 | 6 | -1 | 9 |
| | 1 | 2 | -1 | 1 | 0 |
 | 1 | 1 | 1 | 2 | 6 |
| 3 | 7 | -7 | -1 | -15 |
 |  | | | ||
| | -2 | -6 | 5 | 1 | 9 |
 | 1 | 2 | -1 | 1 | 0 |
| | -1 | -3 | 3 | -2 | 6 |
| 4 | 9 | -8 | 1 | -15 |
| | | | | ||
| | -2/5 | -6/5 | 1/5 | 1/5 | 9/5 |
| | 3/5 | 4/5 | 1/5 | 6/5 | 9/5 |
| | 1/5 | 3/5 | -3/5 | -13/5 | 3/5 |
| 4/5 | -3/5 | 8/5 | 13/5 | -3/5 |
| | |  | | ||
 | 0 | 2 | -1 | -5 | 3 |
| | 1/3 | -4/3 | 1 | 14/3 | 1 |
| | 1/3 | 5/3 | -1 | -13/3 | 1 |
| 1 | 1 | 1 | 0 | 0 |
В нижней строке последней симплекс-таблицы нет отрицательных элементов, следовательно, минимум вспомогательной целевой функции достигнут и
есть угловая точка допустимого множества исходной задачи линейного программирования, тогда