Аналитический метод. № 5. Решить симплексным методом задачу линейного программирования:

№ 5. Решить симплексным методом задачу линейного программирования:

Найти

,

при ограничениях:

Решение. Приведем эту ЗЛП к каноническому виду, для чего введем дополнительные переменные: , :

Так как определитель, составленный из коэффициентов при дополнительных переменных, не равен нулю, то эти переменные и возьмем в качестве основных.

1 шаг. Основные переменные , , , ; свободные - и . Выразим основные переменные через свободные:

Положив свободные переменные равными нулю , получим базисное решение:

.

Оно не является допустимым, так как . Следовательно, надо перевести или , или в основные, то есть увеличить.

Допустимую границу увеличения значений свободных переменных определяем как наименьшее из отношений свободных членов к коэффициенту при соответствующей свободной переменной по абсолютной величине. При этом придерживаются следующих правил:

1) , если и имеют разные знаки;

2) , если и имеют одинаковые знаки;

3) , если и ;

4) если и ;

5) , если .

Тогда:

.

Символ «» означает здесь, что в четвертом уравнении можно увеличить до бесконечности, при этом будет . Для имеем:

.

Здесь «» означает, что свободный член и коэффициент (2) при в первом уравнении имеют одинаковые знаки.

Так как , то переведем в основные . При этом в свободные переходит переменная .

2 шаг. Основные переменные - , свободные - . Выразим основные переменные через свободные:

или

Положив , получим базисное решение:

.

Оно снова не является допустимым, так как . Поэтому надо перевести в основные переменную по правилу:

.

При этом в свободные перейдет переменная .

3 шаг. Основные переменные - , свободные - и . Выразим основные переменные через свободные:

Найдем базисное решение:

.

Оно оказалось допустимым, поэтому найдем значение целевой функции:

,

а именно:

.

Это допустимое базисное решение не является оптимальным, так как и и входят в целевую функцию с отрицательными коэффициентами. Поэтому значение целевой функции можно уменьшить за счет увеличения значений свободных переменных. Для определенности переведем в основные переменную , так как .

Вычислив

,

переведем в свободные переменную .

4 шаг. Основные переменные - , свободные - и . Тогда:

и целевая функция примет вид:

.

Вычислим значение целевой функции при базисном решении:

,

а именно

.

Видно, что действительно значение целевой функции улучшается (уменьшается).

Это допустимое решение также не является оптимальным, так как значение целевой функции можно улучшить за счет переменной , имеющей отрицательный коэффициент .

Вычислив

,

переведем в основные, а в свободные.

5 шаг. Основные переменные - , свободные - и . Тогда

с целевой функцией:

,

и базисным решением

.

Так как все коэффициенты при переменных в положительны, то невозможно уменьшить далее значение целевой функции. Следовательно,

,

и оптимальное решение:

Ответ: , , .

Для определения максимума линейной функции на каждом шаге увеличивают целевую функцию за счет той свободной переменной, которая входит в с положительным коэффициентом. И решение будет оптимальным, если все коэффициенты при переменных в целевой функции будут отрицательными.

№ 6. В условиях №5 решить задачу на максимум.

Решение. На третьем шаге была найдена целевая функция:

.

Так как все коэффициенты при свободных переменных отрицательны, то дальнейшее увеличение значений целевой функции невозможно. Следовательно

,

и

,

а именно,

, .

Ответ: ; ; .

Дата добавления: 2014-12-07