2015-06-10
697
Рассмотрим ЗЛП (1.7) на максимум.
1. Все элементы индексной строки неотрицательны. Следовательно, базисный план является оптимальным. Вычисления прекращаются.
2. Среди элементов индексной строки есть хотя бы один отрицательный, а над ним в таблице нет ни одного положительного. В этом случае целевая функция не ограничена сверху на множестве допустимых планов. Вычисления прекращаем.
3. Над каждым отрицательным элементом индексной строки есть хотя бы один положительный. Это означает, что можно построить новый базисный план с неменьшим значением целевой функции. Переходим к п.4.
4. Среди отрицательных элементов индексной строки выбираем наибольший по абсолютной величине 
. Выделяем j -йстолбец, в основании которого оказался выбранный элемент. Этот столбец будем называть ключевым. Ключевой столбец указывает на переменную 
, которую мы будем вводить в базис.
5. Для положительных элементов ключевого столбца вычисляем симплексное отношение 
и среди найденных величин выбираем наименьшее 
. Строку, которая соответствует наименьшему значению, назовем ключевой. Ей соответствует переменная, которую мы будем выводить из базиса.
|
|
|
6. Элемент, который стоит на пересечении ключевой строки и ключевого столбца, называется ключевым. Переходим к новой симплексной таблице.
7. В столбце БП выписываем новые базисные переменные.
8. Все элементы ключевой строки старой таблицы делим на ключевой элемент и записываем в соответствующую строку новой симплексной таблицы.
9. Остальные элементы новой симплексной таблицы пересчитываем по правилу прямоугольника. Из пересчитываемого элемента старой таблицы опускаем перпендикуляры на ключевую строку и ключевой элемент. Соответствующий элемент новой таблицы будет равен разности между произведением ключевого и пересчитываемого элементов и произведения элементов, которые стоят в основаниях опущенных перпендикуляров.
Пример 4. Рассмотрим M -задачу (1.8) в примере 2. Результаты вычислений запишем в виде следующей симплексной таблицы
| Базис | П | 
| 
| 
| 
| 
| 
| ||
| Шаг 0 | |||||||||
|
| 5/2 | ||||||||
| M |
| -1 | -1 | 1/1 | |||||
|
| 10/1 | ||||||||
| f(x)= | M | M-5 | -M+8 | M | |||||
| Шаг 1 | |||||||||
|
| 3/3 | ||||||||
|
| -1 | -1 | - | ||||||
|
| 9/4 | ||||||||
| f(x)= | -5 | ||||||||
| Шаг 2 | |||||||||
| -8 |
| 1/3 | 2/3 | ||||||
|
| 1/3 | -1/3 | |||||||
|
| -4/3 | -5/3 | |||||||
| f(x)= | -1 | -7 |
На нулевом шаге имеются две положительные оценки свободных переменных. Поэтому переменная вводится в базиса. Теперь определяем симплексное отношение
|
|
|
.
Минимум достигается во второй строке, поэтому из базиса выводится соответствующая ей переменная . Так как ключевой элемент равен 1, то вторая строка переписывается во вторую симплексную таблицу без изменения. Остальные элементы пересчитываем по правилу прямоугольников. Так, например
На первом шаге имеется одна положительная оценка для переменной . Эту переменную мы будем вводить в базис. При определении симплексного отношения в столбце, соответствующем этой переменной мы рассматриваем только положительные элементы 
Это означает, что из базиса уходит переменная .
На втором шаге все оценки свободных переменных отрицательны, следовательно, полученный план оптимален 
или 
, а значение целевой функции равно
.
