Решение задач линейного программирования в Excel - Реферат. Решение транспортной задачи с помощью средства поиск решения

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

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

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

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

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

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

Цель: научиться решать задачи линейного программирования в Excel с помощью надстройки «Поиск решения».

Краткие теоретические сведения

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

Постановка задачи линейного программирования (ЗЛП).

Имеется множество переменных X= (x 1 , х 2 ,..., х n). Целевая функция линейно зависит от управляемых параметров:

Имеются ограничения, которые представляют собой линейные формы

где (2)

Требуется определить максимум (минимум) линейной функции

при условии, что точка (х 1 , х 2 ,..., х n) принадлежит некоторому множеству D, которое определяется системой линейных неравенств

(4)

Любое множество значений (х 1 *, х 2 *,..., х n *), которое удовлетворяет системе неравенств (4) задачи линейного программирования, является допустимым решением данной задачи. Если при этом выполняется неравенство

c 1 х 1 o + c 2 х 2 o +..+ c n х n o ≥ c 1 х 1 + c 2 х 2 +..+ c n х n

для всего множества значений x 1 , х 2 ,..., х n , то значение х 1 o ..х n o является оптимальным решением задачи линейного программирования.

Пример построения математической модели и решения ЗЛП.

Задача. Требуется определить, в каком количестве надо выпускать продукцию четырех типов A, B, C иD, для изготовления которой требуются ресурсы трех видов: трудовые, сырье и финансы. Количество ресурса каждого вида, необходимое для выпуска единицы продукции данного типа, называется нормой расхода. Нормы расхода, а также прибыль, получаемая от реализации единицы каждого типа продукции, приведены в таблице1. Там же приведено наличие располагаемого ресурса.

Таблица1.

Ресурс	A	B	C	D	знак	наличие
трудовые

Составим математическую модель, для чего введем следующие обозначения:

x i - количество выпускаемой продукции i-го типа, i = 1,2,3,4

b j – количество располагаемого ресурса j-го вида, j = 1,2,3

a ji – норма расхода j-го ресурса для выпуска i-ой продукции

c i – прибыль от реализации единицы продукции i-го типа.

Как видно из таблицы 1, для выпуска единицы продукции A требуется 6 единиц сырья, значит, для выпуска всей продукции A требуется 6x 1 единиц сырья, где x 1 - количество выпускаемой продукции A . С учетом того, что для других видов продукции зависимости аналогичны, ограничение по сырью будет иметь вид:

6x 1 + 5x 2 + 4x 3 + 3x 4 ≤ 110

В этом ограничении левая часть равна величине требуемого ресурса, а правая часть показывает количество имеющегося ресурса.

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

x 1 + x 2 + x 3 + x 4 ≤ 16

6x 1 + 5x 2 + 4x 3 + 3x 4 ≤ 110

4x 1 + 6x 2 + 10x 3 + 13x 4 ≤ 100

x i ≥ 0, i=1,2,3,4

1. Для ввода условий задачи создадим форму в Excel (рис.1). В ячейках B3:E3 будут отображаться вычисленные значения x i .

рис.1. Форма для ввода условий задачи

2. Введем коэффициенты целевой функции и ограничений в форму. Из математической модели введем зависимости. Введенные данные отображены на рис.2.

рис.2. Исходные данные задачи

В ячейке F6 записана формула целевой функции, в F9-F11- левые части ограничений из математической модели. На рис. 3 отображен режим представления формул. Перейти к данному режиму можно с помощью последовательности действий: нажмите кнопку Microsoft Office , щелкните Параметры Excel, откройте вкладку Дополнительно и установите флажок Показывать формулы, а не их значения.

рис.3. Режим представления формул.

3. Загрузим надстройку поиск решения Данные │Анализ │Поиск решения .

4. В поле Установить целевую ячейку введем ссылку на целевую ячейку, для чего установим курсор в поле и щелкнем левой кнопкой мыши по ячейке F6.

5. Выберем направление поиска, установив флажок равной максимальному значению.

6. Установим курсор в поле Изменяя ячейки и введем с помощью мыши имена изменяемых ячеек B3:E3. В этих ячейках в результате поиска решения будет выведено решение – значения переменных x i ., при которых целевая функция имеет максимальное значение при заданных ограничениях.

7. Введем ограничения на искомые переменные: x i ≥ 0 (нижняя граница по умолчанию равна 0, количество выпускаемой продукции не может быть отрицательным). Так же введем ограничения на ресурсы (н е может быть использовано больше ресурсов, чем их запасы). Щелкнем по кнопке Добавить , в появившемся окне Добавление ограничения в левом поле с помощью мыши введем ссылку на ячейку B3, из раскрывающегося списка выберем знак ≥, в правом поле щелкнем мышью по ячейкеB4 (рис.4). Аналогично введем остальные ограничения.

Рис.4. Окно добавления ограничений.

На рисунке 5 показано заполненное окно Поиск решения.

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

8. Далее нажимаем на кнопку Выполнить. Появляется диалоговое окно Результаты поиска решения (рис.6). Решение найдено. Все ограничения и условия оптимальности выполнены. Сохраняем найденное решение. В этом окне также можно получить три вида отчетов: по результатам, устойчивости и пределам, отчеты формируются в новых рабочих листах.

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

Результаты оптимального решения задачи приведены в таблице (рис.7).

рис.7. Результаты оптимального решения

Таким образом, получилось оптимальное решение (10;0;6;0), т.е. целесообразно выпускать 10 единиц продукции А и 6 единиц продукции С. Максимальная прибыль равна 1320 денежным единицам, при этом используются все трудовые и финансовые ресурсы, 84 единиц сырья, в запасе остается 26 единиц сырья.

Задания для лабораторной работы.

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

Для перевозки грузов используются машины типов А и Б. Грузоподъемность машин обоих типов одинаковая и равна h т. За одну ходку машина А расходует а 11 кг смазочных материалов и а 12 л горючего, машина Б - а 21 кг смазочных материалов иа 22 л горючего. На базе имеется d 1 кг смазочных материалов и d 2 л горючего. Прибыль от перевозки одной машины А составляет с 1 руб., машины Б - с 2 руб. Необходимо перевезти H т груза (исходные данные приведены в нижеследующей таблице).

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

№ варианта

Инструкция по выполнению лабораторной работы.

1. Изучить теоретический материал.
2. Выполнить приведенный пример.
3. Выбрать свой вариант по последней цифре.
4. Составить математическую модель задачи.
5. Найти оптимальное решение с помощью Поиска решения.
6. Сделать выводы по полученным решениям, сформировать отчеты по результатам решения, устойчивости и пределам.
7. Создать отчет по лабораторной работе.

