Симплексный метод решения злп. Пример решения задачи
Пример №3. Решение задачи линейного программирования симплекс методом.
Нахождение наибольшего значения функции (искусственный базис)
Данное решение является образцом работы программы, представленной на сайте.
Найти наибольшее значение функции
x 1 ≥ 0 x 2 ≥ 01. Свободные члены системы должны быть неотрицательными.
Данное условие выполнено.
2. Каждое ограничение системы должно представлять собой уравнение.
| x 1 | - | 2 | x 2 | ≤ | 4 | |||
| x 1 | - | x 2 | ≥ | 1 | ||||
| x 1 | + | x 2 | ≤ | 8 |
| x 1 | - | 2 | x 2 | + | S 1 | = | 4 | ||||||||||
| x 1 | - | x 2 | - | S 2 | = | 1 | |||||||||||
| x 1 | + | x 2 | + | S 3 | = | 8 |
S 1 ≥ 0, S 2 ≥ 0, S 3 ≥ 0. Введенные переменные S 1 , S 2 , S 3 , называются балансовыми переменными.
3. Нахождение начального базиса и значения функции F, которое соответствует найденному начальному базису.
Что такое базис?
Переменная называется базисной для данного уравнения, если она входит в данное уравнение с коэффициентом один
и не входит в оставшиеся уравнения (при условии, что в правой части уравнения стоит положительное число).
Если в каждом уравнении присутствует базисная переменная, тогда говорят, что в системе присутствует базис.
Переменные, которые не являются базисными, называются свободными.
В чем заключается идея симплекс метода?
Каждому базису соответствует единственное значение функции. Одно из них является наибольшим значением функции F.
Мы будем переходить от одного базиса к другому, получая значение функции F не меньше имеющегося.
Очевидно, количество возможных базисов для любой задачи число не очень большое.
Следовательно, рано или поздно, ответ будет получен.
Как осуществляется переход от одного базиса к другому?
Запись решения удобнее вести в виде таблиц. Каждая строка таблицы эквивалентна уравнению системы. Выделенная строка состоит из коэффициентов функции (см. таблицу ниже). Это позволяет не переписывать переменные каждый раз, что существенно экономит время.
B выделенной строке выбираем наибольший положительный коэффициент (можно выбрать любой положительный).
Это необходимо для того, чтобы получить значение функции F не меньше имеющегося.
Выбран столбец.
Для положительных коэффициентов выбранного столбца считаем отношение Θ и выбираем наименьшее значение.
Это необходимо для того, чтобы после преобразования столбец свободных членов остался положительным.
Выбрана строка.
Определен элемент, который будет базисным. Далее считаем.
В нашей системе есть базис?
| x 1 | - | 2 | x 2 | + | S 1 | = | 4 | ||||||||||
| x 1 | - | x 2 | - | S 2 | = | 1 | |||||||||||
| x 1 | + | x 2 | + | S 3 | = | 8 |
Базиса нет, т.е. мы не можем начать решение.
Придется его найти. Для этого решим вспомогательную задачу.
Добавим искусственную переменную в то уравнение, где нет базисной переменной.
| x 1 | - | 2 | x 2 | + | S 1 | = | 4 | |||||||||||||
| x 1 | - | x 2 | - | S 2 | + | R 1 | = | 1 | ||||||||||||
| x 1 | + | x 2 | + | S 3 | = | 8 |
R 1 ≥ 0. Введенная переменная R 1 , называется искусственной переменной.
Введем в рассмотрение функцию W и будем искать ее наименьшее значение.
Алгоритм нахождения наименьшего значения функции W имеет только одно отличие от алгоритма, рассмотренного выше.
О нем Вам придется догадаться самостоятельно.
| x 1 | x 2 | S 1 | S 2 | S 3 | R 1 | св. член | Θ |
| 1 | -2 | 1 | 0 | 0 | 0 | 4 | 4: 1 = 4 |
| 1 | -1 | 0 | -1 | 0 | 1 | 1 | 1: 1 = 1 |
| 1 | 1 | 0 | 0 | 1 | 0 | 8 | 8: 1 = 8 |
| -1 | 1 | 0 | 1 | 0 | 0 | W - 1 | |
| 0 | -1 | 1 | 1 | 0 | -1 | 3 | |
| 1 | -1 | 0 | -1 | 0 | 1 | 1 | |
| 0 | 2 | 0 | 1 | 1 | -1 | 7 | |
| 0 | 0 | 0 | 0 | 0 | 1 | W - 0 |
Приравниваем свободные переменные нулю. Устно находим значения базисных переменных. (см. таблицу)
Функция W выражена через свободные переменные. Поэтому значение функции W, для данного решения, можно найти мгновенно. (см. выделенную строку таблицы)
| x 2 = 0 S 2 = 0 R 1 = 0 x 1 = 1 S 1 = 3 S 3 = 7 |
=> W - 0 = 0 => W = 0 |
Среди коэффициентов выделенной строки нет отрицательных. Следовательно, найдено наименьшее значение функции W.
Получен базис без использования искусственной переменной. Что и требовалось.
Столбец, соответствующий искусственной переменной можно вычеркнуть.
В итоге, наша система выглядит следующим образом:
| - | x 2 | + | S 1 | + | S 2 | = | 3 | ||||||||||
| x 1 | - | x 2 | - | S 2 | = | 1 | |||||||||||
| 2 | x 2 | + | S 2 | + | S 3 | = | 7 |
| F | = | - | x 1 | + | 3 | x 2 |
|
|
≤ = ≥ |
≤ = ≥ |
≤ = ≥ |
×
Предупреждение
Очистить все ячейки?
Закрыть Очистить
Инструкция ввода данных. Числа вводятся в виде целых чисел (примеры: 487, 5, -7623 и т.д.), десятичных чисел (напр. 67., 102.54 и т.д.) или дробей. Дробь нужно набирать в виде a/b, где a и b (b>0) целые или десятичные числа. Примеры 45/5, 6.6/76.4, -7/6.7 и т.д.
Симплекс метод
Примеры решения ЗЛП симплекс методом
Пример 1. Решить следующую задачу линейного программирования:
 |
Правая часть ограничений системы уравнений имеет вид:
Запишем текущий опорный план:
 |
