Параметры задачи о распределении ресурсов

Ресурс	Телевизор	Монитор	Моноблок	Запас ресурса
Пластиковые формы	2,5	1,7	2,1
Электронные кабели	3,7	2,2	2,8
Электронные платы	4,5	2,1	3,5
Трудозатраты	5,0	3,0	4,5
Прибыль от реализации изделия	3,0	1,0	2,0	–

Пусть переменная обозначает количество телевизоров, − количество мониторов, а − количество моноблоков, выпускаемых предприятием. Тогда, например, затраты по ресурсу «Пластиковые формы» на данном предприятии, согласно заданным технологическим коэффициентам определяются зависимостью . При этом затраты по ресурсу «Пластиковые формы» не должны превышать 150 единиц, заданных в качестве имеющегося на предприятии запаса, т.е. ограничение по ресурсу «Пластиковые формы будет иметь вид: . Аналогичным образом могут быть составлены ограничения по остальным ресурсам.

Поскольку количество выпущенной продукции не может быть отрицательной величиной, естественно потребовать, чтобы введенные переменные были больше либо равны нулю.

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

Полная математическая модель рассматриваемой задачи о распределении ресурсов будет иметь вид:

(1.4)

Решив систему ограничений (1.4), например, симплексным методом, получим следующий оптимальный план: при этом Следовательно, для заданных ограничений по ресурсам максимально возможная прибыль предприятия составляет 78 условных денежных единиц, которая достигается при выпуске только телевизоров. Однако в ходе развития производства ограничения по одному или нескольким видам ресурсов могут изменяться. В этом случае будет изменяться и оптимальное решение задачи. В рассматриваемой задаче достаточно увеличить ресурс "трудозатраты", чтобы предприятию стало выгодно выпускать и другие виды продукции.

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

1.2. Инструкция по использованию редактора Microsoft Excel
для решения ЗЛП

1) Ввести условие задачи:

а) создать экранную форму для ввода условия задачи:

– переменных,

– целевой функции (ЦФ),

– ограничений,

– граничных условий;

б) ввести исходные данные в экранную форму:

– коэффициенты ЦФ,

– коэффициенты при переменных в ограничениях,

– правые части ограничений;

в) ввести зависимости из математической модели в экранную форму:

– формулу для расчета ЦФ,

– формулы для расчета значений левых частей ограничений;

г) задать ЦФ (в окне «Поиск решения»):

– целевую ячейку,

– направление оптимизации ЦФ;

д) ввести ограничения и граничные условия (в окне «Поиск решения»):

– ячейки со значениями переменных,

– граничные условия для допустимых значений переменных,

– соотношения между правыми и левыми частями ограничений.

2) Решить задачу:

а) установить параметры решения задачи (в окне «Поиск решения»);

б) запустить задачу на решение (в окне «Поиск решения»);

в) выбрать формат вывода решения (в окне «Результаты поиска решения»).

1.3. Порядок решения

1. Найти оптимальное решение ЗЛП, соответствующей номеру выбранного варианта, с помощью редактора электронных таблиц Microsoft Excel.

2. Найти оптимальное целочисленное решение ЗЛП, соответствующей номеру выбранного варианта, с помощью редактора электронных таблиц Microsoft Excel.

3. Подготовить отчет по результатам выполненной лабораторной работы.

1.4. Варианты заданий

Вариант 1:

Вариант 2:

Вариант 3:

Вариант 4:

Вариант 5:

Вариант 6:

Вариант 7:

Вариант 8:

Вариант 9:

Вариант 10:

2. анализ чувствительности Задачи линейного программирования с помощью microsoft excel

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

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

Ограничения линейной модели классифицируются следующим образом (рис. 2.1). Связывающие ограничения проходят через оптимальную точку, например, (1) и (2). Несвязывающие ограничения не проходят через оптимальную точку, например, (3), (4) и (5). Аналогично ресурс, представляемый связывающим ограничением, называют дефицитным, а ресурс, представляемый несвязывающим ограничением, – недефицитным. Ограничение называют избыточным в том случае, если его исключение не влияет на область допустимых решений и, следовательно, на оптимальное решение, например, (5).

Выделяют три вида анализа ЗЛП на чувствительность:

1) Анализ сокращения или увеличения ресурсов.

