РЕШЕНИЕ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ С ПОМОЩЬЮ НАДСТРОЙКИ «ПОИСК РЕШЕНИЯ» ТАБЛИЧНОГО РЕДАКТОРА EXCELНадстройка (встроенная программа) «Поиск решения» входит в состав электронного табличного редактора Ехсеl. Если надстройка установлена, то в меню Сервис должен быть соответствующий пункт меню; в противном случае надо этот компонент установить. Этот очень мощный математический инструмент позволяет легко решать задачи линейного и нелинейного программирования, не требуя от пользователя почти никакой специальной подготовки. И все же надо знать два необходимых условия, при отсутствии которых полученное решение будет сомнительным: область планов (допустимых решений) должна быть выпуклой и функция цели не должна быть выпуклой вниз при поиске максимума. Рассмотрим задачу линейного программирования, условия которой представлены в нижеследующей таблице:
Требуется найти оптимальный план производства продукции А и В, максимизирующий общую прибыль, при ограниченных запасах ресурсов и заданных нормах расхода этих ресурсов на производства единицы продукции каждого вида. Посмотрим последовательность решения этой задачи средствами Ехсе1. Условия задачи записываем на рабочем листе Ехсе1, буквально в том же виде, в каком задача была сформулирована (рис.1). Если задача — небольшого размера и размещается на одном экране (обычный размер экрана — 25 строк и 12 столбцов при масштабе 100%, или 31 строка и 16 столбцов при масштабе 75%), то рабочий лист Ехсеl будет являться хорошим отчетным документом.
Рис.1. Расположение условий задачи на листе Excel
Для задачи большего размера результаты расчета будут представлены в виде отчета, где принят такой порядок ссылок на каждую ячейку — объединяется ближайший текст слева с ближайшим текстом сверху. Этот отчет создается надстройкой автоматически. Поэтому желательно, чтобы все тексты были (по возможности) краткими, но достаточно информативными. Так, в рассматриваемой задаче расходы ресурсов в автоматическом отчете будут именоваться СтальРасход, МедьРасход, Токарн-Расход, ФрезерРасход; функция цели согласно текстам будет называться ПрибыльЦель, компоненты плана — ПланХ1, ПланХ2. Для начала (рис.1) обе компоненты плана приняты равными единице (это не имеет никакого значения для последующего расчета). В колонке Расход введены формулы для расчета каждого ресурса на производство планируемого количества продукции. Так, в ячейке СтальРасход вычислено 10*1+70*1=80. Табличный курсор стоит как раз в этой ячейке, поэтому содержимое этой ячейки отображается на панели формул (см. рис.1). Если одна формула набрана правильно (для проверки вычисляем результат для заданных компонент плана), то остальные формулы в столбце Расход получаются копированием. Активизируем надстройку «Поиск решения» (меню Сервис, Поиск решения). На экране появляется панель этой надстройки (рис.2).
Рис. 2. Панель надстройки «Поиск решения»
Перед вызовом надстройки рекомендуется установить табличный курсор в ячейку ПрибыльЦель, тогда ее адрес автоматически появится в поле Установить целевую ячейку. Но в принципе это не важно, так как все равно все поля ввода надо проверять. Нажимаем на кнопочку справа от поля ввода и убеждаемся, что нужная ячейка выделена бегущим пунктиром. Целевую ячейку можно установить равной максимальному значению, минимальному значению, конкретному значению. Выбираем альтернативу Установить целевую ячейку равной максимальному значению. Теперь заполняем поле Изменяя ячейки, где должны быть адреса диапазона плана. В некоторых простых задачах для этого достаточно нажать на кнопку Предположить, но здесь это не стоит делать, так как по умолчанию будут указаны все диапазоны, на которые ссылается целевая ячейка (а надо указать только один диапазон; правда, лишнее всегда можно стереть). Далее формулируем ограничения задачи. На «языке диапазонов» у нас всего лишь два ограничения: все неизвестные — неотрицательные, расход ресурса не превосходит его запаса. Не надо ничего набирать вручную — лучше нажать на кнопку Добавить. На экране появляется панель «Добавление ограничения» (рис. 3), содержащая три поля:
Рис. 3. Панель «Добавление ограничения»
В поле Ссылка на ячейку заносим адреса диапазона плана. В раскрывающемся списке второго поля выбираем > =. В третьем поле (Ограничение) набираем 0 (можно также указывать адреса диапазона такого же размера, как в первом поле, тогда будет производиться сравнение диапазонов по компонентам). Завершив набор 1-го ограничения, нажимаем на кнопку Добавить, и задаем следующее условие: $D$5: $D$8< =$Е$5: $Е$8 (см. рис. 2). Кнопки Исправить и Удалить на панели надстройки помогают отредактировать систему ограничений. Все готово для расчета. Нажимаем на кнопку Выполнить. На экране появляется панель (рис.4) с сообщением о результатах поиска:
Рис.4. Панель «Результаты поиска решения»
В данном случае поиск оптимального решения завершился успешно. Но если условия задачи — несовместные, сообщение будет другое: «Поиск не может найти подходящего решения». Если целевая функция - не ограниченная, сообщение будет иметь вид: «Значения целевой функции не сходятся». Наконец, могут быть еще некоторые сообщения, которые рассмотрим немного позже. Итак, оптимальное решение получено и предлагают заказать три вида отчетов. Заказываем их все (выделяем мышкой), решение сохраняем, ОК. На рис. 5 показан вид рабочего листа Ехсеl с результатами расчета, откуда сразу видны компоненты оптимального плана х1 = 1, х2 = 8 и максимальное значение прибыли z тах = 67 тыс. грн. Первые два ресурса израсходованы полностью — их остатки равны нулю; токарные и фрезерные станки не догружены — остатки их ресурсов равны 2100 и 2400 станко-часов соответственно. Если позволяют размеры задачи, распечатка финального рабочего листа Ехсеl дает понятный и полный отчет. Внизу рабочего листа (рис. 5) видны ярлычки заказанных автоматических отчетов. Рассмотрим их по порядку.
Рис.5. Условия задачи и оптимальное решение
Отчет по результатам состоит из трех таблиц. В 1-й таблице приводятся сведения о целевой функции. Начальное ее значение — 11, максимальное — 67. Во 2-й таблице показаны исходные значения компонент плана (1; 1) и полученные в результате поиска (1; 8).
В 3-й таблице проверяются все ограничения. В графе Значение приведены величины использованных ресурсов, а в графе Разница — остатки ресурсов. Если ресурс израсходован полностью (ограничение — активное), то в графе Статус указывается «связанное».
Отчет по устойчивости состоит из двух таблиц. В 1-й таблице снова приведены компоненты оптимального плана. Во 2-й таблице кроме величин расхода ресурсов приведены значения множителей Лагранжа, которые показывают теневые цены каждого ресурса. Третий и четвертый ресурсы не израсходованы полностью и их дальнейшее увеличение не приводит к соответствующему возрастанию прибыли (их теневые цены равны нулю). Увеличение дефицитного первого ресурса (сталь) на 1 кг приводит к возрастанию прибыли на 0, 0111 тыс. грн.; увеличение дефицитного второго ресурса (цветные металлы) на 1 кг приводит к возрастанию прибыли на 0, 1444 тыс. грн
В третьем отчете — отчете по пределам — снова приведено максимальное значение функции цели и показано, что будет, если в оптимальном плане по очереди каждую компоненту плана приравнять к наименьшему значению, насколько позволяют ограничения. Если принять х1 = 0, то прибыль уменьшится до 64 тыс. грн, если принять x2 = 0, то прибыль уменьшится до 3 тыс. грн. Последние два отчета доступны, если только в числе ограничений нет требования целочисленности или двоичности неизвестных (требования дискретности). На панели надстройки «Поиск решения» (см. рис. 2) есть кнопка Параметры. Нажмем ее и увидим рис. 6:
Рис.6. Панель параметров Прежде всего, заметим, что не включена опция Линейная модель, и задача решалась как нелинейная. Если задача большая и решается долго, есть смысл поставить флажок √ Линейная модель, тогда линейная задача будет решаться симплекс-методом. При этом изменится отчет по устойчивости. Оказывается, требование неотрицательности компонент плана можно задать здесь, установив флажок √ Неотрицательные значения. При решении нелинейных или целочисленных задач могут оказаться существенным заданные ограничения на время решения задачи или на предельное число итераций. По умолчанию задано время решения не более 100 секунд и число итераций не более 100 - этого достаточно для большинства задач. Однако, если за указанное время оптимальное решение не будет получено, то на панели «Результаты поиска решения» появится сообщение: «Время, установленное для поиска решения, истекло. Продолжить?». Аналогично, если задано слишком малое число итераций, появится сообщение: «Достигнуто максимальное число итераций. Продолжить?». Если в ответ нажать на кнопку Продолжить, решение будет продолжаться столько времени и столько итераций, сколько потребуется. Рассмотрим отчет по устойчивости для линейной модели, для чего установим флажок √ Линейная модель и повторим расчет. Это — очень интересный отчет, так как в нем приведено решение задачи с параметрами в ценовых коэффициентах целевой функции и в запасах ресурсов. Отчет состоит из 2-х таблиц. В 1-й таблице произведен анализ устойчивости оптимального плана относительно вариации в ценовых коэффициентах. Оказывается найденный план Заметим, что найденный оптимальный план очень чувствителен к малым изменениям цен. Так, стоит только снизить целевой коэффициент с2 = 8 на | Δ с2|> 0, 5 (примерно на 7%) или увеличить целевой коэффициент с1 = 3 на В графе Нормированная стоимость, где сейчас стоят нули, приводятся коэффициенты при неизвестных в преобразованной функции цели
Во 2-й таблице произведен анализ устойчивости плана относительно вариаций в свободных членах ограничений. В оптимальном плане теневые цены ресурсов равны
В найденном оптимальном плане дефицитными ресурсами являются сталь и цветные металлы — прибыль зависит от запасов этих ресурсов (их теневые цена отличны от нуля). Но при уменьшении запаса цветных металлов b2 = 420 на | Δ b2 | > 12, 857 (всего на 3%) все теневые цены изменяются (естественно, изменяется и план производства продукции). План оказался неустойчивым по запасам ресурсов. В реальных производственных условиях надо быть готовыми ко всяким неожиданностям, поэтому получение статичного оптимального плана нельзя считать полным решении проблемы, требуется провести еще подробное исследование последствий возможных вариаций в запасах ресурсов.
ТРАНСПОРТНАЯ ЗАДАЧА На листе Ехсеl условия задачи записываем так, чтобы получился понятный отчет; если требуется, добавляем необходимое количество пояснений — они не повлияют на расчеты. Первоначально все компоненты плана принимаем равными единице, чтобы можно было проверить правильность всех формул в графе Вывезено, строке Привезено и в целевой ячейке РасходМiт (ячейка I9). В графе Вывезено записаны формулы (приводим только для ячейки Е10): =СУММ(В10: D10). В строке Привезено записаны формулы (приводим только для ячейки В13): =СУММ(В10: В12). Формулы в остальных ячейках графы и строки получены копированием. В ячейке целевой функции РасходМiт (ячейка I9) записана формула: =СУММПРОИЗВ(В4: D6; В10: D12). Все формулы рекомендуется создавать с помощью Мастера функций, указывая мышкой диапазоны, а не набирая вручную их адреса. Еще лучше — дать диапазонам содержательные имена, тогда все формулы станут понятными.
Устанавливаем табличный курсор в ячейку РасходМiт и активизируем надстройку «Поиск решения». Целевую ячейку устанавливаем равной минимальному значению. В поле Изменяя ячейки заносим адреса диапазона плана (протягиваем мышкой по диагонали диапазона). Ограничения задачи: компоненты плана не превосходят пропускных способностей, все запасы должны быть вывезены: Вывезено = Запасы, все потребности должны быть удовлетворены: Привезено = Потребности. Можно нажать кнопку Параметры и установить флажки: √ Линейная модель и √ Неотрицательные значения. Но можно этого не делать, тогда в число ограничений следует добавить условие неотрицательности неизвестных (см. рис. 7).
Рис.7. Ограничения транспортной задачи
Нажимаем на кнопку Выполнить и получаем оптимальное решение задачи. В оптимальном плане заняты все маршруты кроме одного. Минимальные расходы на перевозку равны fm in= 740. Все условия задачи соблюдены.
Рассмотрим также отчеты по результатам и устойчивости.
Если поставлен флажок √ Линейная модель, отчет по устойчивости будет более полным и кроме множителей Лагранжа (теневых цен) будет давать сведения о допустимых вариациях цен и запасов. Отчет состоит из двух таблиц. В первой таблице в графе Нормированная стоимость отрицательные коэффициенты перед некоторыми неизвестными хij показывают, что увеличение перевозок по этим маршрутам приводит к снижению общей стоимости плана. Но грузооборот на этих маршрутах ограничен пропускными способностями коммуникаций. Графы Допустимое увеличение и Допустимое уменьшение относятся к тарифам (Целевой коэффициент). Из второй таблицы находим, что наиболее рентабельным предприятием является А1 с наименьшим потенциалом (теневой ценой), а наиболее убыточным — А2 с наибольшим потенциалом (разыскивается минимум функции цели, а не максимум). Если увеличить запас А1 на единицу, а запас А2 уменьшить на единицу (так как общая потребность неизменна), расходы сократятся на 4 - 0 = 4 стоимостных единицы, что легко проверить новым расчетом. На сколько можно увеличить запас А1 за счет А2 при тех же теневых ценах? Согласно отчету, запас А1 можно увеличить на 5 единиц, но (по этому же отчету) получается, что запас А2 нельзя уменьшать! Это можно объяснить только тем, что в отчете не предусмотрено совместное изменение запасов. Поэкспериментируем — увеличим запас А1 на 5, на 6, па 7 единиц за счет такого же уменьшения запаса А2.
Оказалось, что, действительно, запас А1 можно увеличить за счет А2 на 5 единиц, при этом теневые цены не изменятся. Новый план приведен ниже:
Все правильно, общая стоимость уменьшилась на 5 х (4 - 0) = 20 стоимостных единиц. Новый отчет по устойчивости не приводим, теневые цены не изменились, но теперь указано, что допустимое увеличение запаса А1 уже равно нулю. Для проверки мы изменили запасы А1 и А2 еще на единицу и убедились, что это уже приводит к изменению теневых цен. Как и раньше, наиболее рентабельным предприятием оказалось А1, но с новой теневой ценой u1 = -3, а наиболее убыточным – А2 с теневой ценой u 2 = 0. Согласно новому отчету по устойчивости, запас А1 можно увеличить еще на 4 единицы (а запас А2, как и раньше, нельзя уменьшать). Проверка показала, что стоимость плана с запасами a1 = 55, а2= 55 действительно уменьшилась на 5 х (3 - 0) = 15 и составила fmin = 705 стоимостных единиц. Далее теневые цены снова изменились. Не будем обращать внимания на нули в графе Допустимое уменьшение. Более того, будем иметь в виду, что для пограничных планов появляются нули также в графе Допустимое увеличение. Во всяком случае, можно убедиться, что полный отчет по устойчивости содержит много полезной информации.
|
остается оптимальным в следующих интервалах варьирования цен: 
.
(примерно на 7%), как план производства совершенно изменится (х1 = 16; х2 = 8).
(или «оценки векторов» Δ j). Эта информация полезна, если какой-либо вид продукции невыгодно производить (хj= 0); тогда соответствующий коэффициент будет показывать, на сколько снизится прибыль при принудительном производстве единицы невыгодной продукции.
; 
; 
, т.е. на прибыль влияют сейчас вариации первых двух ресурсов. Эти теневые цены остаются справедливыми в следующих интервалах варьирования запасов ресурсов:
