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

Линейное программирование является разделом, с которого начала развиваться дисциплина «математическое программирование». Термин «программирование» в названии дисциплины ничего общего с термином «программирование (т.е. составление программ) для ЭВМ» не имеет, так как дисциплина «линейное программирование» возникла еще до того времени, когда ЭВМ стали широко применяться при решении математических, инженерных, экономических и других задач. Термин «линейное программирование» возник в результате неточного перевода английского «linear programming». Одно из значений слова «programming» - составление планов, планирование. Следовательно, правильным переводом «linear programming» было бы не «линейное программирование», а «линейное планирование», что более точно отражает содержание дисциплины. Однако, термин линейное программирование, нелинейное программирование и т.д. в нашей литературе стали общепринятыми. Задачи линейного программирования является удобной математической моделью для большого числа экономических задач (планирование производства, расходование материалов, транспортные перевозки и т.д.). Использование метода линейного программирования представляет собой важность и ценность - оптимальный вариант выбирается из достаточно значительного количества альтернативных вариантов. Также все экономические задачи, решаемые с применением линейного программирования, отличаются альтернативностью решения и определенными ограничивающими условиями.В электронных таблицах Excel с помощью функции поиска решения можно вести поиск значения в целевой ячейке, изменения значения переменных. При этом для каждой переменной можно задать ограничения, например верхнюю границу. Перед тем как запустить поиск решения, необходимо четко сформулировать в модели решаемую проблему, т.е. определить условия, выполняемые при оптимизации. Отправленной точкой при поиске оптимального решения является модель вычисления, созданная в рабочем листе. Программе поиска решения при этом необходимы следующие данные. 1. Целевая ячейка - это ячейка в модели вычисления, значения в которой должно быть максимизировано, минимизировано или же равняться определенному указанному значению. Она должна содержать формулу, которая прямо или косвенно ссылается на изменяемые ячейки, или же самой быть изменяемой. 2. Значения в изменяемых ячейках будут последовательно (методом итераций) изменяться до тех пор, пока не будет получено нужное значение в целевой ячейке. Эти ячейки, следовательно, прямо или косвенно должны влиять на значение целевой ячейки. 3. Вы можете задать как для целевой, так и для изменяемых ячеек, ограничения и граничные условия. Можно задать также ограничения для других ячеек. Прямо или косвенно присутствующих в модели. Программа предоставляет возможность задать специальные параметры, определяющие процесс поиска решения. После задания всех необходимых параметров можно запустить поиск решения. Функция поиска решения создаст по итогам своей работы три отчета, которые можно пометить в рабочую книгу.Ограничения - это условия, которые должны быть выполнены аппаратом поиска решения при оптимизации модели.

Изучение литературы показало, что:

1. Линейное программирование - это один из первых и наиболее подробно изученных разделов математического программирования. Именно линейное программирование явилось тем разделом, с которого начала развиваться сама дисциплина «математическое программирование».

Линейное программирование представляет собой наиболее часто используемый метод оптимизации. К числу задач линейного программирования можно отнести задачи:

• · рационального использования сырья и материалов; задачи оптимизации раскроя;
• · оптимизации производственной программы предприятий;
• · оптимального размещения и концентрации производства;
• · составления оптимального плана перевозок, работы транспорта;
• · управления производственными запасами;
• · и многие другие, принадлежащие сфере оптимального планирования.
• 2. Графический метод довольно прост и нагляден для решения задач линейного программирования с двумя переменными. Он основан на геометрическом представлении допустимых решений и ЦФ задачи.

Суть графического метода заключается в следующем. По направлению (против направления) вектора в ОДР производится поиск оптимальной точки. Оптимальной считается точка, через которую проходит линия уровня, соответствующая наибольшему (наименьшему) значению функции. Оптимальное решение всегда находится на границе ОДР, например, в последней вершине многоугольника ОДР, через которую пройдет целевая прямая, или на всей его стороне.