а) На сколько можно увеличить (ограничения типа ) или уменьшить (ограничения типа ) запас дефицитного ресурса для улучшения оптимального значения ЦФ?

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

2) Увеличение (уменьшение) запаса какого из ресурсов наиболее выгодно?

3) Анализ изменения целевых коэффициентов: каков диапазон изменения коэффициентов ЦФ, при котором не меняется оптимальное решение?

Рис. 2.1. ЗЛП в графическом представлении

Для того чтобы выяснить, запас какого из дефицитных ресурсов выгоднее увеличивать в первую очередь, необходимо определить, какую пользу (например, прибыль) принесет увеличение запасов каждого из них на единицу. Для этих целей вводится понятие ценности дополнительной единицы i-го ресурса (теневая цена):

(2.1)

.

То есть сначала наращивается запас ресурса, имеющего максимальное значение (2.1), затем – второе по величине и т.д.

2.2. Анализ чувствительности в Microsoft Excel

Для выполнения анализа чувствительности ЗЛП необходимо после получения в Excel результатов ее решения (окно «Результаты поиска решения») выделить с помощью мыши два типа отчетов: «Результаты» и «Устойчивость».

Отчет по результатам состоит из трех таблиц:

1) Первая таблица содержит информацию о ЦФ.

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

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

Если ресурс используется полностью (то есть ресурс дефицитный), то в графе «Статус» («Состояние») соответствующее ограничение указывается как «связанное»; при неполном использовании ресурса (то есть ресурс недефицитный) в этой графе указывается «не связан». В графе «Значение» приведены величины использованного ресурса.

Для граничных условий в графе «Разница» показана разность между значением переменной в найденном оптимальном решении и заданным для нее граничным условием.

Третья таблица отчета по результам дает информацию для анализа возможного изменения запасов недефицитных ресурсов при сохранении полученного оптимального значения ЦФ. Так, если на ресурс наложено ограничение типа , то в графе «Разница» дается количество ресурса, на которое была превышена минимально необходимая норма. Если на ресурс наложено ограничение типа , то в графе «Разница» дается количество ресурса, которое не используется при реализации оптимального решения.

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

1) Результат решения задачи.

2) Нормированная стоимость, которая показывает, на сколько изменится значение ЦФ в случае принудительного включения единицы этой продукции в оптимальное решение.

3) Коэффициенты ЦФ.

4) Предельные значения приращения целевых коэффициентов, при которых сохраняется первоначальное оптимальное решение.

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

1) Величина использованных ресурсов («Результ. значение»).

2) Предельные значения приращения ресурсов.

3) Ценность дополнительной единицы i-го ресурса (значение в столбце «Теневая цена», которое рассчитывается только для дефицитных ресурсов).

В столбцах «Допустимое Уменьшение»«Допустимое Увеличение» показано, на сколько можно уменьшить (устранить излишек) или увеличить (повысить минимально необходимое требование) ресурс, сохранив при этом оптимальное решение.

2.3. Порядок выполнения лабораторной работы

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

2) Используя построенную математическую модель найдите оптимальное решение ЗЛП в Excel.

3) Получите в Excel все типы отчетов по результатам поиска решения, необходимые для анализа чувствительности, и проанализируйте ЗЛП на чувствительность к изменениям параметров исходной модели.

4) Подготовьте отчет с результатами решения ЗЛП и ее анализа на чувствительность.

2.4. Постановка задачи

Мебельный комбинат выпускает книжные полки А из натурального дерева со стеклом, полки из полированной ДСП (древесно-стружечной плиты) без стекла и полки из полированной ДСП со стеклом. Габариты полок следующие: длина d мм, ширина w мм, высота h мм. Размер листа ДСП метра.

При изготовлении полок А выполняются следующие работы: столярные, покрытие лаком, сушка, резка стекла, упаковка. Все операции, производимые в ходе столярных работ и упаковки, выполняются вручную. Полки и поставляются в торговую сеть в разобранном виде. За исключением операции упаковки, все остальные операции (производство комплектующих полки, резка стекла) при изготовлении полок и , выполняются на специализированных автоматах.