1. Титульный лист.
2. Словесная постановка задачи.
3. Математическая формулировка задачи.
4. Заполненное окно Поиск решения
5. Результаты поиска решения (таблица).
6. Выводы по полученным решениям.

Список источников

1. Гельман В.Я. Решение математических задач средствами Excel: Практикум. – СПб.:Питер, 2003
2. Курицкий Б.Я. Поиск оптимальных решений средствами Excel. – СПб.: BHV-Санкт-Петербург, 1997
3. Пазюк К.Т. Математические методы и модели в экономике. – Хабаровск: Издательство ХГТУ, 2002
4. Джон Уокенбах. MS OfficeExcel 2007 - Библия пользователя, Издатель: Вильямс, 2008

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

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

Размер: px

Начинать показ со страницы:

Транскрипт

1 Министерство образования и науки Российской Федерации Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования «Тихоокеанский государственный университет» Решение задач линейного программирования в Microsoft Excel 00 Методические указания к выполнению лабораторных работ по информатике для обучающихся по всем программам бакалавриата и специалитета дневной формы обучения Хабаровск Издательство ТОГУ 05

2 УДК 68.58(076.5) Решение задач линейного программирования в Microsoft Excel 00: методические указания к выполнению лабораторных работ по информатике для обучающихся по всем программам бакалавриата и специалитета дневной формы обучения / сост. Н. Д. Берман, Н. И. Шадрина. Хабаровск: Изд-во Тихоокеан. гос. ун-та, с. Методические указания составлены на кафедре информатики. Включают общие сведения о задачах линейного программирования, задания для выполнения лабораторных работ с вариантами задач, рекомендательный библиографический список. Печатается в соответствии с решениями кафедры информатики и методического совета факультета компьютерных и фундаментальных наук. Тихоокеанский государственный университет, 05

3 . ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ В MICROSOFT EXCEL 00. ОБЩИЕ СВЕДЕНИЯ Общая характеристика задач оптимизации Задачи линейной оптимизации относятся к широко распространённому классу задач, встречающихся в различных сферах деятельности: в бизнесе, на производстве, в быту. Как оптимально распорядиться бюджетом или за минимальное время добраться до нужного места в городе, как наилучшим образом спланировать деловые встречи, минимизировать риски капитальных вложений, определить оптимальные запасы сырья на складе это те задачи, в которых нужно найти наилучшее из всех возможных решений. Различают следующие типы линейных оптимизационных задач: задачи о перевозках, например, минимизация расходов по доставке товаров с нескольких фабрик в несколько магазинов с учетом спроса; задачи распределения рабочих мест, например, минимизация расходов на содержание штата с соблюдением требований, определенных законодательством; управление ассортиментом товаров: извлечение максимальной прибыли с помощью варьирования ассортиментным набором товаров (при соблюдении требований клиентов). Аналогичная задача возникает при продаже товаров с разной структурой затрат, рентабельностью и показателями спроса; замена или смешивание материалов, например, манипуляция материалами с целью снижения себестоимости, поддержания необходимого уровня качества и соблюдения требований потребителей; задача о диете. Из имеющихся в распоряжении продуктов требуется составить такую диету, которая, с одной стороны, удовлетворяла бы минимальным потребностям организма в питательных веществах (белки, жиры, углеводы, минеральные соли, витамины), с другой требовала бы наименьших затрат; задача распределения ресурсов, например, распределение ресурсов между работами таким образом, чтобы максимизировать прибыль, или минимизировать затраты, или определить такой состав работ, который можно выполнить, используя имеющиеся ресурсы, и при этом достичь максимума опре- 3

4 деленной меры эффективности, или рассчитать, какие ресурсы необходимы для того, чтобы выполнить заданные работы с наименьшими издержками. Математическая постановка задачи линейного программирования Рассмотрим наиболее распространенный класс оптимизационных задач задачи линейного программирования. К такому классу относятся задачи, описываемые линейными математическими моделями. Общей задачей линейного программирования называется задача, которая состоит в определении максимального (минимального) значения функции () при условиях: () () () (3) () (4) где заданные постоянные величины и Функция () называется целевой функцией задачи, а условия ()(4) ограничениями задачи. Совокупность чисел (), удовлетворяющих ограничениям задачи, называется допустимым решением. Решение, при котором целевая функция задачи принимает максимальное (минимальное) значение, называется оптимальным. Использование надстройки Excel для решения задач линейного программирования Поиск решения это надстройка EXCEL, которая позволяет решать оптимизационные задачи. Если команда Поиск решения или группа Анализ отсутствует, необходимо загрузить надстройку Поиск решения. 4

5 На вкладке Файл выберите команду Параметры, а затем категорию Надстройки (рис.). Рис. В поле Управление выберите значение Надстройки Excel и нажмите кнопку Перейти. В поле Доступные надстройки установите флажок рядом с пунктом Поиск решения (рис.) и нажмите кнопку ОК. Рис. Пример решения оптимизационных линейных задач в MS Excel 00 Схема решения задач линейного программирования в MS Excel 00 следующая: 5

6 . Составить математическую модель.. Ввести на рабочий лист Excel условия задачи: а) создать форму на рабочем листе для ввода условий задачи; б) ввести исходные данные, целевую функцию, ограничения и граничные условия. 3. Указать параметры в диалоговом окне Поиск решения. 4. Проанализировать полученные результаты. Рассмотрим решение задачи оптимизации на примере. Пример. Задача определения оптимального ассортимента продукции Предприятие изготавливает два вида продукции П и П, которая поступает в оптовую продажу. Для производства продукции используются два вида сырья А и В. Максимально возможные запасы сырья в сутки составляют 9 и 3 ед. соответственно. Расход сырья на единицу продукции вида П и П табл.. Таблица Сырье Расход сырья на ед. продукции П П Запас сырья, ед. А 3 9 В 3 3 Опыт работы показал, что суточный спрос на продукцию П никогда не превышает спроса на продукцию П более чем на ед. Кроме того, известно, что спрос на продукцию П никогда не превышает ед. в сутки. Оптовые цены единицы продукции равны: 3 д. е. для П и 4 д. е. для П. Какое количество продукции каждого вида должно производить предприятие, чтобы доход от реализации продукции был максимальным? Решение. Построим математическую модель для решения поставленной задачи. Предположим, что предприятие изготовит x единиц продукции П и x единиц продукции П. Поскольку производство продукции ограничено имеющимися в распоряжении предприятия сырьем каждого вида и спросом на данную продукцию, а также учитывая, что количество изготовляемых изделий не может быть отрицательным, должны выполняться следующие неравенства: 6

