logo search
Лаб

3.4.1. Пример решение задачи линейного программирования

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

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

Пусть дана целевая функция Z=5x1 -3x2 - 4x3 max, и ограничения:

x1-x2+x3 1

x1+3x3 8

-2x1+3x2+x3 1

xi 0

Найти оптимальное решение.

Алгоритм решения задачи:

  1. Загружаем MS Excel

  2. В ячейки B3, C3, D3 заносим соответственно коэффициенты первого ограничения; в ячейки B4, C4, D4 – коэффициенты второго ограничения; и аналогично, в ячейки B5, C5, D5 – коэффициенты третьего.

  3. В ячейки Е3, Е4, Е5 соответственно заносим правые части первого, второго и третьего ограничений. Для ограничений x1 0, x2 0 и x3 0 ( т.е. xi 0) занесем в ячейку Е6 ноль.

  4. Далее заносим коэффициенты целевой функции соответственно в ячейки B6, C6 и D6.

  5. Установим неизвестные x1 , x2 , x3 соответственно в ячейках B7, C7 и D7, придав им первоначально нулевые значения.

  6. В ячейку F3 заносим формулу первого ограничения, которая выглядит следующим образом: = B3*B7+C3*C7+D3*D7. Для ее получения, устанавливаем курсор в строке формул, и перемножаем первый коэффициент ограничения (B3), с x1(В7), прибавляем к нему второй коэффициент ограничения (C3) умноженный на x2 (С7), плюс третий коэффициент ограничения (D3) умноженный на х3 (D7). Для записи формулы в ячейку нажимаем клавишу Enter. Аналогично в ячейки F4 и F5 заносим формулы второго и третьего ограничений.

  7. В ячейку F7 заносится формула целевой функции: =B6*B7+C6*C7+D6*D7. Исходные данные приведены на рисунке 3.20.

  8. В меню «Сервис» и выбираем пункт «Поиск решения» (рисунок 3.21).

Рисунок 3.20. - Лист MS Excel с первоначальными данными.

Рисунок 3.21. - Окно «Поиск решения».

  1. В поле «Установить целевую ячейку» устанавливаем абсолютную ссылку на ту ячейку, в которую была занесена формула целевой функции ($F$7); в этой ячейке, после выполнения задачи будет находиться оптимальное решение.

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

  3. В ячейки B7, C7 и D7 мы заносили, пока еще нулевые значения х1, х2 и х3, и в этих ячейках, после выполнения задачи будут храниться ничто иное как значения координат нашей целевой функции. Эти координаты, в процессе нахождения оптимального решения, меняют свои значения, поэтому в поле «Изменяя ячейки» мы внесем абсолютные ссылки на диапазон ячеек $B$7:$D$7.

  4. В поле «Ограничения» заносим все ограничения целевой функции, обозначенные в условии. Для этого нажимаем кнопку «Добавить», после чего открывается новое окно «Добавление ограничения» (рисунок 3.22). Здесь, в первом поле «Ссылка на ячейку» вводится ссылка на ячейку, в которой введена формула ограничения (для первого ограничения это ячейка F3), в следующем поле выбирается знак неравенства (в нашем случае это знак ) и в последнем поле «Ограничение» вводится ссылка на ячейку, в которой занесено значение, стоящее в правой части неравенства (для первого ограничения это Е3). После нажимаем кнопку «Добавить», которая автоматически добавляет введенное ограничение в список ограничений и очищает поле для ввода нового. Аналогично добавляются все последующие два ограничения.

Рисунок 3.22. - Окно «Добавление ограничения»

Устанавливая последние три ограничения x1 0, x2 0 и x3 0; в первом поле «Ссылка на ячейку», устанавливается ссылка на ячейку, которой соответствует неизвестный х, для ограничения x1 0 это ячейка В7, для ограничения x2 0 это ячейка С7, для x3 0 – ячейка D7, в следующем поле выбирается знак неравенства (для этих трех ограничений это знак ), а в последнее поле «Ограничения», для каждого из этих ограничений, заносится ссылка на ячейку Е6 в которой введен ноль, т.к. координаты х1, х2 и х3 должны быть больше или равны нулю

Если необходима корректировка созданного ограничения, то нажимаем кнопку «Изменить» в окне «Поиск решения»; открывается окно «Изменение ограничения» (рисунок 3.23) в котором производят все необходимые корректировки. Так же, по кнопке «Удалить» можно удалить ненужное ограничение.4

13. Далее нажимаем кнопку «Параметры», открывается окно «Параметры поиска решения» (рисунок 3.24). В этом окне возможно указать: максимальное время, предельное число итераций, относительная погрешность, допустимое отклонение, сходимость, оценки, разности, метод поиска.

Рисунок 3.23. - Окно «Изменение ограничения».

Определенные значения уже стоят в этих полях по умолчанию, но при необходимости их можно изменить; для нашей же задачи в этом окне необходимо поставить флажок на поле «Линейная модель», так как решаемая задача относится к задачам линейного программирования.

Рисунок 3.24. - Окно «Параметры поиска решения»

14. После этого, в окне «Поиск решения» нажимаем кнопку «Выполнить». Программа ведет поиск оптимального решения, о результатах которого сообщит в окне «Результаты поиска решения» (рисунок 3.25), а на самом листе, в соответствующих ячейках, отобразится найденное решение (рисунок 3.26).

Найденное решение звучит так: «Целевая функция достигает максимального значения в точке с координатами x1 = 4, x2 = 3, x3 = 0 и равна 11».

Рисунок 3.25. - Окно «Результаты поиска решения»

Рисунок 3.26. - Результат решения задачи.