Рассмотрим пример задачи линейного программирования.

Требуется определить, в каком количестве надо выпустить продукцию четырех типов Прод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 , представляющие собой величины неиспользованных ресурсов.

Составим для исходной задачи двойственную задачу и введем дополнительные двойственные переменные v 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. Необходимо найти оптимальное соотношение объемов выпуска изделий, при котором прибыль от производства всей продукции будет максимальной.

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Частное образовательное учреждение высшего образования «Санкт-Петербургский университет технологий управления и экономики»

Кафедра экономики и менеджмента

КОНТРОЛЬНАЯ РАБОТА

По дисциплине: МЕТОДЫ ОПТИМАЛЬНЫХ РЕШЕНИЙ

Выполнил:

Студент (ка) 3 курса, группа № 19731Д/3-2

Крюк Альбина Владимировна

Руководитель:

к.э.н., доцент Ж.М. Козлова.

Барнаул 2016

• Введение
• Заключение
• ВВЕДЕНИЕ
• Решение широкого круга задач электроэнергетики и других отраслей народного хозяйства основывается на оптимизации сложной совокупности зависимостей, описанных математически с помощью некоторой «целевой функции» (ЦФ). Подобные функции можно записать для определения затрат на топливо для электростанций, на потери электроэнергии при транспорте ее от электростанции к потребителям и многие другие проблемные задачи. В таких случаях требуется найти ЦФ при определенных ограничениях, накладываемых на ее переменные. Если ЦФ линейно зависит от входящих в ее состав переменных и все ограничения образуют линейную систему уравнений и неравенств, то такая частная форма оптимизационной задачи получила название «задачи линейного программирования».
• Темы контрольной работы «Решение задач линейного программирования в MS Excel», получить практические навыки в использовании электронных таблиц Microsoft Excel и решения оптимизационных задач линейного программирования.

1. Типовые задачи оптимизации и их экономико-математические модели

Экономико-математическое моделирование представляет собой процесс выражения экономических явлений математическими мо­делями. Экономическая модель -- это схематичное представление экономического явления или процесса с использованием научной абстракции, отражение их характерных черт. Математические мо­дели -- основное средство решения задач оптимизации любой дея­тельности. По своей сути эти модели -- средство плановых расче­тов. Ценность их для экономического анализа и оптимизации реше­ний состоит в том, что они позволяют оценить напряженность плановых заданий, определить лимитирующую группу оборудова­ния, видов ресурсов, получать оценки их дефицитности и т.п. Мате­матическое моделирование экономических явлений и процессов дает возможность получить четкое представление об исследуемом объекте, охарактеризовать и количественно описать его внутреннюю струк­туру и внешние связи. Модель -- условный образ объекта управле­ния /1/.

Экономико-математическая модель должна быть адекватной действительности, отражать существенные стороны и связи изучаемо­го объекта. Отметим принципиальные черты, характерные для по­строения экономико-математической модели любого вида. Процесс моделирования можно условно подразделить на три этапа:

1) ана­лиз теоретических закономерностей, свойственных изучаемому яв­лению или процессу и эмпирических данных о его структуре и особенностях; на основе такого анализа формируются модели;

2) определение методов, с помощью которых можно решить задачу;

3) анализ полученных результатов.

Важнейшим моментом первого этапа моделирования является четкая формулировка конечной цели построения модели, а также определение критерия, по которому будут сравниваться различные варианты решения. Такими критериями в системе менеджмента могут быть:

а) максимизация полезного эффекта товара при ограни­чении совокупности затрат;

б) максимизация прибыли фирмы при условии, что качество товара не снизится; в) снижение себестоимо­сти товара при условии, что его качество не снизится, затраты у потребителя не увеличатся;

г) рост производительности труда, улуч­шение использования оборудования или материалов, повышение оборачиваемости оборотных средств при условии, что качество то­вара не снизится и другие критерии не ухудшатся.