7 Доход от реализации x единиц продукции П и x единиц продукции П составит Cреди всех неотрицательных решений данной системы линейных неравенств требуется найти такое, при котором функция F принимает максимальное значения F max. Рассматриваемая задача относится к разряду типовых задач оптимизации производственной программы предприятия. В качестве критериев оптимальности в этих задачах могут быть также использованы: прибыль, себестоимость, номенклатура производимой продукции и затраты станочного времени. Создадим на рабочем листе форму для ввода исходных данных (рис. 3). Заливкой выделены ячейки для ввода функций. Рис. 3 В ячейку E5 введем формулу для целевой функции (рис. 4). Используя обозначения соответствующих ячеек в Excel, формулу для расчета целевой функции можно записать как сумму произведений каждой из ячеек, отведенной для значений переменных задачи (B3, C3), на соответствующие ячейки, отведенные для коэффициентов целевой функции (B5, C5). 7

8 Рис. 4 Аналогично в ячейки D0:D введены формулы для расчета левой части ограничений (рис. 5). Рис. 5 На вкладке Данные в группе Анализ выберем команду Поиск решения. В диалоговом окне Параметры поиска решения установим следующее (рис. 6): 8

9 в поле Оптимизировать целевую функцию выбираем ячейку со значением целевой функции Е5; выбираем, максимизировать или минимизировать целевую функцию; в поле Изменяя ячейки переменных выбираем ячейки со значениями искомых переменных B3:C3 (пока в них нули или пусто); в области В соответствии с ограничениями с помощью кнопки Добавить размещаем все ограничения нашей задачи (рис. 7); в поле Выберите метод решения указываем Поиск решения линейных задач симплекс-методом; нажимаем кнопку Найти решение. Рис. 6 9

10 Добавляем ограничения для нашей задачи. Для неравенств указываем в поле Ссылка на ячейки диапазон D0:D, выбираем в раскрывающемся списке знак неравенства, в поле Ограничение выделяем диапазон F0:F и нажимаем кнопку Добавить (рис. 7), чтобы принять ограничение и добавить следующее ограничение. Для принятия ограничения и возврата к диалоговому окну Поиск решения нажмите кнопку Ok. Рис. 7 Покажем окна для добавления ограничений: преобразуем в (рис. 8); Рис. 8 0

11 (рис. 9); Рис. 9, (рис. 0). Рис. 0 После выбора кнопки Найти решение появляется окно Результаты поиска решения (рис.). Рис.

12 Для сохранения полученного решения необходимо использовать переключатель Сохранить найденное решение в открывшемся окне диалога Результаты поиска решения. После чего рабочий лист примет вид, представленный на рис.. Рис. Сохранить модель поиска решения можно следующим образом:) при сохранении книги Excel после поиска решения все значения, введенные в окнах диалога Поиск решения, сохраняются вместе с данными рабочего листа. С каждым рабочим листом в рабочей книге можно сохранить один набор значений параметров Поиска решения;) если в пределах одного рабочего листа Excel необходимо рассмотреть несколько моделей оптимизации (например, найти максимум и минимум одной функции или максимальные значения нескольких функций), то удобнее сохранить эти модели, используя кнопку Загрузить/Сохранить окна Параметры поиска решения. Диапазон для сохраняемой модели содержит информацию о целевой ячейке, об изменяемых ячейках, о каждом из ограничений и все значения диалога Параметры. Выбор модели для решения конкретной оптимизационной задачи осуществляется с помощью кнопки Загрузить/сохранить диалогового окна Параметры поиска решения; 3) сохранить модель можно в виде именованных сценариев, для этого необходимо нажать на кнопку Сохранить сценарий диалогового окна Результаты поиска решений (см. рис.). Кроме вставки оптимальных значений в изменяемые ячейки, Поиск решения позволяет представлять результаты в виде трех отчетов (Результаты,

13 Устойчивость и Пределы). Для генерации одного или нескольких отчетов необходимо выделить их названия в окне диалога Результаты поиска решения (рис.). Рассмотрим более подробно каждый из них. Отчет по устойчивости (рис. 3) содержит информацию о том, насколько целевая ячейка чувствительна к изменениям ограничений и переменных. Этот отчет имеет два раздела: один для изменяемых ячеек, а второй для ограничений. Правый столбец в каждом разделе содержит информацию о чувствительности. Каждая изменяемая ячейка и ограничения приводятся в отдельной строке. При использовании целочисленных ограничений Excel выводит сообщение Отчеты об устойчивости и Пределы не применимы для задач с целочисленными ограничениями. Рис. 3 Отчет по результатам (рис. 4) содержит три таблицы: в первой приведены сведения о целевой функции до начала вычисления, во второй значения искомых переменных, полученные в результате решения задачи, в третьей результаты оптимального решения для ограничений. Этот отчет также содержит информацию о таких параметрах каждого ограничения, как статус и разница. Статус может принимать три состояния: связанное, несвязанное или невыполненное. Значение разницы это разность между значением, выводимым в ячейке ограничения при получении решения, и числом, заданным в правой части формулы ограничения. Связанное ограничение это ограничение, для которого значение разницы равно нулю. Несвязанное 3

14 ограничение это ограничение, которое было выполнено с ненулевым значением разницы. Рис. 4 Отчет по пределам (рис. 5) содержит информацию о том, в каких пределах значения изменяемых ячеек могут быть увеличены или уменьшены без нарушения ограничений задачи. Для каждой изменяемой ячейки этот отчет содержит оптимальное значение, а также наименьшие значения, которые ячейка может принимать без нарушения ограничений. Рис. 5 4

15 Полученное решение означает, что объем производства продукции вида П должен быть равен,4 ед., а продукции П,4 ед. продукции. Доход, получаемый в этом случае, составит,8 д. е. Допустим, что к условию задачи добавилось требование целочисленности значений всех переменных. В этом случае описанный выше процесс ввода условия задачи необходимо дополнить следующими шагами. В окне Поиск решения нажмите кнопку Добавить и в появившемся окне Добавление ограничений введите ограничения следующим образом (рис. 6): в поле Ссылка на ячейки введите адреса ячеек переменных задачи B3:C3; в поле ввода знака ограничения установите целое; подтвердите ввод ограничения нажатием кнопки OK. Рис. 6 Решение задачи при условии целочисленности ее переменных рис. 7. Рис. 7 5