Трудоемкость столярных работ по выпуску одной полки А составляет часов. Производительность автомата, покрывающего полки А лаком – полок в час, автомата, режущего стекло – стекол в час. Сменный фонд времени автомата для покрытия лаком – часов, автомата для резки стекла – часов. Сушка полок, покрытых лаком, происходит в течение суток в специальных сушилках, вмещающих V1полок. На упаковку полки А требуется минуты. В производстве полок заняты Р1столяров и Р2упаковщиков.

Производительность автомата, производящего комплектующие полок и , равна Пр3полки в час, а его сменный фонд времени равен ФВ3часов, трудоемкость упаковочных работ составляет Тр3минут для полки и Тр4минут для полки .

От поставщиков комбинат получает в месяц Z1листов полированной ДСП, Z2листов ДВП (древесно-волокнистой плиты), а также Z3листов стекла. Из каждого листа ДВП можно выкроить К1задних стенок полок и , а из каждого листа стекла – К2стекол для полок А и .

Склад готовой продукции может разместить не более V2полок и комплектов полок, причем ежедневно в торговую сеть вывозится в среднем N полок и комплектов. На начало текущего месяца на складе осталось Ост полок, произведенных ранее. Себестоимость полки А равна C1руб., полки В без стекла – C2руб., со стеклом – С3руб.

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

Составьте план производства полок на текущий месяц. Известны цены реализации полок: полка А – Ц1руб., полка В без стекла – Ц2руб., полка В со стеклом – Ц3руб.

2.5. Варианты заданий

Численные значения параметров задачи приведены в табл. 2.1. При решении задачи следует считать, что рабочая смена состоит из 8 часов (одна смена в день), а в месяце 22 рабочих дня.

Таблица 2.1

Варианты заданий

№ вар.
D
w
h
Тр1	4,4	3,6	4,8	3,2	5,2	2,8	5,6	2,4	6,0	2,0
Тр2
Тр3
Тр4
Р1
Р2

Окончание табл. 2.1

№ вар.
Пp1
Пp2
Пp3
ФВ1	7,1	7,2	7,3	7,4	7,5	7,6	7,7	7,1	7,2	7,0
ФВ2	7,6	7,7	7,0	7,1	7,2	7,3	7,4	7,5	7,6	7,7
ФВ3	7,5	7,6	7,7	7,8	7,4	7,5	7,6	7,7	7,8	7,4
Z1
Z2
Z3
К1
К2
V1
V2
V3
N
Ост
Д	15(A)	10(B1)	15(B)	43(A,B1)	72(A)	12(B2)	16(B)	23(A,B2)	46(A)	59(B1)
З	30(А)	15(B1)	10(A), 18(B1)	5(A), 12(B2)	40(B1), 3(B2)	60(B2)	24(А)	80(B1)	14(A), 21(B1)	38(A), 62(B2)
C1
C2
C3
Ц1
Ц2
Ц3

3. решение транспортной задачи с помощью
microsoft excel

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

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

Стандартная ТЗ определяется как задача разработки наиболее экономичного плана перевозки продукции одного вида из нескольких пунктов отправления в пункты назначения. При этом величина транспортных расходов прямо пропорциональна объему перевозимой продукции и задается с помощью тарифов на перевозку единицы продукции.

Исходные параметры модели ТЗ:

1) n – количество пунктов отправления, m – количество пунктов назначения.

2) – запас продукции в пункте отправления [ед. тов.].

3) – спрос на продукцию в пункте назначения [ед. тов.].

4) – тариф (стоимость) перевозки единицы продукции из пункта отправления в пункт назначения [руб./ед. тов.].

Искомые параметры модели ТЗ:

1) – количество продукции, перевозимой из пункта отправления в пункт назначения [ед. тов.].

2) – транспортные расходы на перевозку всей продукции [руб.].

Математическая модель транспортной задачи:

(3.1)

Целевая функция представляет собой транспортные расходы на осуществление всех перевозок в целом. Первая группа ограничений указывает, что запас продукции в любом пункте отправления должен быть равен суммарному объему перевозок продукции из этого пункта. Вторая группа ограничений указывает, что суммарные перевозки продукции в некоторый пункт потребления должны полностью удовлетворить спрос на продукцию в этом пункте. Наглядной формой представления модели ТЗ является транспортная матрица (табл. 3.1).

Таблица 3.1