Таким образом, в качестве критерия оптимизации может быть целое или любой компонент прибыли, эффективности товара, объема рынка при ус­ловии, что другие компоненты при этом не ухудшатся.

Например, уравнение целевой функции (L) и система ограниче­ний по оптимизации прибыли фирмы (правда, у авторов нет огра­ничений по качеству товара) будет иметь следующий вид:

где хj -- количество производимой продукции j-го вида в нату­ральных измерениях;

Пj -- прибыль, получаемая от производства единицы про­дукции j-го вида;

аij -- норма расхода i-го производственного ресурса на про­изводство единицы j-го вида продукции;

щj -- запасы i-го вида производственного ресурса на рас­сматриваемый период времени.

Не для всякой экономической задачи нужна собственная модель. Некоторые процессы с математической точки зрения однотипны и могут описываться одинаковыми моделями. Например, в линейном программировании, теории массового обслуживания и других су­ществуют типовые модели, к которым приводится множество конк­ретных задач.

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

Третьим этапом моделирования является всесторонний анализ результата, полученного при изучении экономического явления. Окончательным критерием достоверности и качества модели явля­ются практика, соответствие полученных результатов и выводов реальным условиям, экономическая содержательность полученных оценок. Если результаты не соответствуют реальным условиям, то необходим анализ причин несоответствия, в качестве которых могут быть недостоверность информации, несоответствие модели эконо­мическим условиям и др. По результатам анализа причин несоответствия экономико-математическая модель корректируется и ре­шение задачи повторяется.

Решим графическим методом типовую задачу оптимизации

Некоторая фирма выпускает два набора удобрений для газонов: обычный и улучшенный. В обычный набор входит 3 кг азотных, 4 кг фосфорных и 1 кг калийных удобрений, а в улучшенный - 2 кг азотных, 6 кг фосфорных и 3 кг калийных удобрений. Известно, что для некоторого газона требуется по меньшей мере 10 кг азотных, 20 кг фосфорных и 7 кг калийных удобрений. Обычный набор стоит 3 ден. Ед., а улучшенный - 4 ден. Ед. Какие и сколько наборов удобрений нужно купить, чтобы обеспечить эффективное питание почвы и минимизировать стоимость?

Построить экономико-математическую модель задачи, дать необходимые комментарии к ее элементам и получить решение графическим методом. Что произойдет, если решать задачу на максимум, и почему?

Сформулируем прямую оптимизационную задачу.

Пусть х1 - количество обычных наборов удобрений;

х2 - количество улучшенных наборов удобрений.

А для некоторого газона требуется по крайней мере 10 кг азотных удобрений, следовательно:

3х1 + 2х2 ? 10

4х1 + 6х2 ? 20

Стоимость необходимых наборов удобрений составит:

Таким образом, получим следующую экономико-математическую модель задачи:

min (х) = 3х1 + 4х2

3х1 + 2х2 ? 10

4х1 + 6х2 ? 20

Построим область решений системы ограничений. Для этого рассмотрим равенства и построим их графики - прямые.

1) 3х1 + 2х2 ? 10

3х1 + 2х2 = 10

3) х1 + 3х2 ? 7

Неравенство не выполняется, значит, исходному неравенству соответствует полуплоскость, не содержащая точку О(0;0).

х1 = 0 - ось ОХ2.

х2 = 0 - ось ОХ1.

Следовательно, область решений системы ограничений находится только в первой четверти декартовой системы координат.

Рис.1. Графическое решение ЗЛП

Находим общую часть всех построенных полуплоскостей. Это выпуклая заштрихованная область.

Для нахождения оптимального решения задачи изобразим графически функцию цели:

(х) = d1x1 + d2x2

(х) = 3х1 + 4х2

Для этого строим вектор d, начало которого в точке (0;0), а конец в точке (d1;d2).

И строим одну из линий уровня функции цели (это линия, на которой функция цели принимает постоянное значение).

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

