Рассмотрим пример задачи линейного программирования.
Требуется определить, в каком количестве надо выпустить продукцию четырех типов Прод1, Прод2, Прод3, Прод4, для изготовления которой требуются ресурсы трех видов: трудовые, сырье и финансы. Количество ресурса каждого вида, необходимое для выпуска единицы продукции данного типа, называется нормой расхода. Нормы расхода, а также прибыль, получаемая от реализации единицы каждого типа продукции, приведены на рис. 1.
| Ресурс | Прод1 | Прод2 | Прод3 | Прод4 | Знак | Наличие |
| Прибыль | ||||||
| Трудовые | ||||||
| Сырье | ||||||
| Финансы |
Рисунок 1.
Математическая модель задачи имеет вид:
где x j – количество выпускаемой продукции j-го типа; F – функция цели; в левых частях выражений ограничений указаны величины потребного ресурса , а правые части показывают количество имеющегося ресурса .
Для решения задачи с помощью Excel следует создать форму для ввода исходных данных и ввести их. Форма ввода показана на рис. 2.
В ячейку F6 введено выражение целевой функции как суммы произведений значений прибыли от выпуска единицы продукции каждого типа на количество выпускаемой продукции соответствующего типа. Для наглядности на рис. 3 представлена форма ввода исходных данных в режиме вывода формул.
В ячейки F8:F10 введены левые части ограничений для ресурсов каждого вида.
Рисунок 2.
Рисунок 3.
Для решения задач линейного программирования в Excel используется мощный инструмент, называемый Поиск решения . Обращение к Поиску решения осуществляется из меню Сервис , на экран выводится диалоговое окно Поиска решения (рис. 4).
Рисунок 4.
Ввод условий задачи для поиска ее решения состоит из следующих шагов:
1 Назначить целевую функцию, для чего установить курсор в поле Установить целевую ячейку окна Поиск решения и щелкнуть в ячейке F6 в форме ввода;
2 Включить переключатель значения целевой функции, т.е. указать ее Равной Максимальному значению ;
3 Ввести адреса изменяемых переменных (x j): для этого установить курсор в поле Изменяя ячейки окна Поиск решения, а затем выделить диапазон ячеек B3:E3 в форме ввода;
4 Нажать кнопку Добавить окна Поиск решения для ввода ограничений задачи линейного программирования; на экран выводится окно Добавление ограничения (рис. 5) :
Ввести граничные условия для переменных x j (x j ³0), для этого в поле Ссылка на ячейку указать ячейку В3, соответствующую х 1 , выбрать из списка нужный знак (³), в поле Ограничение указать ячейку формы ввода, в которой хранится соответствующее значение граничного условия, (ячейка В4), нажать кнопку Добавить ; повторить описанные действия для переменных х 2 , х 3 и х 4 ;
Ввести ограничения для каждого вида ресурса, для этого в поле Ссылка на ячейку окна Добавление ограничения указать ячейку F9 формы ввода, в которой содержится выражение левой части ограничения, наложенного на трудовые ресурсы, в полях Ограничение указать знак £ и адрес Н9 правой части ограничения, нажать кнопку Добавить ; аналогично ввести ограничения на остальные виды ресурсов;
После ввода последнего ограничения вместо Добавить нажать ОК и возвратиться в окно Поиск решения.
Рисунок 5.
Решение задачи линейного программирования начинается с установки параметров поиска:
В окне Поиск решения нажать кнопку Параметры , на экран выводится окно Параметры поиска решения (рис. 6);
Установить флажок Линейная модель, что обеспечивает применение симплекс-метода;
Указать предельное число итераций (по умолчанию – 100, что подходит для решения большинства задач);
Установить флажок , если необходимо просмотреть все этапы поиска оптимального решения;
Нажать ОК , возврат в окно Поиск решения .
Рисунок 6.
Для решения задачи нажать кнопку Выполнить в окне Поиск решения , на экране – окно Результаты поиска решения (рис. 7), в котором содержится сообщение Решение найдено. Все ограничения и условия оптимальности выполнены. Если условия задачи несовместны, то выводится сообщение Поиск не может найти подходящего решения . Если целевая функция не ограничена, то появляется сообщение Значения целевой ячейки не сходятся .
Рисунок 7.
Для рассматриваемого примера решение найдено и результат оптимального решения задачи выводится в форме ввода: значение целевой функции, соответствующее максимальной прибыли и равное 1320, указывается в ячейке F6 формы ввода, оптимальный план выпуска продукции х 1 =10, х 2 =0, х 3 =6, х 4 =0 указывается в ячейках В3:С3 формы ввода (рис. 8).
Количество использованных для выпуска продукции ресурсов выводится в ячейки F9:F11: трудовых – 16, сырья – 84, финансов – 100.
Рисунок 8.
Если при установке параметров в окне Параметры поиска решения (рис. 6) был установлен флажок Показывать результаты итераций , то будут показаны последовательно все шаги поиска. На экран будет выводиться окно (рис. 9). При этом текущие значения переменных и функции цели будут показаны в форме ввода. Так, результаты первой итерации поиска решения исходной задачи представлены в форме ввода на рисунке 10 .
Рисунок 9.
Рисунок 10.
Чтобы продолжить поиск решения, следует нажимать кнопку Продолжить в окне Текущее состояние поиска решения .
Прежде чем, перейти к анализу результатов решения, представим исходную задачу в форме
введя дополнительные переменные у i , представляющие собой величины неиспользованных ресурсов.
Анализ результатов поиска решения позволит увязать их с переменными исходной и двойственной задач.
С помощью окна Результаты поиска решения можно вызвать отчеты трех типов, позволяющие анализировать найденное оптимальное решение:
Результаты,
Устойчивость,
Пределы.
Для вызова отчета в поле Тип отчета выделить название нужного типа и нажать ОК .
1 Отчет по результатам (рис. 11) состоит из трех таблиц:
Таблица 1 содержит сведения о целевой функции; в столбце Исходно указывается значение целевой функции до начала вычислений;
Таблица 2 содержит значения искомых переменных x j , полученных в результате решения задачи (оптимальный план выпуска продукции);
Таблица 3 показывает результаты оптимального решения для ограничений и для граничных условий.
Для Ограничений в графе Формула приведены зависимости, которые были введены при задании ограничений в окне Поиск решения ; в графе Значение указаны величины использованного ресурса; в графе Разница показано количество неиспользованного ресурса. Если ресурс используется полностью, то в графе Состояние выводится сообщение связанное ; при неполном использовании ресурса в этой графе указывается не связан. Для Граничных условий приводятся аналогичные величины с той лишь разницей, что вместо неиспользованного ресурса показана разность между значением переменной x j в найденном оптимальном решении и заданным для нее граничным условием (x j ³0).
Именно в графе Разница можно увидеть значения дополнительных переменных y i исходной задачи в формулировке (2). Здесь у 1 =у 3 =0, т.е. величины неиспользованных трудовых и финансовых ресурсов равны нулю. Эти ресурсы используются полностью. Вместе с тем, величина неиспользованных ресурсов для сырья у 2 =26, значит, имеются излишки сырья.
Рисунок 11.
2 Отчет по устойчивости (рис. 12)состоит из двух таблиц.
В таблице 1 приводятся следующие значения:
Результат решения задачи (оптимальный план выпуска);
- Нормир. стоимость , т.е. величины, показывающие, насколько изменится целевая функция при принудительном включении единицы продукции соответствующего типа в оптимальный план;
Коэффициенты целевой функции;
Предельные значения приращения коэффициентов целевой функции, при которых сохраняется оптимальный план выпуска.
В таблице 2 содержатся аналогичные данные для ограничений:
Величины использованных ресурсов;
- Теневая цена , показывающая, как изменится целевая функция при изменении величины соответствующего ресурса на единицу;
Допустимые значения приращений ресурсов, при которых сохраняется оптимальный план выпуска продукции.
Рисунок 12.
Отчет по устойчивости позволяет позволяет получить двойственные оценки.
Как известно, двойственные переменные z i показывают, как изменится целевая функция при изменении ресурса i-го типа на единицу. В отчете Excel двойственная оценка называется Теневой ценой .
В нашем примере сырье не используется полностью и его ресурс у 2 =26. Очевидно, что увеличение количества сырья, например, до 111 не повлечет за собой увеличения целевой функции. Следовательно, для второго ограничения двойственная переменная z 2 =0. Таким образом, если по данному ресурсу есть резерв, то дополнительная переменная будет больше нуля, а двойственная оценка этого ограничения равна нулю.
В рассматриваемом примере трудовые ресурсы и финансы использовались полностью, поэтому их дополнительные переменные равны нулю (у 1 =у 3 =0). Если ресурс используется полностью, то его увеличение или уменьшение повлияет на объем выпускаемой продукции, и следовательно, на величину целевой функции. Двойственные оценки ограничений на трудовые и финансовые ресурсы отличны от нуля, т.е. z 1 =20, z 3 =10.
Значения двойственных оценок находим в Отчете по устойчивости , в таблице 2, в графе Теневая цена .
При увеличении (уменьшении) трудовых ресурсов на единицу целевая функция увеличится (уменьшится) на 20 единиц и будет равна
F=1320+20×1=1340 (при увеличении).
Аналогично, при увеличении объема финансов на единицу целевая функция будет
F=1320+10×1=1330.
Здесь же, в графах Допустимое увеличение и Допустимое уменьшение таблицы 2, показаны допустимые пределы изменения количества ресурсов j-го вида. Например, для при изменении приращения величины трудовых ресурсов в пределах от –6 до 3,55, как показано в таблице, структура оптимального решения сохраняется, т.е наибольшую прибыль обеспечивает выпуск Прод1 и Прод3, но в других количествах.
Дополнительные двойственные переменные также отражены в Отчете по устойчивости в графе Нормир. стоимость таблицы 1.
Если основные переменные не вошли в оптимальное решение, т.е. равны нулю (в примере х 2 =х 4 =0), то соответствующие им дополнительные переменные имеют положительные значения (v 2 =10, v 4 =20). Если же основные переменные вошли в оптимальное решение (х 1 =10, х 3 =6), то их дополнительные двойственные переменные равны нулю (v 1 =0, v 3 =0).
Эти величины показывают, насколько уменьшится (поэтому знак минус в значениях переменных v 2 и v 4) целевая функция при принудительном выпуске единицы данной продукции. Следовательно, если мы захотим принудительно выпустить единицу продукции вида Прод3, то целевая функция уменьшится на 10 единиц и будет равна 1320 -10×1 =1310.
Обозначим через Dс j изменение коэффициентов целевой функции в исходной модели (1). Эти коэффициенты определяют прибыль, получаемую при реализации единицы продукции j-го вида.
В графах Допустимое увеличение и Допустимое Уменьшение таблицы 1 Отчета по устойчивости показаны пределы изменения Dс j , при которых сохраняется структура оптимального плана, т.е. будет выгодно по-прежнему выпускать продукцию вида Продj. Например, при изменении Dс 1 в пределах -12£ Dс 1 £ 40, как показано в отчете, по-прежнему будет выгодно выпускать продукцию вида Прод1. При этом значение целевой функции будет F=1320+x 1 ×Dс j =1320+10×Dс j .
3 Отчет по пределам приведен на рис. 13. В нем показывается, в каких пределах могут изменяться значения x j , вошедшие в оптимальное решение, при сохранении структуры оптимального решения. Кроме этого, для каждого типа продукции приводятся значения целевой функции, получаемые при подстановке в оптимальное решение значения нижнего предела выпуска изделий соответствующего типа при неизменных значениях выпуска остальных типов. Например, если при оптимальном решении х 1 =10, х 2 =0, х 3 =6, х 4 =0 положить х 1 =0 (нижний предел) при неизменных х 2 , х 3 и х 4 , то значение целевой функции будет равно 60×0+70×0+120×6+130×0=720.
Инструментом для решений задач оптимизации в MS Excel служит надстройка Поиск решения . Процедура поиска решения позволяет найти оптимальное значение формулы, содержащейся в ячейке, которая называется целевой. Эта процедура работает с группой ячеек, прямо или косвенно связанных с формулой в целевой ячейке. Чтобы получить по формуле, содержащейся в целевой ячейке, заданный результат, процедура изменяет значения во влияющих ячейках.
Если данная надстройка установлена, то Поиск решения
запускается из меню Сервис
. Если такого пункта нет, следует выполнить команду Сервис
→ Надстройки...
и выставить флажок против надстройки
Поиск решения
(рис.2.1).
В окне Поиск решения имеются следующие поля:
Установить целевую ячейку – служит для указания целевой ячейки, значение которой необходимо максимизировать, минимизировать или установить равным заданному числу. Эта ячейка должна содержать формулу .
Равной – служит для выбора варианта оптимизации значения целевой ячейки (максимизация, минимизация или Подбор заданного числа). Чтобы установить число, введите его в поле.
Изменяя ячейки – служит для указания ячеек, значения которых изменяются в процессе поиска решения до тех пор, пока не будут выполнены наложенные ограничения и условие оптимизации значения ячейки, указанной в поле Установить целевую ячейку.
Предположить – используется для автоматического поиска ячеек, влияющих на формулу, ссылка на которую дана в поле Установить целевую ячейку. Результат поиска отображается в поле Изменяя ячейки.
Ограничения – служит для отображения списка граничных условий поставленной задачи.
Добавить - служит для отображения диалогового окна Добавить ограничение.
Изменить - Служит для отображения диалоговое окна Изменить ограничение.
Удалить - Служит для снятия указанного ограничения.
Выполнить – Служит для запуска поиска решения поставленной задачи.
Закрыть – Служит для выхода из окна диалога без запуска поиска решения поставленной задачи.
Параметры поиска решения, в котором можно загрузить или сохранить оптимизируемую модель и указать предусмотренные варианты поиска решения.
Восстановить – Служит для очистки полей окна диалога и восстановления значений параметров поиска решения, используемых по умолчанию.
Для решения задачи оптимизации выполните следующие действия.
1. В меню Сервис выберите команду Поиск решения.
2. В поле Установить целевую ячейку введите адрес или имя ячейки, в которой находится формула оптимизируемой модели.
3. Чтобы максимизировать значение целевой ячейки путем изменения значений влияющих ячеек, установите переключатель в положение максимальному значению.
Чтобы минимизировать значение целевой ячейки путем изменения значений влияющих ячеек, установите, переключатель в положение
минимальному значению.
Чтобы установить значение в целевой ячейке равным некоторому числу путем изменения значений влияющих ячеек, установите переключатель в положение значению и введите в соответствующее поле требуемое число.
4. В поле Изменяя ячейки введите имена или адреса изменяемых ячеек, разделяя их запятыми. Изменяемые ячейки должны быть прямо или косвенно связаны с целевой ячейкой. Допускается установка до 200 изменяемых ячеек.
Чтобы автоматически найти все ячейки, влияющие на формулу модели, нажмите кнопку Предположить.
5. В поле Ограничения введите все ограничения, накладываемые на поиск решения.
6. Нажмите кнопку Выполнить.
Чтобы восстановить исходные данные, установите переключатель в положение
Этап С. Анализ найденного решения задачи оптимизации.
Для вывода итогового сообщения о результате решения используется диалоговое окно Результаты поиска решения.
 |
