Случай 2

Случай 1

При перемещении прямой с₁ x + с₂y= d «вход» или «выход» (как на рисунке) произойдет по стороне многоугольника. Это случится, если в многоугольнике есть стороны, параллельные прямой с₁х + с₂у = d . В этом случае точек «выхода» (« входа») бесчисленное множество, а именно – любая точка отрезка АВ. Это означает, что целевая функция принимает максимальное (минимальное) значение не в одной точке, а во всех точках, лежащих на соответствующей стороне многоугольника D.

Рассмотрим случай, когда область допустимых значений неограниченна. В случае неограниченной области целевая функция может быть задана таким образом, что соответствующая ей прямая не имеет точки «выхода» (или «входа»). Тогда максимальное значение функции (минимальное) не достигается никогда – говорят, что функция не ограничена.

Геометрическая интерпретация, которой мы пользовались при решении задач линейного программирования, перестает быть пригодной для этой цели при числе свободных переменных n - m > 3, а затруднительна уже при n - m = 3.

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

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

Пример. Решить следующую задачу ЛП в канонической форме симплекс-методом.

(5)

(6)

x_i ≥ 0, i = 1,…,6 (7)

Говорят, что задача ЛП имеет каноническую форму, если все ограничения (кроме условий неотрицательности переменных) имеют вид равенств, а все свободные члены неотрицательны. Так что мы имеем задачу в канонической форме.

Идея симплекс-метода заключается в следующем. Сначала нужно найти некоторую (начальную) вершину многогранника допустимых решений (начальное допустимое базисное решение). Затем нужно проверить это решение на оптимальность. Если оно оптимально, то решение найдено; если нет, то перейти к другой вершине многогранника и вновь проверить на оптимальность. Ввиду конечности вершин многогранника (следствие конечности ограничений задачи ЛП) за конечное число "шагов" мы найдем искомую точку минимума или максимума. Надо заметить, что при переходе от одной вершины к другой значение целевой функции убывает (в задаче на минимум) или возрастает (в задаче на максимум).

Таким образом, идея симплекс-метода основывается на трех свойствах задачи ЛП.

Пример решения задачи симплексным методом в Excel

Заполните данные

Загрузите файл шаблон для проверки в Excel

Откройте его в MS Excel

Мышкой или с помощью клавиатуры перейдите к ячейке G4

Выполните команду Сервис / Поиск решения

Если данная команда отсутствует в списке, необходимо выполнить команду Сервис/Надстройки

В диалоговом окне укажите:

вид поиска (максимальное значение)

в поле изменяя ячейки: $B$2:$D$2

в поле Ограничения добавьте заданные ограничения

Поле должно иметь следующее содержание:

$B$2:$D$2>=0

$G$6<=$F$6

$G$7<=$F$7

$G$8<=$F$8

Нажмите на кнопку Выполнить

Значение переменных Xi может различаться, но целевая функция F(x) должна иметь такое же значение.

Чтобы решить задачу линейного программирования с помощью Excel, необходимо выполнить следующее:

1. ввести исходные числовые коэффициенты;
2. ввести формулы для подсчета целевой функции и левых частей ограничений;
3. найти решение.

Рассмотрим эту последовательность шагов на примере следующей задачи линейного программирования.

1. Заполним ячейки электронной таблицы следующим образом

Для значений переменных выбираем ячейки В2:D2, для значения целевой функции – ячейку Е3, для коэффициентов левых частей ограничений – ячейки В6:D6, для правых частей – ячейки G6:G10. Текст в других ячейках является комментарием и на решение задачи не влияет.

2. В ячейках Е3, Е6:Е10 поместим формулы для вычисления целевой функции и левых частей ограничений. Если перейти в режим представления формул, тогда таблица принимает вид

1. После ввода данных и вычислительных формул переходим к решению задачи.

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

В поле для ввода диалогового окна помещаем следующую информацию:

Установить целевую ячейку: $E$3

Равной минимальному значению

Изменяя ячейки: $B$2:$D$2

Ограничения

$Е$6 ³ $G$6

$Е$7 £ $G$7

$Е$8 ³ $G$8

$Е$9 £ $G$9

$Е$10 ³ $G$10

Выбираем команду Выполнить – на экране появляется диалоговое окно Результаты поиск решения и уведомление: Решение найдено. Все ограничения и условия оптимальности выполнены. В соответствующих ячейках таблицы находим минимальное значение целевой функции z = 4,5 и значения переменных х1 = 0, х2 = 0,75, х3 = 1.

Однако, решение задачи не всегда можно найти. Если система неравенств несовместная или целевая функция неограниченна, то в окне Результаты поиск решения появляется уведомление Поиск не может найти подходящего решения или Значения целевой ячейки не сходятся.

С помощью окна Результаты поиск решения можно получить также отчеты, которые Excel помещает на отдельных листах. Например, Отчет по результатам состоит из трех таблиц: в первой таблице приводится значение целевой функции до начала вычислений и в результате решения задачи; в другой – значения переменных до начала вычислений и в результате решения задачи; в третьей – результаты оптимального решения для ограничений и граничные условий.