Решение ЗЛП с помощью MS EXCEL

Для решения задач оптимизации в MS Excel используют надстройку Поиск решения, которая вызывается из пункта главного меню «Сервис» (рис. 1.8). Для версии MS Excel 2007 и выше, Поиск решения находится на вкладке Данные в группе Анализ.

Если в версии Excel, установленной на Вашем компьютере, отсутствует данный подпункт меню, необходимо вызвать пункт меню «Надстройки» и в предложенном списке дополнительных модулей выбрать «Поиск решения» (рис. 1.9). Для версии MS Excel 2007 и выше Надстройки вызываются через кнопку Microsoft Office , Параметры Excel.

Рис. 1.8.

Рис. 1.9.

Рассмотрим использование данной надстройки на примере. Решим с её помощью задачу, математическая модель которой строилась в примере 1. Математическая модель задачи имеет вид:

3Х₁ + 2Х₂

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

Х₁ + 2Х₂ 6 (а)

2Х₁ + Х₂ 8 (б)

Х₁+0,8Х₂ 5 (в)

-Х₁ + Х₂ 1 (г)

Х₂ 2 (д)

Х₁ 0, Х₂ 0 (е)

Составим шаблон в редакторе Excel, как показано на рис. 1.10

Рис.1.10. Шаблон оформления задачи.

Теперь занесём данную в задаче числовую информацию (рис.1.11).

Рис.1.11. Исходные данные задачи

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

Ячейки B4 – С4 называются в Excel изменяемыми (в нашей модели это неизвестные переменные), т.е., изменяя их Поиск решения будет находить оптимальное значение целевой функции. Значения, которые первоначально вводят в эти ячейки, обычно нули (незаполненные клетки трактуются по умолчанию как содержащие нулевые значения).

Теперь необходимо ввести формулы. В нашей математической модели, целевая функция представляет собой произведение вектора коэффициентов на вектор неизвестных. Действительно, выражение можно рассматривать как произведение вектора (3,2) на вектор (Х₁,Х₂).

В Excel существует функция СУММПРОИЗВ, которая позволяет найти скалярное произведение векторов. В ячейку Е4 необходимо вызвать данную функцию, а в качестве перемножаемых векторов задать адреса ячеек, содержащих коэффициенты уравнений (в данном случае, это В5:С5) и ячеек, в которые в результате решения будут помещены значения Х₁ и Х₂ (ячейки В4:С4) (рис. 1.12).

Рис.1.12. Вызов функции СУММПРОИЗВ.

Каждая левая часть ограничения тоже представляет собой произведение двух векторов: соответствующей строки матрицы затрат и вектора неизвестных. То есть, выражение Х₁+2Х₂ (для первого ограничения Х₁ + 2Х₂ 6) будем рассматривать как произведение вектора коэффициентов (1,2) и вектора переменных (Х₁,Х₂).

В ячейке, отведенной для формулы левой части первого ограничения (D9), вызовем функцию СУММПРОИЗВ. В качестве адресов перемножаемых векторов занесем адрес строки коэффициентов В9:С9 и адрес значений переменных В4:С4 (рис. 1.13).

Рис.1.13.

В четыре оставшиеся ячейки графы «Левая часть» вводим аналогичные формулы, используя соответствующую строку матрицы затрат. Фрагмент экрана с введёнными формулами показан на рис.1.14.

Рис.1.14.

Важно! К моменту вызова сервиса «Поиск решения» на рабочем листе с задачей должны быть занесены формулы для левых частей ограничений и формула для значения целевой функции.

В меню Сервис выбираем Поиск решения. В появившемся окне задаём следующую информацию:

а) в качестве целевой ячейки устанавливаем адрес ячейки для значения целевой функции Е4;

б) «флажок» устанавливаем на вариант «максимальному значению», т.к. в данном случае, целевая функция дохода подлежит максимизации;

в) в качестве изменяемых ячеек заносится адрес строки значений переменных В4:С4;

г) справа от окна, предназначенного для занесения ограничений, нажимаем кнопку «Добавить», появится форма для занесения ограничения (рис. 1.15)

Рис.1.15. Форма для занесения одного ограничения ЗЛП

Рис.1.16. Занесение первого ограничения задачи

д) в левой части формы «Ссылка на ячейку» заносится адрес формулы для левой части первого ограничения D9, выбирается требуемый знак неравенства (в нашем случае, <=), в поле «Ограничение» заносится ссылка на правую часть ограничения F9 (рис. 1.16).

е) аналогично заносятся все ограничения задачи, после чего нажимается кнопка «ОК».

Таким образом, окно «Поиск решения» с занесенной информацией выглядит следующим образом (рис.1.17):

Рис.1.17.

Далее необходимо нажать кнопку Параметры, установить «флажки» «Линейная модель» и «Неотрицательные значения», поскольку в данном случае задача является ЗЛП, а ограничение 6) требует неотрицательности значений (рис.1.18).

Рис.1.18. Установка параметров

Затем следует нажать «ОК», «Выполнить», после чего появляется окно результата решения (рис.1.19).

Рис.1.19. Окно результата решения

Если в результате всех действий получено окно с сообщением «Решение найдено», то Вам предоставляется возможность получения трех типов отчета, которые полезны при анализе модели на чувствительность. В данном примере достаточно сохранить найденное решение, нажав «ОК». В результате получено решение задачи из примера 1. (рис.1.20).

Рис.1.20. Результат применения «Поиска решения»

Если в результате решения задачи выдано окно с сообщением о невозможности нахождения решения (рис.1.21), это означает, что при оформлении задачи была допущена ошибка (не заполнены формулы для ограничений, неправильно установлен «флажок» максимизации/минимизации и т.д.).

Рис.1.21. Сообщение об ошибке

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