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

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

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

Рис. 2.208.

Рис. 2.209

Рассмотрим использование данной надстройки на примере:

Фабрика выпускает пряжу двух видов: П1 и П2. Продукция поступает в оптовую продажу. Для производства используется три вида сырья – шерсть, капрон и акрил. Максимально возможные суточные запасы этих материалов составляют 6, 8 и 5 тонн соответственно. Расходы сырья на партию пряжи и оптовые цены приведены в таблице:

Таблица

Изучение рынка сбыта показало, что суточный спрос на пряжу П2 никогда не превышает спроса на пряжу П1 более чем на одну партию. Кроме того, установлено, что спрос на пряжу П2 никогда не превышает 2 партий.

Какое количество пряжи (в партиях) каждого вида должна производить фабрика, что бы доход от реализации продукции был максимальным?

Математическая модель задачи имеет вид:

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

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

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

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

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

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

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

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

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

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

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

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

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

Рис.2.213.

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

Рис.2.214.

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

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

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

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

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

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

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

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

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

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

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

Рис.2.217.

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

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

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

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

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

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

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

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

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

Организовываем расчеты на листе MS Excel. (рис. 2.222)

Рис. 2.222

Заводим функцию цели в ячейке D20, как произведение дневной оплаты работников (ячейка D19) на сумму всех работников, вычисленную в ячейке D15, как СУММ(F15:L15).

В ячейках F15:L15 заводим функции СУММПРОИЗВ ($D$7:$D$13; F7:F13) и т.д. (копируем формулу направо), зафиксировав диапазон изменяемых ячеек (кнопка F4). В итоге в ячейках F15:L15 вычислим количество работников, работающих в данный день недели.

В строках 7-13 1 означает, что данная группа в этот день работает.

Вызываем надстройку Поиск решений на вкладке Данные и устанавливаем целевую ячейку, изменяемые ячейки и ограничения. (рис. 2.223)

Рис. 2.223 Диалоговое окно Поиск решения

В диалоговом окне Поиск решения выставлены следующие параметры:

Нажав кнопку Найти решение, получим следующий график работы:

по графику А работают 3 сотрудника, по графику Б - 5 сотрудников, по графику В - 7 сотрудников, по графику Г - 4 сотрудника, по графику Д - 6 сотрудников, по графику Е - 1 сотрудник и по графику Ж не работает никто. Общие расходы на зарплату за неделю - 987 руб при нанятых 25 сотрудниках.

Поиск по сайту: