Задачи максимизации
Для решения задач максимизации можно использовать два подхода.
Подход1. Преобразование задачи максимизации в эквивалентную задачу минимизации путём умножения целевой функции на –1 и последующего применения симплекс–метода к задаче минимизации.
Подход 2. Как показано выше, относительные оценки в строке pj представляют изменение целевой функции f при уменьшении небазисной переменной на единицу. Отрицательный коэффициент в строке pj указывает на уменьшение f при увеличении соответствующей небазисной переменной.
Следовательно, для задач максимизации в базис должны вводится небазисные переменные xj с положительными pj, поскольку они улучшают целевую функцию. Если все коэффициенты в строке pj отрицательные или равны нулю, текущее решение оптимальное.
Пример 6.9. Решить симплекс – методом задачу:
f(x) = 2х1+3х2→max
при ограничениях
.
Решение. С помощью дополнительных неотрицательных переменных перейдем к системе уравнений. В данном случае все дополнительные переменные вводятся со знаком «+», так как все неравенства имеют вид « 
».
Получим систему ограничений в виде:
И т е р а ц и я 1.
Полагая в равенствах (6.37) свободные переменные x1, x2 равными нулю, находим 
, 
, 
, 
, т.е. базисное решение х0 = (0;0;18;16;5;21). Так как все базисные переменные в х0 положительны, данное базисное решение является допустимым (угловой точкой) и невырожденным. Используя подход 1, перейдем к задаче минимизации
f(x) = −2x1− 3x2 → min. (6.36)
С помощью равенств (6.35) и (6.36) составляем симплекс – таблицу, соответствующую угловой точке х0:
Таблица 6.9
Начальная симплекс-таблица
| Базис | Переменные | Свободный член | Оценочное отношение | |
| x1 | x2 | |||
x3
x4
 x5
x6
|
| |||
 f(x)
| -2 | -3 |
В соответствии с п.4 алгоритма проверяем критерий оптимальности. В последней строке имеются отрицательные коэффициенты. Выберем из них наибольший по модулю (-3); второй столбец разрешающий, переменная x2 перейдет в основные (этот столбец отмечен стрелкой). В соответствии с п.5 находим оценочные отношения и 
. Третья строка является разрешающей (отмечена горизонтальной стрелкой). На пересечении разрешающих строки и столбца стоит опорный элемент 
(обведен рамкой).
И т е р а ц и я 2. Строим таблицу по правилам п.6 алгоритма (табл. 6.10). В новом базисе основные переменные: 
.
Критерий оптимальности вновь не найден. Теперь первый столбец разрешающий; x1 – переход в основные, 
; первая строка разрешающая, 
- опорный элемент.
Таблица 6.10
Симплекс-таблица для угловой точки х1
| Базис | Переменные | Свободный член | Оценочное отношение | |
| x1 | x5 | |||
 x3
x4
x2
x6
| -3 -1 |
11/2
| ||
 f(x)
| -2 |
И т е р а ц и я 3. Новая симплексная таблица примет вид (табл. 6.11).
Таблица 6.11
Симплекс-таблица для угловой точки х2
| Базис | Переменные | Свободный член | Оценочное отношение | |
| x3 | x5 | |||
x1
 x4
x2
x6
| -2 -3 | -3 |
12/9
| |
 f(x)
| -3 |
И на этот раз критерий оптимальности не выполнен; второй столбец и вторая строка – разрешающие, 
- опорный элемент.
И т е р а ц и я 4. Переходим к таблице 6.12.
Таблица 6.12
Симплекс-таблица для угловой точки х3
| Базис | Переменные | Свободный член | |
| x3 | x4 | ||
| x1 x5 x2 x6 | -1/5 -2/5 2/5 3/5 | 3/5 1/5 -1/5 -9/5 | |
| f(x) | 4/5 | 3/5 |
Критерий оптимальности выполнен, значит f* = f(х*) = 24, оптимальное базисное решение х* = (6,4,0,0,1,3).
Графическое решение задачи представлено на рис. 6.10, откуда видно, что х* = (6;4), и f* = f(х*) = 24.
f(x) = 2х1 + 3х2→max
Рис. 6.10. Графическое решение задачи 6.19