Определим координаты точки В:

3х1 + 2х2 = 10 *(-3)

4х1 + 6х2 = 20

9х1 - 6х2 = -30

4х1 + 6х2 = 20

Складываем почленно уравнения и получаем:

(х) = 3*2 + 4*2 = 14 (ден. ед.)

Таким образом, чтобы минимизировать стоимость удобрений, нужно купить 2 обычных набора удобрений и 2 улучшенных набора удобрений. При этом минимальные затраты на покупку удобрений составят 14 денежных единиц. microsoft excel программирование математический

Если решать данную задачу на максимум, то конечного оптимума не найдем, т.к. функция цели неограниченна, область решений системы ограничений бесконечна.

2. Задачи линейного программирования, решение средствами MS Excel

Линейное программирование является разделом, с которого начала развиваться дисциплина «математическое программирование». Термин «программирование» в названии дисциплины ничего общего с термином «программирование (т.е. составление программ) для ЭВМ» не имеет, так как дисциплина «линейное программирование» возникла еще до того времени, когда ЭВМ стали широко применяться при решении математических, инженерных, экономических и других задач. Термин «линейное программирование» возник в результате неточного перевода английского «linear programming». Одно из значений слова «programming» - составление планов, планирование. Следовательно, правильным переводом «linear programming» было бы не «линейное программирование», а «линейное планирование», что более точно отражает содержание дисциплины. Однако, термин линейное программирование, нелинейное программирование и т.д. в нашей литературе стали общепринятыми. Задачи линейного программирования является удобной математической моделью для большого числа экономических задач (планирование производства, расходование материалов, транспортные перевозки и т.д.). Использование метода линейного программирования представляет собой важность и ценность - оптимальный вариант выбирается из достаточно значительного количества альтернативных вариантов. Также все экономические задачи, решаемые с применением линейного программирования, отличаются альтернативностью решения и определенными ограничивающими условиями.
В электронных таблицах Excel с помощью функции поиска решения можно вести поиск значения в целевой ячейке, изменения значения переменных. При этом для каждой переменной можно задать ограничения, например верхнюю границу. Перед тем как запустить поиск решения, необходимо четко сформулировать в модели решаемую проблему, т.е. определить условия, выполняемые при оптимизации. Отправленной точкой при поиске оптимального решения является модель вычисления, созданная в рабочем листе. Программе поиска решения при этом необходимы следующие данные. 1. Целевая ячейка - это ячейка в модели вычисления, значения в которой должно быть максимизировано, минимизировано или же равняться определенному указанному значению. Она должна содержать формулу, которая прямо или косвенно ссылается на изменяемые ячейки, или же самой быть изменяемой. 2. Значения в изменяемых ячейках будут последовательно (методом итераций) изменяться до тех пор, пока не будет получено нужное значение в целевой ячейке. Эти ячейки, следовательно, прямо или косвенно должны влиять на значение целевой ячейки. 3. Вы можете задать как для целевой, так и для изменяемых ячеек, ограничения и граничные условия. Можно задать также ограничения для других ячеек. Прямо или косвенно присутствующих в модели. Программа предоставляет возможность задать специальные параметры, определяющие процесс поиска решения. После задания всех необходимых параметров можно запустить поиск решения. Функция поиска решения создаст по итогам своей работы три отчета, которые можно пометить в рабочую книгу.Ограничения - это условия, которые должны быть выполнены аппаратом поиска решения при оптимизации модели.

Изучение литературы показало, что:

1. Линейное программирование - это один из первых и наиболее подробно изученных разделов математического программирования. Именно линейное программирование явилось тем разделом, с которого начала развиваться сама дисциплина «математическое программирование».

Линейное программирование представляет собой наиболее часто используемый метод оптимизации. К числу задач линейного программирования можно отнести задачи:

· рационального использования сырья и материалов; задачи оптимизации раскроя;

· оптимизации производственной программы предприятий;