Диалоговое окно Результаты поиска решения содержит следующие поля:
Восстановить исходные значения – служит для восстановления исходных значений влияющих ячеек модели.
Отчеты – служит для указания типа отчета, размещаемого на отдельном листе книги.
Результаты. Используется для создания отчета, состоящего из целевой ячейки и списка влияющих ячеек модели, их исходных и конечных значений, а также формул ограничений и дополнительных сведений о наложенных ограничениях.
Устойчивость. Используется для создания отчета, содержащего сведения о чувствительности решения к малым изменениям в формуле (поле Установить целевую ячейку, диалоговое окно Поиск решения) или в формулах ограничений.
Ограничения. Используется для создания отчета, состоящего из целевой ячейки и списка влияющих ячеек модели, их значений, а также нижних и верхних границ. Такой отчет не создается для моделей, значения в которых ограничены множеством целых чисел. Нижним пределом является наименьшее значение, которое может содержать влияющая ячейка, в то время как значения остальных влияющих ячеек фиксированы и удовлетворяют наложенным ограничениям. Соответственно, верхним пределом называется наибольшее значение.
Сохранить сценарий – служит для отображения диалогового окна Сохранение сценария, в котором можно сохранить сценарий решения задачи, чтобы использовать его в дальнейшем с помощью диспетчера сценариев MS Excel. В следующих разделах рассмотрим несколько конкретных моделей линейной оптимизации и примеры их решения с помощью MS Excel.
2.4 Задача о планировании производства
Постановка задачи. Предприятие должно производить изделия n видов: и 1 ,и 2 ,...и п , причем количество каждого выпускаемого изделия не должно превысить спрос β 1 , β 2 ,..., β n и одновременно не должно быть меньше запланированных величин b 1 ,b 2 ,...,b n соответственно. На изготовление изделий идет m видов сырья s l ,s 2 ,...,s m , запасы которых ограничены соответственно величинами γ 1 , γ 2 ,..., γ m . Известно, что на изготовление i -го изделия идет а ij единиц j -го сырья. Прибыль, получаемая от реализации изделий u 1 , ,и 2 ,...и п равна соответственно с 1 ,с 2 ,...,с п. Требуется так спланировать производство изделий, чтобы прибыль была максимальной и при этом выполнялся план на производство каждого изделия, но не превышался спрос на него.
Математическая модель. Обозначим за х 1 ,х 2 ,...х n количества единиц изделий u 1 , ,и 2 ,...и п, выпускаемых предприятием. Прибыль, приносимая планом (целевая функция), будет равна:
z = z(x 1 ,x 2 ,...,x n) = с 1 x 1 + c 2 x 2 + ...+c n x n → max. Ограничения на выполнение плана запишется в виде: х i ≥β i для i = 1,2,...,n Чтобы не превысить спрос, надо ограничить выпуск изделий: x i ≤β i для i = 1,2,...n. И, наконец, ограничения на сырье запишутся в виде системы неравенств:
α 11 x 1 + α 12 x 2 +...+ α 1n x n ≤b 1
α 21 x 1 + α 22 x 2 +...+ α 2n x n ≤b 2
................................................
α m1 x 1 + α m2 x 2 +...+ α mn x n ≤b m
при условии, что х 1 ,х 2 ,...х п неотрицательны.
Пример 2.1:
Рассмотрим конкретный пример задачи о планировании производства и приведем последовательность действий, необходимых для ее решения с помощью MS Excel.
Условие задачи. Предприятие выпускает два вида железобетонных изделий: лестничные марши и балконные плиты. Для производства одного лестничного марша требуется израсходовать 3,5 куб.м. бетона и 1 упаковку арматуры, а для производства плиты - 1 куб.м. бетона и 2 упаковки арматуры. На каждую единицу продукции приходится 1 человеко-день трудозатрат. Прибыль от продажи 1 лестничного марша составляет 200 руб., а одной плиты - 100 руб. На предприятии работает 150 человек, причем известно, что в день предприятие производит не более 350 куб.м. бетона и завозится не более 240 упаковок арматуры. Требуется составить такой производственный план, чтобы прибыль от производимой продукции была максимальной.
Решение.
1. На листе рабочей книги MS Excel заполните таблицу параметров задачи (рис. 2.2).
2.
Создайте модель задачи и заполните ячейки для значений переменных (первоначально ячейки х { и х г
заполняются произвольными числовыми значениями, например, значением 10), целевой функции (ячейка содержит формулу) и ограничений (ячейки содержат формулы)
(рис. 2.2)
3. Выполните команду Сервис Поиск решения и установите необходимые значения в полях диалогового окна Поиск решения, добавляя ограничения в окне Добавление ограничений.
Замечание. В окне Добавление ограничений при необходимости есть возможность установить ограничения на целочисленность переменных модели.
4. Нажмите на кнопку Выполнить и установите параметры в окне Результаты поиска решения (переключатель Сохранить найденное решение или Восстановить исходные значения и Тип отчета).
Замечание: В случае ошибок в формулах, ограничениях или неверных параметрах модели в данном окне могут появиться следующие сообщения: «Значения целевой ячейки не сходятся», «Поиск не может найти решения» или «Условия линейной модели не выполняются». При этом переключатель следует установить в положение Восстановить исходные значения, проверить данные на листе и процедуру поиска решения проделать заново.
5. В результате в ячейках с переменными задачи появятся значения, соответствующие оптимальному плану (80 лестничных маршей и 70 плит перекрытия в день), а в ячейке для целевой функции - значение прибыли (23 000 руб.), соответствующее данному плану (рис. 2.3)
6. Вслучае если полученное решение является удовлетворительным, можно сохранить оптимальный план и ознакомиться с результатами поиска, которые выводятся на отдельный лист.
Упражнение:
Упр. 2.1. Предприятие выпускает телевизоры, стереосистемы и акустические системы, используя общий склад комплектующих. Запасы шасси на складе составляют 450 шт., кинескопов – 250 шт., динамиков – 800 шт., блоков питания – 450 шт., плат – 600 шт. На каждое изделие расходуется количество комплектующих, указанное в таблице:
Прибыль от производства одного телевизора составляет 90 у.е, одной стереосистемы – 50 и аудиосистемы – 45. Необходимо найти оптимальное соотношение объемов выпуска изделий, при котором прибыль от производства всей продукции будет максимальной.
Цель работы: изучение современных программных средств решения задачи линейного программирования; практическое решение задач линейного программирования графическим методом, симплекс-методом и средствами программыMicrosoftExcel; программная реализация симплекс-метода на языке программирования высокого уровня.
Для решения задач линейного программирования в программе Microsoft Excel имеется надстройка Поиск решения , обращение к которой производится из меню Сервис .
Если команда Поиск решения отсутствует в меню Сервис , то требуется установить надстройку «Поиск решения». Для этого в меню Сервис выбирается команда Надстройки , которая открывает диалоговое окно, показанное на рис. 1.
Покажем использование надстройки «Поиск решения» на примере решения следующей задачи.
Предприятие изготавливает и реализует три вида продукции – P 1 , Р 2 и Р 3 . Для производства продукции используются три вида ресурсов – комплектующие изделия, сырье и материалы. Запасы ресурсов и их расход на изготовление единицы продукции каждого вида приведены в табл. 1.
Таблица 1
Прибыль от реализации единицы продукции каждого вида составляет 240, 210 и 180 денежных единиц для P 1 , Р 2 и Р 3 соответственно.
Требуется определить производственную программу предприятия таким образом, чтобы прибыль от реализации продукции была максимальной.
Обозначим переменными x 1 , x 2 и x 3 искомые объемы производства продукции видов P 1 , Р 2 и Р 2 , а через F – прибыль предприятия. Тогда математическая постановка представленной задачи принимает следующий вид.
Определить значения переменных x 1 , x 2 и x 3 , для которых достигается максимум целевой функции
F = 240 x 1 + 210 х 2 + 180 x 3
при ограничениях:
Целевая функция описывает суммарную прибыль от реализации произведенной продукции всех трех видов. Ограничения (1), (2) и (3) учитывают расход и запасы комплектующих изделий, сырья и материалов соответственно. Поскольку объемы производства продукции не могут быть отрицательными, добавляются условия
x 1 ≥ 0; x 2 ≥ 0; x 3 ≥ 0.
Примерные действия, необходимые для решения задачи линейного программирования средствами программы Excel, представим в виде последовательности шагов.
Шаг 1. Исходные данные задачи записываются на рабочем листе электронной таблицы. Один из вариантов показан на рис. 2.
Замечание. Если известно исходное допустимое базисное решение, то можно несколько ускорить процесс поиска оптимального решения. Для этого начальные значения некоторых или всех переменных могут быть заданы вручную. В данном примере для их хранения используются ячейки $B$2, $C$2 и $D$2. Если допустимое базисное решение не задано, то программа Excel автоматически определяет начальные значения переменных задачи.
Шаг 2. В ячейку E3 вводится формула
СУММПРОИЗВ(В3:D3; $B$2:$D$2)
для вычисления текущего значения целевой функции, которая находит сумму попарных произведений ячеек (В3:D3) с коэффициентами при переменных в выражении целевой функции на ячейки ($B$2:$D$2) с текущими значениями переменных.
Шаг 3. Чтобы задать ограничения решаемой задачи, в ячейки E5, E6 и E7 копируется формула из ячейки E3. После этого в указанных ячейках должны быть получены формулы, представленные в табл. 2.
Таблица 2
|
СУММПРОИЗВ(В5:D5; $B$2:$D$2) |
|
|
СУММПРОИЗВ(В6:D6; $B$2:$D$2) |
|
|
СУММПРОИЗВ(В7:D7; $B$2:$D$2) |
Шаг 4. После создания таблицы с исходными данными курсор устанавливается в ячейку E3, содержащую формулу для вычисления целевой функции. Далее в меню Сервис выбирается команда Поиск решения , которая открывает диалоговое окно, приведенное на рис. 3.
В поле Установить целевую ячейку окна «Поиск решения», показанного на рис. 3, должен появиться адрес ячейки с формулой целевой функции (в данном примере это ячейка $E$3).
Затем в этом окне (рис. 3) заполняются следующие поля этого окна:
В поле Равной переключатель вида экстремума целевой функции устанавливается в положение максимальное значение (или минимальное значение при соответствующей постановке задачи);
В поле Изменяя ячейки указывается диапазон ячеек со значениями переменных задачи, выделяемый на рабочем листе электронной таблицы (в примере это ячейки $B$2:$D$2);
В поле Ограничения задаются ограничения исходной задачи. Для этого курсор устанавливается в поле ввода ограничений и нажимается кнопка Добавить . В результате выводится диалоговое окно «Добавление ограничения», показанное на рис. 4.
В этом окне в поле Ссылка на ячейку вводится адрес ячейки с формулой соответствующего ограничения (например, для ограничения (1) это будет ячейка E5), а в поле Ограничение указывается предельное значение, которое может принимать выбранное ограничение (в данном примере правая часть ограничения (1) находится в ячейке G5).
Следует заметить, что заполнение полей Ссылка на ячейку и Ограничение в окне «Добавление ограничения» можно выполнить выделением соответствующих ячеек рабочего листа электронной таблицы.
Затем выбирается вид отношения, связывающего левую и правую части ограничения, что показано на рис. 5.
После нажатия кнопки Добавить в окне «Добавление ограничения» (или кнопки ОК для ввода последнего ограничения) данное ограничение попадает в список ограничений решаемой задачи. С помощью кнопок Удалить и Изменить можно удалять выделенные в списке ограничения или вносить в них исправления.
Замечание . В окне «Добавление ограничения» можно указать, что все или некоторые переменные должны принимать только целые значения (рис. 5). Это позволяет получать решения задач целочисленного линейного программирования (полностью или частично целочисленных).
Шаг 5. После заполнения всех полей окна «Поиск решения» нажимается кнопка Параметры (рис. 3), которая открывает диалоговое окно «Параметры поиска решения», показанное на рис. 6.
В этом окне требуется установить флажки Линейная модель для решения задачи линейного программирования и Неотрицательные значения , если такое условие накладываются на все переменные задачи.
Здесь (рис. 6) также можно определить параметры процесса решения: предельное время поиска решения, максимальное количество итераций, точность и т.п. Флажок Показывать результаты итераций позволяет по шагам следить за поиском решения. Флажок Автоматическое масштабирование включается в том случае, когда разброс значений переменных очень велик.
Шаг 6. Задав необходимые параметры в окне «Параметры поиска решения», следует нажать на кнопку Выполнить для поиска решения задачи (рис. 3) в окне «Поиск решения». Если решение найдено, то на экран выводится окно с соответствующим сообщением (рис. 7).
Полученные результаты отображаются на рабочем листе электронной таблицы, как это показано на рис. 8. В частности, значения переменных - в ячейках $B$2:$D$2, значение целевой функции – в ячейке E3.
Таким образом,
получено оптимальное решение исходной
задачи в виде вектора
,
где
,
и
,
для которого значение целевой функцииF
максимально и составляет F
*
= 129825.
Результаты решения задачи линейного программирования также можно сохранить в виде отдельных рабочих листов с именами Отчет по результатам , Отчет по устойчивости и Отчет по пределам . Для сохранения результатов в виде отчетов необходимо предварительно в поле Тип отчета выделить требуемые типы отчетов (рис. 7). В этом же окне можно отказаться от полученных решений и восстановить исходные значения переменных.
Отчет по результатам для рассмотренной задачи показан на рис. 9.
В данном отчете
представлены оптимальное решение задачи
линейного программирования и его
расположение в области допустимых
решений. В графах Результат
выводятся
оптимальные значения целевой функции
F
*
и переменных задачи
,
а также их значения для исходного
базисного решения, с которого начинался
поиск оптимального решения (графаИсходное
значение
).
Состояние
ограничений (графа Статус
)
характеризует расположение точки
в области допустимых решений. ГрафаРазница
показывает разности между значениями
левых и правых частей ограничений
(невязки). Для связанного ограничения
невязка равна нулю, что свидетельствует
о расположение точки
на границе области допустимых решений,
которая задается этим ограничением.
Если ограничение являются не связанным,
то оно не влияет на оптимальное решение.
Замечание . В экономической интерпретации связанные ограничения соответствуют дефицитным ресурсам. Для не связанных ограничений графа Разница показывает оставшиеся объемы неиспользованных не дефицитных ресурсов. В рассмотренной задаче ограничения (1) и (3) соответствуют комплектующим изделиям и материалам, которые являются дефицитными ресурсами. Ограничение (2) является не связанным, т.е. не влияет на оптимальный план производства продукции по критерию максимальной прибыли. Это означает, что второй ресурс (сырье) не использован в объеме 292,5 ед.
В отчете по устойчивости (рис. 10) приведены границы устойчивости переменных задачи (графы Допустимое увеличение и Допустимое уменьшение коэффициентов целевой функции), а также границы устойчивости теневых цен (т.е. переменных двойственной задачи), в пределах которых оптимальное решение не изменяется. Большие значения пределов (1Е+30) означают фактическое отсутствие соответствующих границ, т.е. переменная может изменяться до бесконечности.
В графе Нормированная стоимость элемент во второй строке (-150) показывает, на сколько уменьшится значение функции, если в решении переменную x 2 увеличить на единицу. С другой стороны, при допустимом увеличении коэффициента функции при неизвестной x 2 на 150 единиц значение этой переменной не изменится, т.е. неизвестная x 2 будет равна нулю, а если выйти за пределы допустимого увеличения (коэффициент при x 2 увеличить более чем на 150), то неизвестная x 2 в решении будет больше нуля.
В отчете по пределам (рис. 11) показаны нижние и верхние пределы возможного изменения переменных (в пределах области допустимых решений) и соответствующие значения целевой функции (графа Целевой результат ) при этих изменениях. В частности, если x 1 = 0, а x 2 и x 3 остаются без изменений, то F = 2400 + 2100 + 180191,25 = 34425; при x 3 = 0 и неизменных x 1 и x 2 получим F = 240397,5 + 2100 + 1800 = 95400.
Для решения задач линейного программирования симплекс-методом в среде MS Excel заполняются ячейки исходными данными в режиме чисел и формулами математической модели.
MS Excel позволяет получить оптимальное решение без ограничения размерности системы неравенств целевой функции.
Решим задачу о выпускаемых изделиях симплекс-методом применяя надстройку «Поиск решения» в MS Excel.
1. Заполните таблицу Excel в режиме чисел (рис.1)
2. Заполните таблицу Excel в режиме формул (рис.2)
Рис.1 Таблица в режиме чисел
Рис.1 Таблица в режиме формул
Здесь: В9:С9 – результат (оптимальное количество изделий каждого вида);
В6:С6 – коэффициенты целевой функции;
В10 – значение целевой функции;
В3:С5 – коэффициенты ограничений;
D12:D14 – правая часть ограничений;
B12:B14 – вычисляемые (фактические) значения левой части ограничений.
Решим задачу с помощью команды Данные/Поиск решения. На экране появляется диалоговое окно Поиск решения.
В поле Установить целевую функция будет показана ссылка на активную ячейку, т.е. на В10. Причем эта ссылка абсолютная. В секции Равной устанавливаем переключатель Максимальному (минимальному) значению в зависимости от целевой функции. Ограничения устанавливаются с помощью кнопки Добавить, которая вызывает диалоговое окно их ввода Добавление ограничения.
В поле ввода Ссылка на ячейку: указывается адрес ячейки, содержащей формулу левой части ограничения. Затем выбирается из списка знак соотношения. В поле Ограничение указывается адрес ячейки, содержащей правую часть ограничения. Щёлкаем на кнопку Добавить и повторяем до следующего ограничения. После ввода всех ограничений нажимаем ОК.
Так как все переменные несут условия неотрицательности, то их положительность задается через кнопку Параметры в окне диалога Поиск решения. После щелчка по ней, на экране окно Параметры поиска решения.
Устанавливаем флажок Сделать переменные без ограничений неотрицательными и выбрать Метод решения Поиск решения линеных задач симплекс-методом. Щёлкаем на кнопке Найти решение.
Excel предъявит окно Результаты поиска решения с сообщением о том, что решение найдено, или о том, что не может найти подходящего решения.
Если вычисления оказались успешными, Excel предъявит следующее окно итогов. Их можно сохранить или отказаться. Кроме того, можно получить один из трёх видов отчётов (Результаты, Устойчивость, Пределы), позволяющие лучше осознать полученные результаты, в том числе, оценить их достоверность.
После найденного решения, в ячейках В9:С9 появится оптимальное количество изделий каждого вида.
При сохранении отчета выберите – Отчет по результатам (рис.3).
Из отчета видно, что ресурс 1 не используется полностью на 150 кг, а ресурс 2 и 3 используется полностью.
В результате получен оптимальный план, при котором изделий 1 вида необходимо выпустить в количестве 58 шт., а изделий 2 вида в количестве 42 шт. При этом прибыль от их реализации максимальная и составляет 4660 тыс.руб.
Рис.3 Отчет по результатам
1. Со станции формирования ежедневно отправляются пассажирские и скорые поезда, составленные из плацкартных, купейных и мягких вагонов. Число мест в плацкартном вагоне – 54, в купейном – 36, в мягком – 18. В таблице указаны состав поезда каждого типа и количество имеющихся в парке вагонов различного типа. Определить число скорых и пассажирских поездов, которые необходимо формировать ежедневно, чтобы число перевозимых пассажиров было максимальным.
Решение транспортных задач
Транспортными задачами называются задачи определения оптимального плана перевозок груза из данных пунктов отправления в заданные пункты потребления.
| b 1 | b 2 | … | b k | … | b g | |
| a 1 | } Статьи по теме:
Что такое кэшированные данные и кэширование?
Удобство использования на высоком уровне
Подробная расшифровка некоторых характеристик акустики
Как найти потерянный, украденный ноутбук
Как снять с флешки защиту от записи
Новое:
Популярное:
|