Данный опорный план не является оптимальным, так как в последней строке есть отрицательные элементы. Самый большой по модулю отрицательный элемент (-3), следовательно в базис входит вектор x
при 
. min
(40:6, 28:2)=20/3 соответствует строке 1. Из базиса выходит вектор x
3 . Сделаем исключение Гаусса для столбца x
2 , учитывая, что ведущий элемент соответствует строке 1. Обнулим все элементы этого столбца, кроме ведущего элемента. Для этого сложим строки строки 2, 3, 4 со строкой 1, умноженной на -1/3, 1/6, 1/2, соответственно. Далее делим строку с ведущим элементом на ведущий элемент.
Данный опорный план не является оптимальным, так как в последней строке есть отрицательный элемент (-3), следовательно в базис входит вектор x
1 . Определяем, какой вектор выходит из базиса. Для этого вычисляем 
при 
. min(44/3:11/3, 62/3:5/3)=4 соответствует строке 2. Из базиса выходит вектор x
4 . Сделаем исключение Гаусса для столбца x
1 , учитывая, что ведущий элемент соответствует строке 2. Обнулим все элементы этого столбца, кроме ведущего элемента. Для этого сложим строки строки 1, 3, 4 со строкой 2, умноженной на 1/11, -5/11, 9/11, соответственно. Далее делим строку с ведущим элементом на ведущий элемент.
Симплекс таблица примет следующий вид:
Текущий опорный план является оптимальным, так как в строках 4 под переменными 
нет отрицательных элементов.
Решение можно записать так: 
.
Значение целевой функции в данной точке: F
(X
)=
.
Пример 2. Найти максимум функции
Р е ш е н и е.
Базисные векторы x 4 , x 3 , следовательно, все элементы в столбцах x 4 , x 3 , ниже горизонтальной линии должны быть нулевыми.
Обнулим все элементы столбца x 4 , кроме ведущего элемента. Для этого сложим строку 3 со строкой 1, умноженной на 4. Обнулим все элементы столбца x 3 , кроме ведущего элемента. Для этого сложим строку 3 со строкой 2, умноженной на 1.
Симплекс таблица примет вид:
Данный опорный план не является оптимальным, так как в последней строке есть отрицательный элемент (-11), следовательно в базис входит вектор x
2 . Определяем, какой вектор выходит из базиса. Для этого вычисляем 
при 
. Все следовательно целевая функция неограничена сверху. Т.е. задача линейного программирования неразрешима.
Примеры решения ЗЛП методом искусственного базиса
Пример 1. Найти максимум функции
Р е ш е н и е. Так как количество базисных векторов должен быть 3, то добавляем искусственное переменное, а в целевую функцию добавляем это переменное, умноженное на −M, где M, очень большое число:
 |