· оптимального размещения и концентрации производства;

· составления оптимального плана перевозок, работы транспорта;

· управления производственными запасами;

· и многие другие, принадлежащие сфере оптимального планирования.

2. Графический метод довольно прост и нагляден для решения задач линейного программирования с двумя переменными. Он основан на геометрическом представлении допустимых решений и ЦФ задачи.

Суть графического метода заключается в следующем. По направлению (против направления) вектора в ОДР производится поиск оптимальной точки. Оптимальной считается точка, через которую проходит линия уровня, соответствующая наибольшему (наименьшему) значению функции. Оптимальное решение всегда находится на границе ОДР, например, в последней вершине многоугольника ОДР, через которую пройдет целевая прямая, или на всей его стороне.

ЗАКЛЮЧЕНИЕ

С помощью правильной постановки задачи планирования производства и наличия основных производственных параметров, мы можем найти план выпуска продукции, при котором будет достигнута максимальная прибыль.

Благодаря программному продукту Excel, который входит в пакет MS Office, решение наших задач ускоряется в несколько десятков раз. А благодаря точным математическим расчетам данного ПО, мы можем без сомнения найти самые точные результаты исследований.

Размещено на Allbest.ru

...

Подобные документы

Краткие сведения об электронных таблицах MS Excel. Решение задачи линейного программирования. Решение с помощью средств Microsoft Excel экономической оптимизационной задачи, на примере "транспортной задачи". Особенности оформления документа MS Word.

курсовая работа , добавлен 27.08.2012


История развития и функции линейного программирования. Исследование условий типовых задач и возможностей табличного процессора. Решение задач о рационе питания, плане производства, раскрое материалов и рациональной перевозке груза в среде MS Excel.

курсовая работа , добавлен 28.04.2014


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

лабораторная работа , добавлен 26.10.2013


Алгоритм решения задач линейного программирования симплекс-методом. Построение математической модели задачи линейного программирования. Решение задачи линейного программирования в Excel. Нахождение прибыли и оптимального плана выпуска продукции.

курсовая работа , добавлен 21.03.2012


Изучение и укрепление на практике всех моментов графического метода решения задач линейного программирования о производстве журналов "Автомеханик" и "Инструмент". Построение математической модели. Решение задачи с помощью электронной таблицы Excel.

курсовая работа , добавлен 10.06.2014


Общее понятие и характеристика задачи линейного программирования. Решение транспортной задачи с помощью программы MS Excel. Рекомендации по решению задач оптимизации с помощью надстройки "Поиск решения". Двойственная задача линейного программирования.

дипломная работа , добавлен 20.11.2010


Анализ метода линейного программирования для решения оптимизационных управленческих задач. Графический метод решения задачи линейного программирования. Проверка оптимального решения в среде MS Excel с использованием программной надстройки "Поиск решения".

курсовая работа , добавлен 29.05.2015


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

курсовая работа , добавлен 07.06.2010


Методы решения задач линейного программирования: планирования производства, составления рациона, задачи о раскрое материалов и транспортной. Разработка экономико-математической модели и решение задачи с использованием компьютерного моделирования.

курсовая работа , добавлен 13.03.2015


Графическое решение задач. Составление математической модели. Определение максимального значения целевой функции. Решение симплексным методом с искусственным базисом канонической задачи линейного программирования. Проверка оптимальности решения.

Рассмотрим линейное программирование в Excel на примере задачи, ранее решенной .

Задача. Николай Кузнецов управляет небольшим механическим заводом. В будущем месяце он планирует изготавливать два продукта (А и В), по которым удельная маржинальная прибыль оценивается в 2500 и 3500 руб., соответственно. Изготовление обоих продуктов требует затрат на машинную обработку, сырье и труд. На изготовление каждой единицы продукта А отводится 3 часа машинной обработки, 16 единиц сырья и 6 единиц труда. Соответствующие требования к единице продукта В составляют 10, 4 и 6. Николай прогнозирует, что в следующем месяце он может предоставить 330 часов машинной обработки, 400 единиц сырья и 240 единиц труда. Технология производственного процесса такова, что не менее 12 единиц продукта В необходимо изготавливать в каждый конкретный месяц. Необходимо определить количество единиц продуктов А и В, которые Николай доложен производить в следующем месяце для максимизации маржинальной прибыли.