16 . ЛАБОРАТОРНЫЕ РАБОТЫ Лабораторная работа Задание Найти максимум линейной функции при заданной системе ограничений. Вариант Целевая функция F Ограничения { { { { 3 { { 4 { { 5 { { 6 { { 7 { { 8 { { 9 { { 0 { { { { { { 3 { { 4 { { 5 { { 6

17 Лабораторная работа Задание. Построить математическую модель задачи.. Представить ее в табличной форме на листе Excel. 3. Найти решение задачи средствами надстройки Поиск решения. 4. Вывести отчеты по результатам и устойчивости. Вариант Для производства столов и шкафов мебельная фабрика использует необходимые ресурсы. Нормы затрат ресурсов на одно изделие данного вида, прибыль от реализации одного изделия и общее количество имеющихся ресурсов каждого вида табл.. Таблица Ресурсы Древесина, м 3: -го вида -го вида Нормы затрат ресурсов на одно изделие Стол Шкаф 0, 0, 0, 0,3 Общее количество ресурсов Трудоемкость, чел.ч,5 37,4 Прибыль от реализации одного изделия, р. 6 8 Определить, сколько столов и шкафов следует изготавливать фабрике, чтобы прибыль от их реализации была максимальной. Ответ. Прибыль 940 р. при количестве столов и шкафов 0 и 66. Вариант Для производства двух видов изделий A и В используется токарное, фрезерное и шлифовальное оборудование. Нормы затрат времени для каждого из типов оборудования на одно изделие данного вида, общий фонд рабочего времени каждого из типов оборудования, а также прибыль от реализации одного изделия табл. 3. 7

18 Таблица 3 Затраты времени, стан.-ч, Тип оборудования на обработку одного изделия А В Фрезерное 0 8 Токарное 5 0 Шлифовальное 6 Прибыль от реализации одного изделия, р. 4 8 Общий фонд полезного рабочего времени оборудования, ч Найти план выпуска изделий А и В, обеспечивающий максимальную прибыль от их реализации. Ответ. Прибыль 76 р. при выпуске изделий и 6. Вариант 3 Для изготовления трех видов изделий А, В и С используется токарное, фрезерное, сварочное и шлифовальное оборудование. Затраты времени на обработку одного изделия для каждого из типов оборудования, общий фонд рабочего времени каждого из типов используемого оборудования, прибыль от реализации одного изделия данного вида табл. 4. Таблица 4 Тип оборудования Фрезерное Токарное Сварочное Шлифовальное Затраты времени, стан.-ч, на обработку одного изделия вида А В С Прибыль, р. 0 4 Общий фонд рабочего времени оборудования, ч Требуется определить, сколько изделий и какого вида следует изготовить предприятию, чтобы прибыль от их реализации была максимальной. Ответ. Прибыль 49 р. при выпуске изделий 4, 8, 0. 8

19 Вариант 4 Для поддержания нормальной жизнедеятельности человеку ежедневно необходимо потреблять не менее 8 г белков, 56 г жиров, 500 г углеводов, 8 г минеральных солей. Количество питательных веществ, содержащихся в кг каждого вида потребляемых продуктов, а также цена кг каждого из этих продуктов табл. 5 Таблица 5 Питательные вещества Содержание, г, питательных веществ в кг продуктов Мясо Рыба Молоко Масло Сыр Крупа Картофель Белки Жиры Углеводы Минеральные соли Цена кг продуктов, р.,8,0 0,8 3,4,9 0,5 0, Составить дневной рацион, содержащий не менее минимальной суточной нормы потребности человека в необходимых питательных веществах при минимальной общей стоимости потребляемых продуктов. Ответ. Минимальная общая стоимость 0, р. при количестве продуктов: мясо 0; рыба 0; молоко 0; масло 0,03335; сыр 0; крупа 0,9053; картофель 0. Вариант 5 Кондитерская фабрика для производства трех видов карамели А, В, и С использует три вида основного сырья: сахарный песок, патоку и фруктовое пюре. Нормы расхода сырья каждого вида на производство т карамели данного вида, общее количество сырья каждого вида, прибыль от реализации т карамели табл. 6. 9

20 Таблица 6 Вид сырья Сахарный песок Патока Фруктовое пюре Нормы расхода сырья, т, на т карамели А В С 0,8 0,4 0,5 0,4 0, 0,6 0,3 0, Прибыль от реализации т продукции, р Общее количество сырья, т Найти план производства карамели, обеспечивающий максимальную прибыль от ее реализации. Ответ. Максимальная прибыль р. при выпуске карамели 00, 0, 00 т. Вариант 6 На швейной фабрике для изготовления четырех видов изделий может быть использована ткань трех артикулов. Нормы расхода тканей всех артикулов на пошив одного изделия, имеющееся в распоряжении фабрики общее количество тканей каждого артикула и цена одного изделия данного вида табл. 7. Таблица 7 Артикул ткани I II III Норма расхода ткани, м, на одно изделие вида 3 4 Цена одного изделия, р Общее количество ткани, м Определить, сколько изделий каждого вида должна произвести фабрика, чтобы стоимость изготовленной продукции была максимальной. Ответ. Максимальная стоимость продукции 5 р. при выпуске изделий 95, 0, 0, 0. 0

21 Вариант 7 Предприятие выпускает четыре вида продукции и использует три типа основного оборудования: токарное, фрезерное и шлифовальное. Затраты времени на изготовление единицы продукции для каждого из типов оборудования, общий фонд рабочего времени каждого из типов оборудования и прибыль от реализации одного изделия данного вида табл. 8. Таблица 8 Затраты времени, стан.-ч, Тип оборудования на единицу продукции вида 3 4 Токарное Фрезерное Шлифовальное Прибыль от реализации 3 единицы продукции, р. 8 3 Общий фонд рабочего времени, стан.-ч Определить такой объем выпуска каждого из изделий, при котором общая прибыль от их реализации является максимальной. Ответ. Максимальная прибыль 965 р. при выпуске изделий 70, 35, 0, 0. Вариант 8 Торговое предприятие планирует организовать продажу четырех видов товара, используя при этом только два вида ресурсов: рабочее время продавцов в количестве 840 ч и площадь торгового зала 80 м. При этом известны плановые нормативы затрат этих ресурсов в расчете на единицу товаров и прибыль от их продажи табл. 9. Таблица 9 Показатели Расход рабочего времени на единицу товара, ч Использование площади торгового зала на единицу товара, м Товар А В С D 0,6 0,8 0,6 0,4 0, 0, 0,4 0, Прибыль от продажи единицы товара, р Общее количество ресурсов

22 Требуется определить оптимальную структуру товарооборота, обеспечивающую торговому предприятию максимальную прибыль. Ответ. Максимальная прибыль 6 00 р. при продаже товаров 0, 0, 0, 800. Вариант 9 Из трех видов сырья необходимо составить смесь, в состав которой должно входить не менее 6 ед. химического вещества А, 30 ед. вещества В и 4 ед. вещества С. Количество единиц химического вещества, содержащегося в кг сырья каждого вида, цена кг сырья каждого вида табл. 0 Таблица 0 Вещество А В С Цена кг сырья, р. Количество единиц вещества, содержащегося в кг сырья вида Составить смесь, содержащую не менее нужного количества веществ данного вида и имеющую минимальную стоимость. Ответ. Минимальная стоимость 6 р. при количестве 0; 0; 0; 6,5 кг. Вариант 0 Для производства трех видов продукции предприятие использует два типа технологического оборудования и два вида сырья. Нормы затрат сырья и времени на изготовление одного изделия каждого вида, общий фонд рабочего времени каждой из групп технологического оборудования, объемы имеющегося сырья каждого вида, цена одного изделия каждого вида, ограничения на возможный выпуск каждого из изделий табл..

23 Ресурсы Производительность оборудования в нормочасах: I типа II типа Сырье, кг: -го вида -го вида Цена одного изделия, р. Выпуск, шт.: минимальный максимальный Нормы затрат на одно изделие вида Таблица Общее количество ресурсов Составить план производства продукции, по которому будет изготовлено необходимое количество изделий каждого вида, при максимальной общей стоимости всей изготовляемой продукции. Ответ. Общая стоимость 495 р. при выпуске продукции 0, 33, 45. Вариант При производстве четырех видов кабеля выполняется пять групп технологических операций. Нормы затрат на км кабеля данного вида для каждой из групп операций, прибыль от реализации км каждого вида кабеля, а также общий фонд рабочего времени, в течение которого могут выполняться эти операции, табл. Таблица Технологическая операция Нормы затрат времени, ч, на обработку км кабеля вида 3 4 Волочение Наложение изоляций Скручивание элементов в кабель Освинцовывание Испытание и контроль,0 6,4 3,0,8 0,4 5,6,5,6 0,8 6,0,8 0,8,4 0,7 8,0,4 3,0 Прибыль от реализации км кабеля, р., 0,8,0,3 Общий фонд рабочего времени, ч

24 Определить план выпуска кабеля, при котором общая прибыль от реализации изготовляемой продукции является максимальной. Ответ. Общая прибыль от реализации 939,48 57 р. при выпуске 00; 64,8 57; 0; 0. Вариант Стальные прутья длиной 0 см необходимо разрезать на заготовки длиной 45, 35 и 50 см. Требуемое количество заготовок данного вида составляет соответственно 40, 30 и 0 шт. Возможные варианты разреза и величина отходов при каждом из них табл. 3. Таблица 3 Варианты разреза Длина заготовки, см Величина отходов, см Определить, сколько прутьев по каждому из возможных вариантов следует разрезать, чтобы получить не менее нужного количества заготовок каждого вида при минимальных отходах. Ответ. Минимальные отходы равны 550 см при количестве прутьев 0, 0, 0, 0, 0, 0 шт. Вариант 3 Для производства трех видов изделий А, В, С предприятие использует четыре вида сырья. Нормы затрат сырья каждого вида на производство единицы продукции данного вида, прибыль от реализации одного изделия каждого вида табл. 4. 4

25 Таблица 4 Нормы затрат сырья, кг, на единицу продукции Вид сырья А В С I II III IV Прибыль от реализации одного изделия Изделия А, В и С могут производиться в любых соотношениях (сбыт обеспечен), но для их производства предприятие может использовать сырье I вида не более 00 кг, II вида не более 0 кг, III вида не более 80 кг, IV вида не более 38 кг. Определить план производства продукции, при котором общая прибыль предприятия от реализации всей продукции была бы наибольшей. Ответ. План производства изделий 7, 5, 0 кг при общей прибыли 5 кг. Вариант 4 Туристическое агентство собирается заказать издательству выпуск художественных альбомов трех типов A, B, C. Их изготовление лимитируется затратами ресурсов трех видов, удельные расходы которых приведены в табл. 5. Вид ресурса Финансы, $ Бумага, л. Трудозатраты, чел. ч Таблица 5 Удельные затраты ресурсов на выпуск альбомов A B C 4 4 Издательство для выполнения заказа получило финансовые средства в объеме $ 3 600, имеет в наличии л. бумаги и может использовать трудовые ресурсы в объеме 00 чел. ч. Агентство платит за выпуск одного альбома типа А дол., за альбом В 8 дол., за альбом С 30 дол. 5

26 Сколько альбомов каждого типа должно выпустить издательство, чтобы получить наибольшую прибыль? Ответ. Максимальный суммарный доход дол., количество альбомов: 400; 800; 0 шт. Вариант 5 Предприятие оптовой торговли может реализовать T j, j, 4 группы товаров. Для этого используется несколько видов ресурсов. Исходные данные для построения математической модели табл. 6. Лимитирующие ресурсы и показатели Товарная группа T T T 3 T4 Объем ресурса Таблица 6 Складские площади, м Трудовые ресурсы, чел.ч Издержки обращения, ден. ед Товарные запасы, ден. ед План товарооборота, ден. ед Минимально допустимые значения товарооборота по j-й группе, ед. Прибыль в расчете на единицу товарооборота j-й группы, ден. ед. Вид огра ниче- ния Требуется рассчитать план хозяйственной деятельности торгового предприятия, обеспечивающий максимум прибыли при заданных ограничениях на складские площади, трудовые ресурсы, издержки обращения, товарные запасы, величину товарооборота, если торговая прибыль в расчете на единицу товарооборота j -й группы задана. Ответ. Максимальна прибыль ден. ед. Товарооборот по группам: Т 00 ед., Т 000 ед., Т ед., Т ед. 6

27 3. РЕКОМЕНДАТЕЛЬНЫЙ БИБЛИОГРАФИЧЕСКИЙ СПИСОК. Акулич, И. Л. Математическое программирование в примерах и задачах: учеб. пособие для студентов экон. спец. сузов / И. Л. Акулич. М. : Высш. шк., с.. Леоненков, А. В. Решение задач оптимизации в среде MS Excel / А. В. Леоненков. СПб. : БХВ-Петербург, с. 3. Васильев, А. Н. Финансовое моделирование и оптимизация средствами Excel007 / А. Н. Васильев. СПб. : Питер, с. 4. Уокенбах, Дж. Microsoft Excel 00. Библия пользователя: пер. с англ. / Дж. Уокенбах. М. : И. Д. Вильямс, 0. 9 с. 5. Уокенбах, Дж. Формулы в Microsoft Excel 00: пер. с англ. / Дж. Уокенбах. М. : И. Д. Вильямс, с. 6. Иванов, И. Microsoft Excel 00 для квалифицированного пользователя / И. Иванов. М. : Академия АЙТИ, с. 7. Справка и инструкции по Excel // Поддержка по Microsoft Office [Электронный ресурс]. Режим доступа: (дата обращения:). 8. Решение задач оптимизации управления с помощью MS Excel 00 // НОУ «ИНТУИТ» [Электронный ресурс]. Режим доступа: (дата обращения:). Оглавление. Задачи линейного программирования в Microsoft Excel 00. Общие сведения... 3 Общая характеристика задач оптимизации... 3 Математическая постановка задачи линейного программирования... 4 Использование надстройки Excel для решения задач линейного программирования... 4 Пример решения оптимизационных линейных задач в MS Excel Лабораторные работы... 6 Лабораторная работа... 6 Лабораторная работа Рекомендательный библиографический список

28 Решение задач линейного программирования в Microsoft Excel 00 Методические указания к выполнению лабораторных работ по информатике для обучающихся по всем программам бакалавриата и специалитета дневной формы обучения Нина Демидовна Берман Нина Ивановна Шадрина Главный редактор Л. А. Суевалова Редактор Е. Н. Ярулина Подписано в печать Формат 60 x 84 / 6. Бумага писчая. Гарнитура «Калибри». Печать цифровая. Усл. печ. л.,68. Тираж 60 экз. Заказ 70. Издательство Тихоокеанского государственного университета, Хабаровск, ул. Тихоокеанская, 36. Отдел оперативной полиграфии издательства Тихоокеанского государственного университета, Хабаровск, ул. Тихоокеанская, 36. 8

ОБЪЕМНОЕ ПЛАНИРОВАНИЕ РАБОТЫ ТЕХНОЛОГИЧЕСКИХ СТАНОЧНЫХ СИСТЕМ Х а б а р о в с к 2 0 0 9 Федеральное агентство по образованию Государственное образовательное учреждение высшего профессионального образования

Практическое занятие 3. 1. Для данных условий сформулируйте оптимизационную задачу, составьте математическую модель, найдите оптимальный план производства с помощью надстройки «Поиск решения» в EXCEL.

Министерство образования и науки Российской Федерации Федеральное государственное бюджетное образовательное учреждение высшего образования «Тихоокеанский государственный университет» Н. И. Шадрина, Н.

Составление, решение и анализ задачи линейного программирования в Excel ЗАДАНИЕ. Построить математическую модель задачи и решить её средствами Excel. Записать сопряжённую задачу. Провести анализ и сделать

Задача распределения ресурсов предприятия Содержательная постановка задачи Фабрика выпускает сумки: женские, мужские, дорожные. Данные о материалах, используемых для производства сумок и месячный запас

Лабораторная работа 11 Решение задачи оптимального распределения ресурсов Задание Предприятие выпускает продукты нескольких видов. Для их изготовления используется сырье различного типа. Известны нормы

Лабораторная работа 3_9. Поиск и принятие решений в Excel. Что осваивается и изучается? Решение задачи определения оптимального плана и транспортной задачи при помощи надстройки «Поиск решения». Задание

Лабораторная работа 3. Поиск решения в Microsoft Excel Целью лабораторной работы является изучение возможностей средства Поиск решения MS Excel для решения оптимизационных задач. К защите лабораторной

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РФ ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬ- НОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ «ДОНСКОЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ» Кафедра «Технология

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ОБРАЗОВАНИЯ «ТИХООКЕАНСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ» Совместная работа

ЛАБОРАТОРНАЯ РАБОТА СРЕДСТВА ПОДДЕРЖКИ ПРИНЯТИЯ РЕШЕНИЙ КАК ФУНКЦИИ EXCEL Команда Подбор параметра Задание 1. Рассмотрим задачу, составленную на основании задачи по использованию функции ЧПС. Вас просят

ВАРИАНТ Для изготовления изделий двух видов имеется 00 кг металла. На одно изделие -го вида расходуется кг металла, а изделия -говида кг. Составить план производства, обеспечивающий получение наибольшей

Лабораторная работа 4 Тема работы: Решение задачи об оптимальном распределении ресурсов при выпуске продукции с использованием процедуры Поиск решения Microsoft Excel. Цель работы: Научиться использовать

Практическая работа 5.4. Решение задачи об оптимальном распределении ресурсов при выпуске продукции с использованием процедуры «Поиск решения» Microsoft Excel Цель работы. Выполнив эту работу, Вы научитесь:

Московская Государственная Академия Тонкой Химической Технологии имени М. В. Ломоносова Корнюшко В.Ф., Морозова О.А. Детерминированные модели экономических систем Методическое пособие по дисциплине Математические

МИНИСТЕРСТВО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ КУРГАНСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ КАФЕДРА «ИНФОРМАТИКА» РЕАЛИЗАЦИЯ ОПТИМИЗАЦИОННЫХ МОДЕЛЕЙ В СРЕДЕ EXCEL Методические указания к проведению лабораторных

Оптимизация производственной программы Методические указания к лабораторной работе по экономике электротехнической промышленности Ульяновск 009 В 9 Васильев, В. Н. Оптимизация производственной программы

Экономико-математические методы и моделирование. Практическая работа 2. Симплексный метод решения задач линейного программирования. Решить задачу линейного программирования (ЛП) симплексным методом. Расчеты

РАБОТА 2 РЕШЕНИЕ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ Цель работы: ознакомление с методами решения задач линейного программирования в табличном процессоре Ecel. Решение экономических задач, как правило, связано

ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ Государственное образовательное учреждение высшего профессионального образования «Тихоокеанский государственный университет» Кафедра «Технология деревообработки» МОДЕЛИРОВАНИЕ

АНАЛИЗ ДАННЫХ В MS EXCEL Гедранович Валентина Васильевна 27 июня 2012 г. Аннотация Глава 11 из УМК: Гедранович, В.В. Основы компьютерных информационных технологий: учеб.-метод. комплекс / В.В. Гедранович,

Решение задачи линейного программирования графическим методом, симплекс-методом и через «Поиск решения» в Ecel ЗАДАНИЕ. Предприятие выпускает два вида продукции: Изделие и Изделие. На изготовление единицы

Лабораторная работа 3. Надстройка Поиск решения в Microsoft Excel. Диспетчер сценариев в Microsoft Excel. Целью данной лабораторной работы является изучение возможностей средства Поиск решения в Microsoft

Негосударственное образовательное частное учреждение высшего профессионального образования Уральский институт фондового рынка Кафедра Экономики предприятия ЭКОНОМИКА ФИРМЫ Сборник кейсов тема «Планирование

Практическое занятие 4. Для условий задачи cформулируйте двойственную задачу и найдите объективно обусловленные оценки. Проанализируйте использование ресурсов в оптимальном плане. Вариант 1. Для изготовления

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ федеральное государственное бюджетное образовательное учреждение высшего профессионального образования «Курганский государственный университет» Кафедра

ЛАБОРАТОРНАЯ РАБОТА 6 Тема: Анализ данных в OpenOffice Calc 1. Основные понятия Процесс изменения значений ячеек и анализа влияния этих изменений на результат вычисления формул в OpenOffice.org Calc называется

Подбор параметра При обработке табличных данных часто возникает необходимость в прогнозировании результата на основе известных исходных данных или наоборот, в определении того, какими должны быть исходные

2 ПЛАН ЛЕКЦИИ: АНАЛИЗ ДАННЫХ В MS EXCEL Информатика 2 семестр Кондратенко Ольга Брониславовна [email protected] Инструмент анализа «что если» Инструмент анализа «что если» создание таблиц данных с одной

Практическая работа 13 Тема: ЗАДАЧИ ОПТИМИЗАЦИИ (ПОИСК РЕШЕНИЯ) В MICROSOFT EXCEL Цель занятия. Изучение технологии поиска решения для задач оптимизации (минимизации, максимизации). Задание 13.1. Минимизация

Приложение Содержимое кейса Задача 1 Одна вновь организованная коммерческая фирма решила выпускать два типа стульев х1 и х2. Для их производства необходимо два вида материалов: дерево и ткань. Фирма ежемесячно

ЛАБОРАТОРНАЯ РАБОТА 2 ИСПОЛЬЗОВАНИЕ MICROSOFT EXCEL 2007 ПРИ РЕШЕНИИ ПРАКТИЧЕСКИХ ЗАДАЧ (ДЛЯ СТУДЕНТОВ НАПРАВЛЕНИЯ 100800.62) 2.1 Решение задач оптимизации Задача. Завод производит электронные приборы

МОСКОВСКИЙ РАДИОТЕХНИЧЕСКИЙ КОЛЛЕДЖ им. А.А.Расплетина ЛАБОРАТОРНАЯ РАБОТА По предмету «Математические методы» «Двухиндексные задачи линейного программирования» Составил: Преподаватель МРТК им.а.а.расплетина

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РФ федеральное государственное автономное образовательное учреждение высшего образования «НАЦИОНАЛЬНЫЙ ИССЛЕДОВАТЕЛЬСКИЙ ТОМСКИЙ ПОЛИТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ» УТВЕРЖДАЮ

СОДЕРЖАНИЕ. ЗАДАНИЕ.... ЭТАПЫ РАБОТЫ..... Формирование математической модели задачи..... Решение прямой задачи симплекс-методом..... Построение двойственной задачи... 6.4. Решение прямой и двойственной

ЛАБОРАТОРНАЯ РАБОТА РЕШЕНИЕ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ С ИСПОЛЬЗОВАНИЕМ Microsoft Ecel ЦЕЛЬ РАБОТЫ Приобретение навыков решения задач линейного программирования (ЛП) в табличном редакторе Microsoft

МИНОБРНАУКИ РОССИИ Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования «САМАРСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ» Кафедра «Технология машиностроения»

Министерство образования и науки Российской Федерации Федеральное государственное бюджетное образовательное учреждение высшего образования «НИЖЕГОРОДСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ ИМ. Р.

Тверь Реферат Сервис Содержание Задача 1. Ассортимент продукции... 3 Условие задачи... 3 Математическая постановка задачи... 3 Табличная модель задачи... 5 Отчет о результатах решения задачи 1.... 6 Вывод...

ЗАДАНИЕ ПРАКТИЧЕСКОЙ РАБОТЫ 4 И ПРАКТИЧЕСКОЙ РАБОТЫ 5 Задачи линейной оптимизации Построение экономико-математических моделей (ЭММ). Решение задач линейной оптимизации с использованием информационных технологий.

ЛАБОРАТОРНЫЕ РАБОТЫ ПО MS EXCEL 2007 ЛАБОРАТОРНАЯ РАБОТА 1.... 1 ЛАБОРАТОРНАЯ РАБОТА 2... 3 ЛАБОРАТОРНАЯ РАБОТА 3... 4 ЛАБОРАТОРНАЯ РАБОТА 4... 7 ЛАБОРАТОРНАЯ РАБОТА 5... 8 ЛАБОРАТОРНАЯ РАБОТА 6... 10

Федеральное агентство по образованию Государственное образовательное учреждение высшего профессионального образования Ульяновский государственный технический университет ИНФОРМАЦИОННЫЕ СИСТЕМЫ В ЭКОНОМИКЕ

1 Лабораторная работа 3 Решение задач. Подбор параметров, поиск решения 1. Реализация математической модели в Excel Математическая модель это описание состояния поведения некоторой реальной системы (объекта,

Gnumeric: электронная таблица для всех И.А.Хахаев, 2007-2010 7 Линейная оптимизация (поиск решения) 7.1 Оптимизация как задача линейного программирования Пусть имеется функция, называемая целевой, линейно

ФЕДЕРАЛЬНОЕ АГЕНТСТВО ЖЕЛЕЗНОДОРОЖНОГО ТРАНСПОРТА Государственное образовательное учреждение высшего профессионального образования «МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ПУТЕЙ СООБЩЕНИЯ» Институт экономики

МИНОБРНАУКИ РОССИИ Федеральное государственное бюджетное образовательное учреждение высшего образования «Самарский государственный технический университет» ИНЖЕНЕРНО-ЭКОНОМИЧЕСКИЙ ФАКУЛЬТЕТ КАФЕДРА ЭКОНОМИКИ

ЗАНЯТИЕ ПРИБЛИЖЕННОЕ РЕШЕНИЕ НЕЛИНЕЙНЫХ УРАВНЕНИЙ Отделение корней Пусть дано уравнение f () 0, () где функция f () C[ a; Определение Число называется корнем уравнения () или нулем функции f (), если

Министерство образования и науки Российской Федерации Федеральное агентство по образованию Саратовский государственный технический университет РЕШЕНИЕ ЗАДАЧ ОПТИМИЗАЦИИ В СРЕДЕ MS EXCEL Методические указания

«Юго-Западный государственный университет» ЮЗГУ) Кафедра конструирования и технологии электронновычислительных средств МЕТОДЫ УСЛОВНОЙ ОПТИМИЗАЦИИ Методические указания по выполнению лабораторной работы

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования «Тихоокеанский государственный университет»

ФЕДЕРАЛЬНОЕ АГЕНТСТВО ЖЕЛЕЗНОДОРОЖНОГО ТРАНСПОРТА ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ «МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ПУТЕЙ СООБЩЕНИЯ» (МИИТ)

МИНОБРНАУКИ РОССИИ Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования «Самарский государственный технический университет» (ФГБОУ ВПО «СамГТУ») Кафедра

Министерство образования и науки РФ Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования Уральский государственный лесотехнический университет Кафедра

Лабораторная работа 4 «Электронные таблицы Excel и автоматизация вычислений на ПК» РАЗДЕЛ 4. Решение систем уравнений и оптимизационных задач. Вычислительные возможности программы Excel достаточно широки,

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

ФЕДЕРАЛЬНОЕ АГЕНСТВО ЖЕЛЕЗНОДОРОЖНОГО ТРАНСПОРТА ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ «МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ПУТЕЙ СООБЩЕНИЯ

АНАЛИЗ УСТОЙЧИВОСТИ КОММЕРЧЕСКОЙ ДЕЯТЕЛЬНОСТИ ПРЕДПРИЯТИЯ Дегтярёва Нина Адамовна, к.э.н., доцент Коммерческая работа - это деятельность предприятия, направленная на решение особого комплекса задач. Изучение

ЛАБОРАТОРНАЯ РАБОТА 2 РЕШЕНИЕ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ 1. Цели работы: построение математической модели задачи линейного программирования; решение задачи линейного программирования графическим

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

Решить задачи линейного программирования в Excel достаточно просто: 1) внести исходные данные задачи и ограничения, 2) запустить надстройку Поиск решения, 3) установить нужные параметры решения и запустить выполнение. Программа подберет оптимальное решение, выдаст отчеты для анализа решения задачи.

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

Линейное программирование: примеры решений в Excel

Задача 1. Построить математическую модель задачи и решить её средствами Excel. Записать сопряжённую задачу. Провести анализ и сделать выводы по полученным результатам.
Для производства столов и шкафов мебельная фабрика использует различные ресурсы. Нормы затрат ресурсов на одно изделие данного вида, прибыль от реализации одного изделия и общее количество имеющихся ресурсов каждого вида приведены в таблице.
Определить, сколько столов и шкафов фабрике следует выпускать, чтобы прибыль от реализации была максимальной.

Задача 2. Цех производит 8 различных видов деталей для двигателей A, B, C1, C2, C3, D, E6, F имея в своем распоряжении перечисленный ниже парк из 7 видов универсальных станков: 2 шт. -ADF, 3 шт. -SHG, 3 шт. -BSD, 1 шт. -AVP, 1 шт. -BFG, 3 шт. -ABM, 2 шт. -RL.
Время, требуемое для обработки единицы каждого продукта на каждом станке, вклад в прибыль от производства единицы каждого продукта и рыночный спрос на каждый продукт за месяц даны в таблице.
Цех работает 12 часов в день. Каждый месяц содержит 26 рабочих дней. Для упрощения задачи считаем, что возможен произвольный порядок обработки деталей на различных станках.
Составьте оптимальный план производства.
Определите, производство каких продуктов лимитировано рынком, и каких – техническими возможностями цеха. Какие машинные ресурсы должны быть увеличены в первую очередь, чтобы добиться максимального увеличения прибыли (при заданных потребностях рынка)?
Есть ли продукт, который невыгодно производить? Почему? Что нужно изменить, чтобы все продукты стало выгодно производить?

Задача 3. Необходимо составить самый дешевый рацион питания цыплят, содержащий необходимое количество определенных питательных веществ тиамина Т и ниацина Н. Пищевая ценность рациона (в калориях) должна быть не менее заданной. Смесь для цыплят изготавливается из двух продуктов - К и С. Известно содержание тиамина и ниацина в этих продуктах, а также питательная ценность К и С (в калориях). Сколько К и С надо взять для одной порции куриного корма, чтобы цыплята получили необходимую им дозу веществ Н и Т и калорий (или больше), а стоимость порции была минимальна? Исходные данные для расчетов приведены в таблице.

Задача 4. Фирма "Компьютер-сервис" поставляет компьютеры под ключ четырех базовых комплектаций: «домашний», «игровой», «офисный» и «экстрим». Известны средние затраты времени на сборку, проверку и подключение компьютеров. Каждый компьютер приносит определенный уровень прибыли, но спрос ограничен. Кроме того, в плановом периоде ограничен ресурс человеко-часов, отведенных на выполнение каждой производственной операции. Определить, сколько компьютеров каждого типа необходимо произвести в плановом периоде, имея целью максимизировать прибыль.

Задача 5. На лесопилку поступают доски длиной 10 м. По контракту лесопилка должна поставить клиенту не менее 100 досок длиной 5 м, не менее 200 досок длиной 4 м и не менее 300 досок длиной 3 м. Как работникам лесопилки выполнить условия контракта, разрезав наименьшее количество досок?

Задача 6. Компания "Евростройтур" организует экскурсионные автобусные туры по странам Европы. Компания получила 4 новых автобуса и предполагает направить их на маршруты во Францию, Италию, Чехию и Испанию. Каждый автобус обслуживают 2 водителя. Компанией приглашены 8 водителей, в различной степени знакомых с дорогами европейских стран (в % от экскурсионного маршрута).
Необходимо распределить водителей так, чтобы общий показатель освоения маршрутов был максимальным.

Задача 7. Решить задачу методом ветвей и границ, решая отдельные задачи линейного нецелочисленного программирования с помощью функции "Поиск решения" в Microsoft Excel (в случае, если первая же задача ЛП выдает целочисленное решение, не позволяя ветвить задачу, немного изменить начальные условия).
Состав еды рядовых регламентируется верховной ставкой главнокомандующего, которая устанавливает нижние нормы питания в сутки по основным компонентам: 1500 килокалорий, 100 г белков, 280 г углеводов, 90 г жиров, 1 кг воды. На складах есть 4 вида продуктов, которые выдают защитникам Родины сухим пайком: лимонад, тушенка в маленьких банках, унифицированные наборы горбушек и пирожки с ежевикой. Стоимость этих четырех продуктов соответственно 12 руб., 34 руб., 3 руб. и 20 руб. Какова минимальная сумма, которую должен затратить прапорщик на питание одного солдата?

Задача 8. Предприятие выпускает два вида продукции: Изделие 1 и Изделие 2. На изготовление единицы Изделия 1 требуется затратить a11 кг сырья первого типа, a21 кг сырья второго типа, a31 кг сырья третьего типа.
На изготовление единицы Изделия 2 требуется затратить a12 кг сырья первого типа, a22 кг сырья второго типа, a32 кг сырья третьего типа.
Производство обеспечено сырьем каждого типа в количестве b1 кг, b2 кг, b3 кг соответственно.
Рыночная цена единицы Изделия 1 составляет c1 тыс. руб., а единицы Изделия 2 - c2 тыс.руб.
Требуется:
1) построить экономико – математическую модель задачи;
2) составить план производства изделий, обеспечивающий максимальную выручку от их реализации при помощи графического метода решения задачи линейного программирования.
3) составить план производства изделий, обеспечивающий максимальную выручку от их реализации при помощи табличного симплекс – метода решения задачи линейного программирования.
4) составить план производства изделий, обеспечивающий максимальную выручку от их реализации, используя надстройку «Поиск решения» в среде MS EXCEL.