Матрица коэффициентов системы уравнений имеет вид:
Базисные векторы следовательно, все элементы в столбцах ниже горизонтальной линии должны быть нулевыми.
Обнулим все элементы столбца кроме ведущего элемента. Для этого сложим строку 5 со строкой 3, умноженной на -1.
Симплекс таблица примет вид:
Данный опорный план не является оптимальным, так как в последней строке есть отрицательные элементы. Самый большой по модулю отрицательный элемент (-5), следовательно в базис входит вектор Определяем, какой вектор выходит из базиса. Для этого вычисляем 
при 
соответствует строке 3. Из базиса выходит вектор Сделаем исключение Гаусса для столбца учитывая, что ведущий элемент соответствует строке 3. Обнулим все элементы этого столбца, кроме ведущего элемента. Для этого сложим строки строку 5 со строкой 3, умноженной на 1. Далее делим строку с ведущим элементом на ведущий элемент.
Симплекс таблица примет следующий вид:
Данный опорный план не является оптимальным, так как в последней строке есть отрицательные элементы. Самый большой по модулю отрицательный элемент (-3), следовательно в базис входит вектор Определяем, какой вектор выходит из базиса. Для этого вычисляем 
при 
соответствует строке 1. Из базиса выходит вектор x
2 . Сделаем исключение Гаусса для столбца x
1 , учитывая, что ведущий элемент соответствует строке 1. Обнулим все элементы этого столбца, кроме ведущего элемента. Для этого сложим строки строки 2, 3, 4 со строкой 1, умноженной на 3/2, -1/10, 3/2, соответственно. Далее делим строку с ведущим элементом на ведущий элемент.
Симплекс таблица примет следующий вид:
Данный опорный план не является оптимальным, так как в последней строке есть отрицательные элементы. Самый большой по модулю отрицательный элемент (-13/2), следовательно в базис входит вектор x
3 . Определяем, какой вектор выходит из базиса. Для этого вычисляем 
при 
соответствует строке 3. Из базиса выходит вектор x
5 . Сделаем исключение Гаусса для столбца x
3 , учитывая, что ведущий элемент соответствует строке 3. Обнулим все элементы этого столбца, кроме ведущего элемента. Для этого сложим строки строки 1, 2, 4 со строкой 3, умноженной на 5/3, 25/9, 65/9, соответственно. Далее делим строку с ведущим элементом на ведущий элемент.
Симплекс таблица примет следующий вид:
Текущий опорный план является оптимальным, так как в строках 4−5 под переменными нет отрицательных элементов.
Решение исходной задачи можно записать так:
Пример 2. Найти оптимальный план задачи линейного программирования:
Матрица коэффициентов системы уравнений имеет вид:
Базисные векторы x 4 , x 5 , x 6 , следовательно, все элементы в столбцах x 4 , x 5 , x 6 , ниже горизонтальной линии должны быть нулевыми.
Обнулим все элементы столбца x 4 , кроме ведущего элемента. Для этого сложим строку 4 со строкой 1, умноженной на -1. Обнулим все элементы столбца x 5 , кроме ведущего элемента. Для этого сложим строку 5 со строкой 2, умноженной на -1. Обнулим все элементы столбца x 6 , кроме ведущего элемента. Для этого сложим строку 5 со строкой 3, умноженной на -1.
Симплекс таблица примет вид:
В строке 5 элементы, соответствующие переменным x 1 , x 2 , x 3 , x 4 , x 5 , x 6 неотрицательны, а число находящийся в пересечении данной строки и столбца x 0 отрицательнo. Тогда исходная задача не имеет опорного плана. Следовательно она неразрешима.
При решении симплекс-методом могут возникать следующие ситуации:
- Вырожденность;
- Зацикливание;
- Альтернативные оптимальные решения;
- Неограниченные решения;
- Отсутствие допустимых решений.
Вырожденность
Если нет однозначной идентификации переменной (в случае одинаковых отношений), которая подлежит исключению из базиса, то выбор такой переменной можно сделать произвольно. Однако на следующей итерации по крайней мере, одна из базисных переменных должна быть равна нулю. В этом случае говорят, что новое решение является вырожденным. Появление вырожденного решения объясняется присутствием в модели, по крайней мере, одного избыточного ограничения. Для устранения подобной ситуации применяется правило Креко .Зацикливание
Данная ситуация возникает в случае ухудшения значения целевой функции по сравнению с предыдущими итерацией. В общем случае может возникнуть зацикливание (циклическое повторение одинаковых операций, не улучшающих значение целевой функции, и не приводящих к завершению вычислительного процесса). Имеются специальные приемы, которые предотвращают зацикливание.Альтернативные оптимальные решения
Если линия уровня целевой функции параллельна прямой (или гиперплоскости), соответствующей связывающему ограничению, то могут возникнуть альтернативные оптимальные планы X * . В этом случае целевая функция принимает одно и тоже оптимальное значение в некоторой совокупности точек пространства решений.Пример
. Определим максимальное значение целевой функции F(X) = 2x 1 + 4x 2 при следующих условиях-ограничений.
x 1 + 2x 2 x 1 + x 2 Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме
).
В 1-м неравенстве смысла (1x 1 + 2x 2 + 1x 3 + 0x 4 = 5
1x 1 + 1x 2 + 0x 3 + 1x 4 = 4
| A = |
|
Базисные переменные
x 3 , x 4 ,
Полагая, что свободные переменные
X1 = (0,0,5,4)
Базисное решение
| Базис | B | x 1 | x 2 | x 3 | x 4 |
| x 3 | 5 | 1 | 2 | 1 | 0 |
| x 4 | 4 | 1 | 1 | 0 | 1 |
| F(X0) | 0 | -2 | -4 | 0 | 0 |
Итерация №0 .
.
.
.
и из них выберем наименьшее:
min (5: 2 , 4: 1) = 2 1 / 2
Разрешающий элемент равен (2) и находится на пересечении ведущего столбца и ведущей строки.
| Базис | B | x 1 | x 2 | x 3 | x 4 | min |
| x 3 | 5 | 1 | 2 | 1 | 0 | |
| x 4 | 4 | 1 | 1 | 0 | 1 | 4 |
| F(X1) | 0 | -2 | -4 | 0 | 0 | 0 |
4. Пересчет симплекс-таблицы .
Вместо переменной x 3 в план 1 войдет переменная x 2 .
Строка, соответствующая переменной x 2 в плане 1, получена в результате деления всех элементов строки x 3 плана 0 на разрешающий элемент РЭ=2
В остальных клетках столбца x 2 плана 1 записываем нули.
Таким образом, в новом плане 1 заполнены строка x 2 и столбец x 2 .
НЭ = СЭ - (А*В)/РЭ
СТЭ - элемент старого плана, РЭ - разрешающий элемент (2), А и В - элементы старого плана, образующие прямоугольник с элементами СТЭ и РЭ.
| B | x 1 | x 2 | x 3 | x 4 |
| 5: 2 | 1: 2 | 2: 2 | 1: 2 | 0: 2 |
| 4-(5 1):2 | 1-(1 1):2 | 1-(2 1):2 | 0-(1 1):2 | 1-(0 1):2 |
| 0-(5 -4):2 | -2-(1 -4):2 | -4-(2 -4):2 | 0-(1 -4):2 | 0-(0 -4):2 |
| Базис | B | x 1 | x 2 | x 3 | x 4 |
| x 2 | 2 1 / 2 | 1 / 2 | 1 | 1 / 2 | 0 |
| x 4 | 1 1 / 2 | 1 / 2 | 0 | -1 / 2 | 1 |
| F(X1) | 10 | 0 | 0 | 2 | 0 |
1. Проверка критерия оптимальности .
Среди значений индексной строки нет отрицательных. Поэтому эта таблица определяет оптимальный план задачи.
| Базис | B | x 1 | x 2 | x 3 | x 4 |
| x 2 | 2 1 / 2 | 1 / 2 | 1 | 1 / 2 | 0 |
| x 4 | 1 1 / 2 | 1 / 2 | 0 | -1 / 2 | 1 |
| F(X2) | 10 | 0 | 0 | 2 | 0 |
Оптимальный план можно записать так:
x 2 = 2 1 / 2
F(X) = 4 2 1 / 2 = 10
Анализ оптимального плана .
В оптимальный план вошла дополнительная переменная x 4 . Следовательно, при реализации такого плана имеются недоиспользованные ресурсы 2-го вида в количестве 1 1 / 2
В индексной строке в 1-ом столбце нулевое значение. В столбце, содержащем этот нуль, имеется хотя бы один положительный элемент. Следовательно, задача имеет множество оптимальных планов.
Покажем это на примере. Свободную переменную, соответствующую указанному столбцу, вносим в базис (вместо x 2), выполнив соответствующие этапы алгоритма.
После преобразований получаем новую таблицу:
| Базис | B | x 1 | x 2 | x 3 | x 4 |
| x 1 | 5 | 1 | 2 | 1 | 0 |
| x 4 | -1 | 0 | -1 | -1 | 1 |
| F(X) | 10 | 0 | 0 | 2 | 0 |
В результате получен второй оптимальный план с другим набором базисных переменных.
Неограниченные решения
Когда при решении задач линейного программирования значения переменных постоянно растет без нарушения ограничений, то это свидетельствует о том, что пространство допустимых решений, по крайней мере, в одном направлении, неограниченно. В таких случаях целевую функцию можно сделать бесконечно большой (при решении задачи на mах и бесконечно малой (при min). Тогда говорят, что оптимальное значение целевой функции не ограничено.Пример
. Определим максимальное значение целевой функции F(X) = x 1 + 2x 2 при следующих условиях-ограничений.
x 1 - x 2 x 1 Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме
).
В 1-м неравенстве смысла (1x 1 -1x 2 + 1x 3 + 0x 4 = 10
1x 1 + 0x 2 + 0x 3 + 1x 4 = 20
Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:
| A = |
|
Базисные переменные это переменные, которые входят только в одно уравнение системы ограничений и притом с единичным коэффициентом.
Экономический смысл дополнительных переменных : дополнительные перемены задачи ЛП обозначают излишки сырья, времени, других ресурсов, остающихся в производстве данного оптимального плана.
Решим систему уравнений относительно базисных переменных:
x 3 , x 4 ,
Полагая, что свободные переменные равны 0, получим первый опорный план:
X1 = (0,0,10,20)
Базисное решение называется допустимым, если оно неотрицательно.
| Базис | B | x 1 | x 2 | x 3 | x 4 |
| x 3 | 10 | 1 | -1 | 1 | 0 |
| x 4 | 20 | 1 | 0 | 0 | 1 |
| F(X0) | 0 | -1 | -2 | 0 | 0 |
Переходим к основному алгоритму симплекс-метода.
Итерация №0 .
1. Проверка критерия оптимальности .
Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.
2. Определение новой базисной переменной .
В качестве ведущего выберем столбец, соответствующий переменной x 1 , так как это наибольший коэффициент по модулю.
3. Определение новой свободной переменной .
Вычислим значения D i по строкам как частное от деления: b i / a i1
и из них выберем наименьшее:
min (10: 1 , 20: 1) = 10
Следовательно, 1-ая строка является ведущей.
| Базис | B | x 1 | x 2 | x 3 | x 4 | min |
| x 3 | 10 | 1 | -1 | 1 | 0 | 10 |
| x 4 | 20 | 1 | 0 | 0 | 1 | 20 |
| F(X1) | 0 | -1 | -2 | 0 | 0 | 0 |
4. Пересчет симплекс-таблицы .
Формируем следующую часть симплексной таблицы.
Вместо переменной x 3 в план 1 войдет переменная x 1 .
Строка, соответствующая переменной x 1 в плане 1, получена в результате деления всех элементов строки x 3 плана 0 на разрешающий элемент РЭ=1
На месте разрешающего элемента в плане 1 получаем 1.
В остальных клетках столбца x 1 плана 1 записываем нули.
Таким образом, в новом плане 1 заполнены строка x 1 и столбец x 1 .
Все остальные элементы нового плана 1, включая элементы индексной строки, определяются по правилу прямоугольника.
Для этого выбираем из старого плана четыре числа, которые расположены в вершинах прямоугольника и всегда включают разрешающий элемент РЭ.
НЭ = СЭ - (А*В)/РЭ
СТЭ - элемент старого плана, РЭ - разрешающий элемент (1), А и В - элементы старого плана, образующие прямоугольник с элементами СТЭ и РЭ.
Представим расчет каждого элемента в виде таблицы:
| B | x 1 | x 2 | x 3 | x 4 |
| 10: 1 | 1: 1 | -1: 1 | 1: 1 | 0: 1 |
| 20-(10 1):1 | 1-(1 1):1 | 0-(-1 1):1 | 0-(1 1):1 | 1-(0 1):1 |
| 0-(10 -1):1 | -1-(1 -1):1 | -2-(-1 -1):1 | 0-(1 -1):1 | 0-(0 -1):1 |
Получаем новую симплекс-таблицу:
| Базис | B | x 1 | x 2 | x 3 | x 4 |
| x 1 | 10 | 1 | -1 | 1 | 0 |
| x 4 | 10 | 0 | 1 | -1 | 1 |
| F(X1) | 10 | 0 | -3 | 1 | 0 |
Итерация №1 .
1. Проверка критерия оптимальности .
Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.
2. Определение новой базисной переменной .
В качестве ведущего выберем столбец, соответствующий переменной x 2 , так как это наибольший коэффициент по модулю.
3. Определение новой свободной переменной .
Вычислим значения D i по строкам как частное от деления: b i / a i2
и из них выберем наименьшее:
min (- , 10: 1) = 10
Следовательно, 2-ая строка является ведущей.
Разрешающий элемент равен (1) и находится на пересечении ведущего столбца и ведущей строки.
| Базис | B | x 1 | x 2 | x 3 | x 4 | min |
| x 1 | 10 | 1 | -1 | 1 | 0 | - |
| x 4 | 10 | 0 | 1 | -1 | 1 | 10 |
| F(X2) | 10 | 0 | -3 | 1 | 0 | 0 |
4. Пересчет симплекс-таблицы .
Формируем следующую часть симплексной таблицы.
Вместо переменной x 4 в план 2 войдет переменная x 2 .
Строка, соответствующая переменной x 2 в плане 2, получена в результате деления всех элементов строки x 4 плана 1 на разрешающий элемент РЭ=1
На месте разрешающего элемента в плане 2 получаем 1.
В остальных клетках столбца x 2 плана 2 записываем нули.
Таким образом, в новом плане 2 заполнены строка x 2 и столбец x 2 .
Все остальные элементы нового плана 2, включая элементы индексной строки, определяются по правилу прямоугольника.
Представим расчет каждого элемента в виде таблицы:
| B | x 1 | x 2 | x 3 | x 4 |
| 10-(10 -1):1 | 1-(0 -1):1 | -1-(1 -1):1 | 1-(-1 -1):1 | 0-(1 -1):1 |
| 10: 1 | 0: 1 | 1: 1 | -1: 1 | 1: 1 |
| 10-(10 -3):1 | 0-(0 -3):1 | -3-(1 -3):1 | 1-(-1 -3):1 | 0-(1 -3):1 |
Получаем новую симплекс-таблицу:
| Базис | B | x 1 | x 2 | x 3 | x 4 |
| x 1 | 20 | 1 | 0 | 0 | 1 |
| x 2 | 10 | 0 | 1 | -1 | 1 |
| F(X2) | 40 | 0 | 0 | -2 | 3 |
Окончательный вариант симплекс-таблицы:
| Базис | B | x 1 | x 2 | x 3 | x 4 |
| x 1 | 20 | 1 | 0 | 0 | 1 |
| x 2 | 10 | 0 | 1 | -1 | 1 |
| F(X3) | 40 | 0 | 0 | -2 | 3 |
Последняя строка содержит отрицательные элементы. Решения не существует. Пространство допустимых решений в одном направлении неограниченно.
Отсутствие допустимых решений
Если ограничения модели одновременно выполняться не могут, то ОДР пустое. Если модель содержит ограничения в виде равенств или в виде неравенств ≥, то обычно используются искусственные переменные, не гарантирующие получения допустимого решения задачи в ее первоначальной постановке. Несмотря на введение штрафа за использование в целевой функции искусственных переменных, если в оптимальном решении хотя бы одна из искусственных переменных будет иметь положительное решение, то задача не имеет допустимых решений.Пример
. Определим максимальное значение целевой функции F(X) = 3x 1 + 2x 2 при следующих условиях-ограничений.
2x 1 + x 2 3x 1 + 4x 2 =>12
Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме
).
В 1-м неравенстве смысла () вводим базисную переменную x 4 со знаком минус.
2x 1 + 1x 2 + 1x 3 + 0x 4 = 2
3x 1 + 4x 2 + 0x 3 -1x 4 = 12
Введем искусственные переменные
x: в 2-м равенстве вводим переменную x 5 ;
2x 1 + 1x 2 + 1x 3 + 0x 4 + 0x 5 = 2
3x 1 + 4x 2 + 0x 3 -1x 4 + 1x 5 = 12
Для постановки задачи на максимум целевую функцию запишем так:
F(X) = - Mx 5 → max
Полученный базис называется искусственным, а метод решения называется методом искусственного базиса.
Причем искусственные переменные не имеют отношения к содержанию поставленной задачи, однако они позволяют построить стартовую точку, а процесс оптимизации вынуждает эти переменные принимать нулевые значения и обеспечить допустимость оптимального решения.
Из уравнений выражаем искусственные переменные:
x 5 = 12-3x 1 -4x 2 +x 4
F(X) = - M(12-3x 1 -4x 2 +x 4) → max
или
F(X) = (3M)x 1 +(4M)x 2 +(-M)x 4 +(-12M) → max
Введем новую переменную x 0 = 3x 1 + 4x 2 .
Выразим базисные переменные через небазисные.
x 0 = -12+3x 1 +4x 2 -x 4
x 3 = 2-2x 1 -x 2
x 5 = 12-3x 1 -4x 2 +x 4
Переходим к основному алгоритму симплекс-метода.
Поскольку задача решается на максимум, то переменную для включения в текущий план выбирают по максимальному положительному числу в уравнении для x 0 .
1. Проверка критерия оптимальности
.
В выражении для x 0 присутствуют отрицательные элементы. Следовательно, текущий план неоптимален
2. Определение новой базисной переменной
.
max(3,4,0,-1,0) = 4
x 0 = -12+3x 1 +4x 2 -x 4
x 3 = 2-2x 1 -x 2
x 5 = 12-3x 1 -4x 2 +x 4
В качестве новой переменной выбираем x 2 .
3. Определение новой свободной переменной
.
Вычислим значения D i по всем уравнениям для этой переменной: b i / a i2
и из них выберем наименьшее:
min (2: 1 , 12: 4) = 2
Вместо переменной x 3 в план войдет переменная x 2 .
4. Пересчет всех уравнений
.
Выразим переменную x 2 через x 3
x 2 = 2-2x 1 -x 3
и подставим во все выражения.
x 0 = -12+3x 1 +4(2-2x 1 -x 3)-x 4
x 5 = 12-3x 1 -4(2-2x 1 -x 3)+x 4
После приведения всех подобных, получаем новую систему, эквивалентную прежней:
x 0 = -4-5x 1 -4x 3 -x 4
x 2 = 2-2x 1 -x 3
x 5 = 4+5x 1 +4x 3 +x 4
Полагая небазисные переменные x = (2, 5) равными нулю, получим новый допустимый вектор и значение целевой функции:
x = (5, 0, 4, 1, 0), x 0 = -4
x 0 = -4-5x 1 -4x 3 -x 4
x 2 = 2-2x 1 -x 3
x 5 = 4+5x 1 +4x 3 +x 4
На этом первый этап симплекс-метода завершен. Переходим ко второму этапу
. Удаляем переменные с искусственными переменными.
x 2 = 2-2x 1 -x 3
x 5 = 4+5x 1 +4x 3 +x 4
Выразим базисные переменные:
x 2 = 2-2x 1 -x 3
которые подставим в целевую функцию:
F(X) = 3x 1 + 2(2-2x 1 -x 3)
или
F(X) = 4-x 1 -2x 3
Получаем новую систему переменных.
x 0 = 4-x 1 -2x 3
x 2 = 2-2x 1 -x 3
x 5 = 4+5x 1 +4x 3 +x 4
Переменных для включения в новый базис не найдено.
Выражение для x 0 не содержит положительных элементов. Найден оптимальный план.
Окончательный вариант системы уравнений:
x 0 = 4-x 1 -2x 3
x 2 = 2-2x 1 -x 3
x 5 = 4+5x 1 +4x 3 +x 4
Так как в оптимальном решении присутствуют искусственные переменные (x5 > 0), то задача не имеет допустимого решения.
Данный метод является методом целенаправленного перебора опорных решений задачи линейного программирования. Он позволяет за конечное число шагов либо найти оптимальное решение, либо установить, что оптимальное решение отсутствует.
Основное содержание симплексного метода заключается в следующем:- Указать способ нахождения оптимального опорного решения
- Указать способ перехода от одного опорного решения к другому, на котором значение целевой функции будет ближе к оптимальному, т.е. указать способ улучшения опорного решения
- Задать критерии, которые позволяют своевременно прекратить перебор опорных решений на оптимальном решении или следать заключение об отсутствии оптимального решения.
Алгоритм симплексного метода решения задач линейного программирования
Для того, чтобы решить задачу симплексным методом необходимо выполнить следующее:- Привести задачу к каноническому виду
- Найти начальное опорное решение с "единичным базисом" (если опорное решение отсутствует, то задача не имеет решение ввиду несовместимости системы ограничений)
- Вычислить оценки разложений векторов по базису опорного решения и заполнить таблицу симплексного метода
- Если выполняется признак единственности оптимального решения, то решение задачи заканчивается
- Если выполняется условие существования множества оптимальных решений, то путем простого перебора находят все оптимальные решения
Пример решения задачи симплексным методом
Пример 26.1Решить симплексным методом задачу:
Решение:
Приводим задачу к каноническому виду.
Для этого в левую часть первого ограничения-неравенства вводим дополнительную переменную x 6 с коэффициентом +1. В целевую функцию переменная x 6 входит с коэффицентом ноль (т.е. не входит).
Получаем:
Находим начальное опорное решение. Для этого свободные (неразрешенные) переменные приравниваем к нулю х1 = х2 = х3 = 0.
Получаем опорное решение Х1 = (0,0,0,24,30,6) с единичным базисом Б1 = (А4, А5, А6).
Вычисляем оценки разложений векторов условий по базису опорного решения по формуле:
Δ k = C б X k — c k
- C б = (с 1 , с 2 , ... , с m) — вектор коэффициентов целевой функции при базисных переменных
- X k = (x 1k , x 2k , ... , x mk) — вектор разложения соответствующего вектора А к по базису опорного решения
- С к — коэффициент целевой функции при переменной х к.
Оценки векторов входящих в базис всегда равны нулю. Опорное решение, коэффиценты разложений и оценки разложений векторов условий по базису опорного решения записываются в симплексную таблицу :
Сверху над таблицей для удобства вычислений оценок записываются коэффициенты целевой функции. В первом столбце "Б" записываются векторы, входящие в базис опорного решения. Порядок записи этих векторов соответствует номерам разрешенных неизвестных в уравнениях ограничениях. Во втором столбце таблицы "С б " записываются коэффициенты целевой функции при базисных переменных в том же порядке. При правильном расположении коэффициентов целевой функции в столбце "С б " оценки единичных векторов, входящих в базис, всегда равных нулю.
В последней строке таблицы с оценками Δ k в столбце "А 0 " записываются значения целевой функции на опорном решении Z(X 1).
Начальное опорное решение не является оптимальным, так как в задаче на максимум оценки Δ 1 = -2, Δ 3 = -9 для векторов А 1 и А 3 отрицательные.
По теореме об улучшении опорного решения, если в задаче на максимум хотя бы один вектор имеет отрицательную оценку, то можно найти новое опорное решение, на котором значение целевой функции будет больше.
Определим, введение какого из двух векторов приведет к большему приращению целевой функции.
Приращение целевой функции находится по формуле: .
Вычисляем значения параметра θ 01 для первого и третьего столбцов по формуле:
Получаем θ 01 = 6 при l = 1, θ 03 = 3 при l = 1 (таблица 26.1).
Находим приращение целевой функции при введении в базис первого вектора ΔZ 1 = — 6*(- 2) = 12, и третьего вектора ΔZ 3 = — 3*(- 9) = 27.
Следовательно, для более быстрого приближения к оптимальному решению необходимо ввести в базис опорного решения вектор А3 вместо первого вектора базиса А6, так как минимум параметра θ 03 достигается в первой строке (l = 1).
Производим преобразование Жордана с элементом Х13 = 2, получаем второе опорное решение Х2 = (0,0,3,21,42,0) с базисом Б2 = (А3, А4, А5). (таблица 26.2)
Это решение не является оптимальным, так как вектор А2 имеет отрицательную оценку Δ2 = — 6. Для улучшение решения необходимо ввести вектор А2 в базис опорного решения.
Определяем номер вектора, выводимого из базиса. Для этого вычисляем параметр θ 02 для второго столбца, он равен 7 при l = 2. Следовательно, из базиса выводим второй вектор базиса А4. Производим преобразование Жордана с элементом х 22 = 3, получаем третье опорное решение Х3 = (0,7,10,0,63,0) Б2 = (А3, А2, А5) (таблица 26.3).
Это решение является единственным оптимальным, так как для всех векторов, не входящих в базис оценки положительные
Δ 1 = 7/2, Δ 4 = 2, Δ 6 = 7/2.
Ответ: max Z(X) = 201 при Х = (0,7,10,0,63).
Метод линейного программирования в экономическом анализе
Метод линейного программирования дает возможность обосновать наиболее оптимальное экономическое решение в условиях жестких ограничений, относящихся к используемым в производстве ресурсам (основные фонды, материалы, трудовые ресурсы). Применение этого метода в экономическом анализе позволяет решать задачи, связанные главным образом с планированием деятельности организации. Данный метод помогает определить оптимальные величины выпуска продукции, а также направления наиболее эффективного использования имеющихся в распоряжении организации производственных ресурсов.
При помощи этого метода осуществляется решение так называемых экстремальных задач, которое заключается в нахождении крайних значений, то есть максимума и минимума функций переменных величин.
Этот период базируется на решении системы линейных уравнений в тех случаях, когда анализируемые экономические явления связаны линейной, строго функциональной зависимостью. Метод линейного программирования используется для анализа переменных величин при наличии определенных ограничивающих факторов.
Весьма распространено решение так называемой транспортной задачи с помощью метода линейного программирования. Содержание этой задачи заключается в минимизации затрат, осуществляемых в связи с эксплуатацией транспортных средств в условиях имеющихся ограничений в отношении количества транспортных средств, их грузоподъемности, продолжительности времени их работы, при наличии необходимости обслуживания максимального количества заказчиков.
Кроме этого, данный метод находит широкое применение при решении задачи составления расписания. Эта задача состоит в таком распределении времени функционирования персонала данной организации, которое являлось бы наиболее приемлемым как для членов этого персонала, так и для клиентов организации.
Данная задача заключается в максимизации количества обслуживаемых клиентов в условиях ограничений количества имеющихся членов персонала, а также фонда рабочего времени.
Таким образом, метод линейного программирования весьма распространен в анализе размещения и использования различных видов ресурсов, а также в процессе планирования и прогнозирования деятельности организаций.
Все же математическое программирование может применяться и в отношении тех экономических явлений, зависимость между которыми не является линейной. Для этой цели могут быть использованы методы нелинейного, динамического и выпуклого программирования.
Нелинейное программирование опирается на нелинейный характер целевой функции или ограничений, либо и того и другого. Формы целевой функции и неравенств ограничений в этих условиях могут быть различными.
Нелинейное программирование применяется в экономическом анализе в частности, при установлении взаимосвязи между показателями, выражающими эффективность деятельности организации и объемом этой деятельности, структурой затрат на производство, конъюнктурой рынка, и др.
Динамическое программирование базируется на построении дерева решений. Каждый ярус этого дерева служит стадией для определения последствий предыдущего решения и для устранения малоэффективных вариантов этого решения. Таким образом, динамическое программирование имеет многошаговый, многоэтапный характер. Этот вид программирования применяется в экономическом анализе с целью поиска оптимальных вариантов развития организации как в настоящее время, так и в будущем.
Выпуклое программирование представляет собой разновидность нелинейного программирования. Этот вид программирования выражает нелинейный характер зависимости между результатами деятельности организации и осуществляемыми ей затратами. Выпуклое (иначе вогнутое) программирование анализирует выпуклые целевые функции и выпуклые системы ограничений (точки допустимых значений). Выпуклое программирование применяется в анализе хозяйственной деятельности с целью минимизации затрат, а вогнутое — с целью максимизации доходов в условиях имеющихся ограничений действия факторов, влияющих на анализируемые показатели противоположным образом. Следовательно, при рассматриваемых видах программирования выпуклые целевые функции минимизируются, а вогнутые — максимизируются.
Симплекс метод - это метод последовательного перехода от одного базисного решения (вершины многогранника решений) системы ограничений задачи линейного программирования к другому базисному решению до тех пор, пока функция цели не примет оптимального значения (максимума или минимума).
Симплекс-метод является универсальным методом, которым можно решить любую задачу линейного программирования , в то время, как графический метод пригоден лишь для системы ограничений с двумя переменными.
Симплекс метод был предложен американским математиком Р.Данцигом в 1947 году, с тех пор для нужд промышленности этим методом нередко решаются задачи линейного программирования с тысячами переменных и ограничений.
Перед тем, как перейти к алгоритму симплекс метода, несколько определений .
Всякое неотрицательное решение системы ограничений называется допустимым решением .
Пусть имеется система m ограничений с n переменными (m n).
Допустимым базисным решением является решение, содержащее m неотрицательных основных (базисных ) переменных и n - m неосновных . (небазисных, или свободных ) переменных. Неосновные переменные в базисном решении равны нулю, основные же переменные, как правило, отличны от нуля, то есть являются положительными числами.
Любые m переменных системы m линейных уравнений с n переменными называются основными , если определитель из коэффициентов при них отличен от нуля. Тогда остальные n - m переменных называются неосновными (или свободными ).
Алгоритм симплекс метода
- Шаг 1 . Привести задачу линейного программирования к канонической форме. Для этого перенести свободные члены в правые части (если среди этих свободных членов окажутся отрицательные, то соответствующее уравнение или неравенство умножить на - 1) и в каждое ограничение ввести дополнительные переменные (со знаком "плюс", если в исходном неравенстве знак "меньше или равно", и со знаком "минус", если "больше или равно").
- Шаг 2 . Если в полученной системе m уравнений, то m переменных принять за основные, выразить основные переменные через неосновные и найти соответствующее базисное решение. Если найденное базисное решение окажется допустимым, перейти к допустимому базисному решению.
- Шаг 3 . Выразить функцию цели через неосновные переменные допустимого базисного решения. Если отыскивается максимум (минимум) линейной формы и в её выражении нет неосновных переменных с отрицательными (положительными) коэффициентами, то критерий оптимальности выполнен и полученное базисное решение является оптимальным - решение окончено. Если при нахождении максимума (минимума) линейной формы в её выражении имеется одна или несколько неосновных переменных с отрицательными (положительными) коэффициентами, перейти к новому базисному решению.
- Шаг 4 . Из неосновных переменных, входящих в линейную форму с отрицательными (положительными) коэффициентами, выбирают ту, которой соответствует наибольший (по модулю) коэффициент, и переводят её в основные. Переход к шагу 2.
Важные условия
В отдельных статьях разобраны некоторые особые случаи: когда максимум целевой функции - бесконечность , когда система не имеет ни одного решения , и когда оптимальное решение - не единственное .
Далее разберём всё же типичный пример, когда система ограничений является совместной и имеется конечный оптимум, причём единственный. Разновидностью симплекс-метода является распределительный метод решения транспортной задачи .
Симплекс метод с симплексными таблицами
Путём построения симплексных таблиц решить задачу линейного программирования намного проще, чем путём алгебраических преобразований, который показан в следующем параграфе. Симплексные таблицы очень наглядны. Существует несколько разновидностей правил работы с симплексными таблицами. Мы разберём правило, которое чаще всего называется правилом ведущего столбца и ведущей строки.
Будет нелишним открыть в новом окне пособие Действия с дробями : их, дробей в задачах на симплекс-метод, мягко говоря, хватает.
Пример.
Вводим добавочные неотрицательные переменные и сводим данную систему неравенств к эквивалентной ей системе уравнений
.
Это было сделано с соблюдением следующего правила: если в первоначальном ограничении знак "меньше или равно", то добавочную переменную нужно прибавлять, а если "больше или равно", то добавочную переменную нужно отнимать.
Введённые добавочные переменные принимаем за основные (базисные). Тогда и - неосновные (свободные) переменные.
Выразив основные (базисные) переменные через неосновные (свободные), получим
Функцию цели также выразим через неосновные (свободные) переменные:
Из коэффициентов при переменных (неизвестных) построим первую симплексную таблицу.
| Таблица 1 | ||||
| Базисные неизвестные | Свободные члены | Свободные неизвестные | Вспомогательные коэффициенты | |
| X1 | X2 | |||
| X3 | -2 | 1 | -2 | |
| X4 | -4 | -1 | -1 | |
| X5 | 2 | 1 | -1 | |
| X6 | 6 | 0 | 1 | |
| F | 0 | -1 | -2 | |
Последнюю строку таблицы, в которой записаны функция цели и коэффициенты при свободных переменных в ней, будем называть в индексной строкой.
Полученное решение не оптимально, так как в индексной строке коэффициенты при свободных переменных отрицательны. То есть оптимальным будет то решение, в котором коэффициенты при свободных переменных в индексной строке будут больше или равны нулю.
Для перехода к следующей таблице найдём наибольшее (по модулю) из чисел и . Это число 2. Поэтому ведущий столбец - тот столбец, в котором записано
Для определения ведущей строки находим минимум отношений свободных членов к элементам ведущего столбца, причём если в числителе положительное число, а в знаменателе отрицательное, отношение считается равным бесконечности.
.
Поэтому ведущая строка - та, в которой записано
Ведущим элементом, таким образом, является -2.
Составляем вторую симплексную таблицу.
Новый базисный элемент вписываем первой строкой, а столбец, в котором стояло , вписываем новую свободную переменную
Заполняем первую строку. Для этого все числа, стоящие в ведущей строке таблицы 1, делим на ведущий элемент и записываем в соответствующий столбец первой строки таблицы 2, кроме числа, стоящего в ведущем столбце, куда записывается величина, обратная ведущему элементу (то есть, единица, делённая на ведущий элемент).
Заполняем столбец вспомогательных коэффициентов. Для этого числа ведущего столбца таблицы 1, кроме ведущего элемента, записываем с противоположными знаками в графу вспомогательных коэффициентов таблицы 2.
| Таблица 2 | ||||
| Базисные неизвестные | Свободные члены | Свободные неизвестные | Вспомогательные коэффициенты | |
| X1 | X3 | |||
| X2 | 1 | -1/2 | -1/2 | |
| X4 | -3 | -3/2 | -1/2 | 1 |
| X5 | 3 | 1/2 | -1/2 | 1 |
| X6 | 5 | 1/2 | 1/2 | -1 |
| F | 2 | -2 | -1 | 2 |
Кто ещё не открыл в новом окне пособие Действия с дробями , может сделать это сейчас, поскольку самое время.
Для получения остальных строк таблицы 2 числа, уже стоящие в первой строке этой таблицы, умножаем на вспомогательный коэффициент, стоящий в заполняемой строке, и к результату прибавляем число из таблицы 1, стоящее в той же строке при соответствующей переменной.
Например, для получения свободного члена второй строки число 1 умножаем на 1 и прибавляем
из таблицы 1 число -4. Получаем -3. Коэффициент при
во второй строке находим так же: 
.
Так как в предыдущей таблице отсутствует столбец с новой свободной переменной ,
то коэффициент второй строки в столбце новой свободной переменной
будет 
(то есть из таблицы
1 прибавляем 0, так как в таблице 1 столбец с
отсутствует).
Так же заполняется и индексная строка:
Полученное таким образом решение вновь не оптимально, так как в индексной строке коэффициенты при свободных переменных вновь отрицательны.
Для перехода к следующей симплексной таблице найдём наибольшее (по модулю) из чисел и , то есть, модулей коэффициентов в индексной строке. Это число 2. Поэтому ведущий столбец - тот столбец, в котором записано .
Для поиска ведущей строки найдём минимум отношений свободных членов к элементам ведущей строки. Получаем:
.
Следовательно, ведущая строка - та, в которой записано , а ведущим элементом является -3/2.
Составляем третью симплексную таблицу
Новую базисную переменную записываем первой строкой. В столбец, в котором было , вписываем новую свободную переменную .
Первая строка:
Вспомогательные коэффициенты:
| Таблица 3 | ||||
| Базисные неизвестные | Свободные члены | Свободные неизвестные | Вспомогательные коэффициенты | |
| X4 | X3 | |||
| X1 | 2 | -2/3 | 1/3 | |
| X2 | 2 | -1/3 | -1/3 | 1/2 |
| X5 | 2 | 1/3 | -2/3 | -1/2 |
| X6 | 4 | 1/3 | 1/3 | -1/2 |
| F | 6 | -4/3 | -1/3 | 2 |
Полученное решение вновь не оптимальное, поскольку коэффициенты при свободных неизвестных в индексной строке вновь отрицательные.
Для перехода к четвёртой симплексной таблице найдём наибольшее из чисел и . Это число .
Следовательно, ведущий столбец - тот, в котором записано .
Минимум модулей отношений свободных членов к элементам ведущего столбца:
.
Поэтому ведущая строка - та, в которой записано , а ведущий элемент 1/3.
В четвёртой симплексной таблице новую базисную переменную записываем первой строкой. В столбец, где было , записываем новую свободную переменную .
Первая строка:
Вспомогательные коэффициенты:
| Таблица 4 | ||||
| Базисные неизвестные | Свободные члены | Свободные неизвестные | Вспомогательные коэффициенты | |
| X5 | X3 | |||
| X4 | 6 | 3 | -2 | |
| X1 | 6 | 2 | -1 | 2/3 |
| X2 | 4 | 1 | -1 | 1/3 |
| X6 | 2 | -1 | 1 | -1/3 |
| F | 14 | 4 | -3 | 4/3 |
Вычисление остальных строк на примере второй строки:
Полученное решение так же не оптимально, но оно уже лучше предыдущих, так как один из коэффициентов при свободных переменных в индексной строке неотрицателено.
Для улучшения плана перейдём к следующей симплексной таблице.
Найдём наибольшее из чисел 4 и . Это число 4. Следовательно, ведущий столбец .
Для нахождения ведущей строки найдём
.
Следовательно, ведущая строка - та, в которой записано . Но и уже были вместе среди свободных переменных. Поэтому для перевода очередной переменной из свободных в базисные выбираем другой ведущий столбец - тот, в котором записано .
Для нахождения ведущей строки найдём
.
Следовательно, ключевая строка - та, в которой записано , а ведущий элемент 1.
В пятой симплексной таблице новую базисную переменную записываем первой строкой. В столбец, где было , записываем новую свободную переменную .
Первая строка:
Вспомогательные коэффициенты:
| Таблица 5 | ||||
| Базисные неизвестные | Свободные члены | Свободные неизвестные | Вспомогательные коэффициенты | |
| X5 | X6 | |||
| X3 | 2 | -1 | 1 | |
| X4 | 10 | 2 | ||
| X1 | 8 | 1 | ||
| X2 | 6 | 1 | ||
| F | 20 | 1 | 3 | 3 |
Попробуем сразу узнать, не является ли решение оптимальным. Поэтому для остальных строк вычислим только свободные члены (чтобы узнать значения базисных переменных при равенстве свободных переменных нулю) и коэффициенты при свободных переменных в индексной строке.
Свободные члены:
Во второй строке ;
В третьей строке ;
В четвёртой строке .
Индексная строка:
Смотрим в симплексную таблицу 5. Видим, что получено оптимальное решение, так как коэффициенты при свободных неизвестных в индексной строке неотрицательны.
Симплекс метод с алгебраическими преобразованиями
Решим алгебраическими преобразованиями тот же пример, что и в предыдущем параграфе.
Следует отметить, что при решении этой разновидностью симплекс метода лучше не записывать функцию
цели в виде ,
так как при этом легко запутаться в знаках. Но в этом случае пункт алгоритма, определяющий критерий
оптимальности, будет модифицирован следующим образом.
Если отыскивается максимум (минимум) линейной формы и в её выражении нет неосновных переменных с положительными (отрицательными) коэффициентами, то критерий оптимальности выполнен и полученное базисное решение является оптимальным - решение окончено. Если при нахождении максимума (минимума) линейной формы в её выражении имеется одна или несколько неосновных переменных с положительными (отрицательными) коэффициентами, перейти к новому базисному решению.
Пример. Найти максимум функции при ограничениях
Шаг I. Вводим добавочные неотрицательные переменные и сводим данную систему неравенств к эквивалентной ей системе уравнений
.
Введённые добавочные переменные принимаем за основные, так как в этом случае базисное решение системы легко находится. Тогда и - неосновные переменные.
Выразив основные переменные через неосновные, получим
Следовательно, данному разбиению переменных на основные и неосновные
соответствует базисное решение 
,
которое является недопустимым (две переменные отрицательны), а поэтому оно не оптимальное.
От этого базисного решения перейдём к улучшенному.
Чтобы решить, какую переменную следует перевести из неосновных в основные, рассмотрим любое из двух имеющихся уравнений последней системы с отрицательными свободными членами, например второе. Оно показывает, что в основные переменные можно перевести и , так как в этом уравнении они имеют положительные коэффициенты (следовательно, при их увеличении, а это произойдёт, если переведём любую из них в основные переменные, переменная увеличится).
Попробуем перевести в основные переменную . Чтобы установить, какую переменную следует перевести из основные в неосновные, найдём абсолютную величину наименьшего отношения свободных членов системы к коэффициентам при . Имеем . Оно получено из третьего уравнения, показывающего, что в неосновные нужно перевести переменную , которая в исходном базисном решении положительна. Следовательно, полученное базисное решение, как и исходное, содержит две отрицательные компоненты, т. е. при переходе к такому базисному решению улучшения не произойдёт.