Скачать заметку в формате , пример в формате

1. Воспользуемся математической моделью построенной . Вот эта модель:

Максимизировать: Z = 2500 * х 1 + 3500 *х 2

При условии, что: 3 * х 1 + 10 * х 2 ≤ 330

16 * х 1 + 4 * х 2 ≤ 400

6 * х 1 + 6 * х 2 ≤ 240

2. Создадим экранную форму и введем в нее исходные данные (рис. 1).

Рис. 1. Экранная форма для ввода данных задачи линейного программирования

Обратите внимание на формулу в ячейке С7. Это формула целевой функции. Аналогично, в ячейки С16:С18 введены формулы для расчета левой части ограничений.

3. Проверьте, если у вас установлена надстройка «Поиск решения» (рис. 2), пропустите этот пункт.

Рис. 2. Надстройка Поиск решения установлена; вкладка «Данные», группа «Анализ»

Если надстройки «Поиск решения» вы на ленте Excel не обнаружили, щелкните на кнопку Microsoft Office, а затем Параметры Excel (рис. 3).

Рис. 3. Параметры Excel

Выберите строку Надстройки, а затем в самом низу окна «Управление надстройками Microsoft Excel» выберите «Перейти» (рис. 4).

Рис. 4. Надстройки Excel

В окне «Надстройки» установите флажок «Поиск решения» и нажмите Ok (рис. 5). (Если «Поиск решения» отсутствует в списке поля «Надстройки», чтобы найти надстройку, нажмите кнопку Обзор. В случае появления сообщения о том, что надстройка для поиска решения не установлена на компьютере, нажмите кнопку Да, чтобы установить ее.)

Рис. 5. Активация надстройки «Поиск решения»

После загрузки надстройки для поиска решения в группе Анализ на вкладке Данные становится доступна команда Поиск решения (рис. 2).

4. Следующим этапом заполняем окно Excel «Поиск решения» (рис. 6)

Рис. 6. Заполнение окна «Поиск решения»

В поле «Установить целевую ячейку» выбираем ячейку со значением целевой функции – $C$7. Выбираем, максимизировать или минимизировать целевую функцию. В поле «Изменяя ячейки» выбираем ячейки со значениями искомых переменных $C$4:$D$4 (пока в них нули или пусто). В области «Ограничения» с помощью кнопки «Добавить» размещаем все ограничения нашей модели. Жмем «Выполнить». В появившемся окне «Результат поиска решения» выбираем все три типа отчета (рис. 7) и жмем Ok. Эти отчеты нужны для анализа полученного решения. Подробнее о данных, представленных в отчетах, можно почитать .

Рис. 7. Выбор типов отчета

На основном листе появились значения максимизированной целевой функции – 130 000 руб. и изменяемых параметров х 1 = 10 и х 2 = 30. Таким образом, для максимизации маржинального дохода Николаю в следующем месяце следует произвести 10 единиц продукта А и 30 единиц продукта В.

Если вместо окна «Результат поиска решения» появилось что-то иное, Excel`ю найти решение не удалось. Проверьте правильность заполнения окна «Поиск решения». И еще одна маленькая хитрость. Попробуйте уменьшить точность поиска решения. Для этого в окне «Поиск решения» щелкните на Параметры (рис. 8.) и увеличьте погрешность вычисления, например, до 0,001. Иногда из-за высокой точности Excel не успевает за 100 итераций найти решение. Подробнее о параметрах поиска решения можно почитать .

Рис. 8. Увеличение погрешности вычислений