В. М. Паклина е. М. Паклина подготовка документов средствами microsoft office 2013 Учебно-методическое пособие



Pdf просмотр
страница4/5
Дата24.12.2016
Размер4.69 Mb.
Просмотров740
Скачиваний0
ТипУчебно-методическое пособие
1   2   3   4   5
Решение задач оптимизации
Задачи оптимизации занимают очень важное место в бизнесе, производстве, прогнозировании. Условно эти задачи можно разделить на следующие категории:
− транспортная задача – минимизация расходов на транспортировку товаров;
− задача о назначениях – составление штатного расписания с мини- мизацией денежных затрат на заработную плату или времени выполнения работ;
− задачи оптимизации производства – максимизация выпуска товаров при ограничениях на сырье для производства этих товаров.
Прежде чем искать оптимальное решение задачи, необходимо построить ее математическую модель, т. е. осуществить перевод условия и решения на четкий язык математических отношений.
Задача оптимизации в общем виде формулируется следующим образом.
Найти значения переменных x
1
, x
2
, … , x
n
, такие, что целевая функция f(x
1
,
x
2
, …, x
n
) примет максимальное, минимальное или заданное значения при ограничениях вида g(x
1
, x
2
, …, x
n
).
Таким образом, задача оптимизации содержит три основных компонента:
переменные x
1
, x
2
, …, x
n
– определяемые величины;
целевая функция – это цель, записанная математически в виде функции от переменных, принимающая максимальное, минималь- ное или заданное значения;
ограничения – условия или соотношения, которым должны удовлетворять переменные.
MS Excel предоставляет возможность решения оптимизационных задач с помощью надстройки Поиск решения. При этом после создания матема- тической модели на рабочем листе Excel создается табличная модель, где

75 в отдельных ячейках содержатся переменные решения, в отдельные ячейки записаны формулы, по которым будут вычисляться целевая функция и функции ограничений.
Продемонстрируем эту возможность на примере решения следующей транспортной задачи.
Пример 1. Компания «Атлант» хранит свою продукцию на трех складах
(первом, втором и третьем), расположенных в разных частях города. На этих складах хранится продукция в количествах 1000, 3000 и 2500 штук соответственно.
Продукцию необходимо доставить четырем оптовым покупателям «Урал», «Купец», «Гелиос» и «Меркурий» с минимальными затратами, заявки которых составляют 1300, 800, 2700 и 1700 штук соответственно. Склады оптовых покупателей также расположены в разных частях города. Стоимости (в рублях) доставки одной штуки продукции со складов компании на склады покупателей показаны в табл. 7.
Таблица 7
Стоимость доставки продукции
Склады компании
Оптовые покупатели
«Урал»
«Купец»
«Гелиос»
«Меркурий»
№ 1 50 150 60 75
№ 2 100 30 100 40
№ 3 70 180 210 120 1. Построим математическую модель задачи: определим переменные, целевую функцию и ограничения.
Пусть:
x
11
, x
12
, x
13
, x
14
, x
21
, x
22
, x
23
, x
24
, x
31
, x
32
, x
33
, x
34
– количество продукции, перевозимой со складов компании на соответствующие склады покупателей;

76
z=50 x
11
+ 150 x
12
+ 60 x
13
+ 75 x
14
+ 100 x
21
+ 30 x
22
+100 x
23
+40 x
24
+
+70x
31
+180 x
32
+ 210 x
33
+ 120 x
34
– целевая функция, общая стоимость доставки грузов покупателям;
x
11
+ x
12
+ x
13
+ x
14
=1000,
x
21
+ x
22
+x
23
+x
24
=3000,
x
31
+x
32
+ x
33
+ x
34
=2500 – ограничения для складов компании;
x
11
+ x
21
+ x
31
=1300,
x
12
+ x
22
+ x
32
=800,
x
13
+ x
23
+ x
33
=2700,
x
14
+ x
24
+ x
34
=1700 – ограничения для складов покупателей.
2. Имеем сбалансированную транспортную задачу, так как спрос поку- пателей (1300 + 800 + 2700 + 1700 = 6500) равен предложению произво- дителей (1000 + 3000 + 2500 = 6500).
3. Запустите табличный процессор MS Excel. Переименуйте Лист 1 в Сбалансированная модель.
4. Составьте табличную модель Excel (рис. 65).

77

Рис. 65. Сбалансированная модель
5. Последняя таблица не обязательна. Целевую функцию можно было вычислить по формуле:
=СУММПРОИЗВ(В4:Е6;В13:Е15).
6. Выделите целевую ячейку и запустите надстройку Поиск решения
(Данные Анализ Поиск решения).

78 7. В появившемся диалоговом окне Поиск решения укажите адреса целевой ячейки, диапазон изменяемых ячеек и ограничения (рис. 66). Целевую ячейку установите равной минимальному значению.
Рис. 66. Диалоговое окно «Поиск решения»
8. В диалоговом окне параметры Поиска решения установите флажки
Линейная модель, Неотрицательные значения и Автоматическое
масштабирование.
9. В диалоговом окне Поиск решения нажмите кнопку Выполнить.
10. Получаем оптимальное решение задачи (рис. 67).

79

Рис. 67. Оптимальное решение задачи
11. Скопируйте полученную табличную модель на Лист 2 рабочей книги и переименуйте его в Несбалансированная задача.
12. Решим эту же задачу, немного изменив условие.
13. Пусть на складе № 1 хранится не 1000 штук продукции, а 500. В таком случае на трех складах компании хранится 6000 штук продукции, покупатели по-прежнему заказывают
6500 штук.
Перед нами транспортная задача с дефицитом.
14. Несбалансированная задача решается аналогично сбалансированной.
Изменения коснутся только ограничений. Причем в ограничениях для складов покупателей знак «=» заменяется знаком «≤».
15. После выполнения надстройки Поиск решения (рис. 68) получаем, что покупатель «Гелиос» недополучит 500 ед. продукции, а минимальные транспортные расходы составят 479 000 (рис. 69).

80

Рис. 68. Поиск решения
Рис. 69. Оптимальное решение задачи
16. Покажите работу преподавателю.

81
Частным случаем транспортной задачи является задача о назначениях.
В общем виде она формулируется следующим образом: имеется n различных работ и n рабочих. Известны стоимости выполнения каждого вида работ каждым работником. Необходимо так составить штатное расписание, чтобы все работы были выполнены, на выполнение каждой работы назначался только один работник, а затраты на заработную плату были минимальными. В данном случае задача является сбалансированной, так как количество работников равно количеству работ. Ограничения записываются в виде следующих равенств.
x
11
+ x
12
+ …+ x
1n
=1,
x
21
+ x
22
+… +x
2n
=1,

x
n1
+ x
n2
+ … + x
nn
=1 – ограничения для работников (каждый работник может выполнять только один вид работ).
x
11
+ x
21
+ …+ x
n1
=1,
x
12
+ x
22
+… + x
n2
=1,

x
1n
+ x
2n
+ … + x
nn
=1 – ограничения для работ (каждый вид работ может быть выполнен только одним работником).
x
ij
– это двоичные переменные, которые могут принимать только два значения: 1, если работник i назначается на выполнение работы j и 0, если не назначается.
Решение задачи о назначениях рассмотрим на примере.
Пример 2. В лингвистическом центре работают 4 преподавателя по следующим направлениям: «Английский для начинающих», «Деловой английский», «Подготовка к ЕГЭ» и «Английский для путешествий».
Стоимость академического часа работы каждого преподавателя по каждому курсу представлена в табл. 8. Составьте оптимальное распределение нагрузки среди сотрудников таким образом, чтобы все курсы были проведены, каждый преподаватель был занят только на одном виде работ, а затраты на заработную плату были минимальными.

82
Таблица 8
Стоимость обучения
№ п/п
ФИО преподавателя
Название курса
Английский для начинающих
Деловой английский
Подготовка к ЕГЭ
Английский для путешествий
1
Королёв Д. А.
100 300 110 250 2
Воробьёва А. С.
120 180 100 150 3
Соловьёв Н. А.
200 200 80 170 4
Павлова Р. Г.
300 250 150 230 1. Построим математическую модель задачи: определим переменные, целевую функцию и ограничения.
Пусть:
x
11
, x
12
, x
13
, x
14
, x
21
, x
22
, x
23
, x
24
, x
31
, x
32
, x
33
, x
34
– двоичные переменные, которые могут принимать два значения: 1, если преподаватель i назначается на чтение курса j и 0, если не назначается.
z=100 x
11
+ 300 x
12
+ 110 x
13
+ 250 x
14
+ 120 x
21
+ 180 x
22
+100 x
23
+150 x
24
+
+200 x
31
+200 x
32
+ 80 x
33
+ 170 x
34
+300 x
41
+250 x
42
+ 150 x
43
+ 230 x
44
– целевая функция (общая стоимость работ).
x
11
+ x
12
+ x
13
+ х
14
=1,
x
21
+ x
22
+x
23
+ х
24
=1,
x
31
+ x
32
+x
33
+ х
34
=1,
x
41
+ x
42
+x
43
+ х
44
=1,
x
11
+ x
21
+ x
31
+ х
41
=1,
x
21
+ x
22
+x
23
+ х
24
=1,
x
13
+ x
23
+x
33
+ х
43
=1,
x
14
+ x
24
+x
34
+ х
44
=1 – ограничения (каждый преподаватель может быть задействован на чтении только одного курса и каждый курс должен быть проведен).
2. На основе математической модели на рабочем листе Excel создадим табличную модель (рис. 70).

83

Рис. 70. Задача о назначениях
3. Целевая функция в данном случае вычисляется по формуле
=СУММПРОИЗВ(C6:F9;C15:F18).
4. Выделите целевую ячейку и запустите надстройку Поиск решения
(Данные Анализ Поиск решения).
5. В появившемся диалоговом окне Поиск решения укажите адреса целевой ячейки, диапазон изменяемых ячеек и ограничения (рис. 71). Целевую ячейку установите равной минимальному значению. В диалоговом окне
Параметры поиска решения установите флажки Линейная модель
и Автоматическое масштабирование.
6. В диалоговом окне Поиск решения (рис. 71) нажмите кнопку Выполнить.


84

Рис. 71. Поиск решения
7. Получаем оптимальное решение задачи (рис. 72).

Рис. 72. Оптимальное решение задачи

85
Индивидуальные задания
1. Фирма производит две модели А и В сборных книжных полок.
Их производство ограничено наличием сырья (высококачественных досок) и временем машинной обработки. Для каждого изделия модели А требуется 3 м
2
досок, а для изделия модели В – 4 м
2
. Фирма может получать от своих поставщиков до 1700 м
2
досок в неделю. Для каждого изделия модели А требуется 12 минут машинного времени, а для изделия модели В – 30 минут. В неделю можно использовать 160 часов машинного времени. Каждое изделие модели А приносит 2 $ прибыли, а каждое изделие модели В – 4 $. Сколько изделий каждой модели следует выпускать фирме в неделю, чтобы получать максимальную прибыль?
2. Фирма выпускает два набора удобрений для газонов: обычный и улуч- шенный. В обычный набор входят 3 фунта азотных, 4 фунта фосфорных и
1 фунт калийных удобрений, а в улучшенный – 2 фунта азотных,
6 фунтов фосфорных и 2 фунта калийных удобрений. Известно, что для некоторого газона требуется, по меньшей мере, 10 фунтов азотных,
20 фунтов фосфорных и 7 фунтов калийных удобрений. Обычный набор стоит 3 $, а улучшенный – 4 $. Сколько и каких наборов удобрений надо купить, чтобы обеспечить эффективное питание почвы и минимизировать стоимость?
3. Издательский дом «Живое слово» выпускает два журнала: «Следопыт» и «Путешественник», которые печатаются в трех типографиях: «Алмаз-
Пресс», «Урал-Принт» и «Уникум-Пресс», где общее количество часов, отведенное для печати, и производительность печати одной тысячи экземпляров ограничены (представлены в табл. 9).



86
Таблица 9
Производительность
Типография
Время печати одной тысячи экземпляров
Ресурс времени, отведенный типографией, час
«Следопыт»
«Путешественник»
«Алмаз-Пресс»
2 14 112
«Урал-Принт»
4 6
70
«Уникум-Пресс»
6 4
80
Оптовая цена, руб./шт
16 12

Спрос на журнал «Следопыт» составляет 12 тысяч экземпляров, а на журнал «Путешественник» – не более 7,5 тысячи в месяц. Определите оптимальное количество издаваемых журналов, которое обеспечит максимальную выручку от продажи.
4. На кафедре работает 4 преподавателя-почасовика. Каждый из них может проводить определенные виды занятий. Почасовая оплата препода- вателям по каждому виду работ представлена в табл. 10.
Таблица 10
Почасовая оплата труда
Преподаватели
Почасовая оплата курсов
Системный анализ
Информатика
Интеллектуальные информационные системы
Web- программирование
Алексеев И. М.
350 420 610 200
Ковалёв Г. Н.
890 130 650 900
Семёнова О. В.
430 520 600 720
Петров Г. П.
830 610 780 470
Составить план проведения учебных занятий так, чтобы все виды занятий были проведены, каждый преподаватель проводил занятия только по одному виду, а суммарная стоимость почасовой оплаты была мини- мальной.
5. Необходимо составить диету, состоящую из двух продуктов: А и В.
Дневное питание этими продуктами должно давать не более 14 единиц жира, но и не менее 300 калорий. В одном килограмме продукта А

87 содержится 15 единиц жира и 150 калорий, а в одном килограмме продукта В – 4 единицы жира и 200 калорий. При этом цена одного килограмма продукта А равна 15 $, а цена одного килограмма продукта В –
25 $. Какое количество продуктов в день необходимо употреблять для соблюдения диеты, чтобы вложенные средства были минимальными?
6. Компания хранит готовую продукцию на трех складах (первом, втором и третьем), расположенных в разных частях города. На этих складах хранится продукция в количествах 1000, 3000 и 2100 штук соответственно. Продукцию необходимо доставить четырем оптовым покупателям П1, П2, П3, П4 с минимальными затратами, заявки которых составляют 1300, 800, 2700 и 1700 штук соответственно. Склады оптовых покупателей также расположены в разных частях города. Стоимости (в рублях) доставки одной штуки продукции со складов компании на склады покупателей показаны в следующей табл. 11.
Таблица 11
Стоимость доставки продукции
Склады компании
Оптовые покупатели
П1
П2
П3
П4
№ 1 50 150 60 75
№ 2 100 30 100 40
№ 3 70 180 210 120 7. Фабрика детских игрушек на одном сборочном участке собирает три вида игрушек: модели легкового автомобиля, гоночного автомобиля и грузовика. При сборке каждого вида игрушки используется три вида операций (ручная сборка, «отверточная сборка» и проверка сборки).
Ежедневный фонд рабочего времени на выполнение каждой операции ограничен величинами 490, 560 и 520 минут. Доход на одну игрушку каждого вида составляет соответственно 85, 100 и 125 руб. Время выполнения каждой операции в минутах, необходимое для сборки одной игрушки, показано в табл. 12.

88
Таблица 12
Время сборки моделей автомобилей
Операция
Модель легкового автомобиля
Модель гоночного автомобиля
Модель грузовика
Ручная сборка
2 3
3
«Отверточная» сборка
3 2
5
Проверка сборки
4 2
6
Количество производимых ежедневно моделей легковых автомобилей и грузовиков не должно быть меньше 20 и 15 штук соответственно.
Руководство фабрики решило добавить на этот сборочный участок производство новой игрушки, модели экскаватора, доходность которой прогнозируется на уровне 150 руб. Каждая модель экскаватора требует 3,
4 и 3 минут выполнения операций трех видов. Фонд рабочего времени участка остается неизменным. Определите, выгодно ли фабрике начинать производство новых игрушек.
8. Завод производит электронные приборы трех видов (прибор А, прибор В и прибор С), используя при сборке микросхемы трех типов (тип 1, тип 2 и тип 3). Расход микросхем задается табл. 13.
Таблица 13
Расход микросхем
Тип
Прибор А
Прибор В
Прибор С
1 2
1 1
2 1
1 4
3 2
2 1
Стоимость изготовленных приборов одинакова. Ежедневно на склад завода поступает 400 микросхем типа 1 и 500 микросхем типов 2 и 3.
Каково оптимальное соотношение дневного производства приборов различного вида, если производственные мощности завода позволяют использовать запас поступивших микросхем полностью. Решите эту же задачу, но с условием, что количество приборов каждого вида не должно быть меньше 90. Проанализируйте полученное решение.

89 9. Строительной фирме необходимо выполнить бетонные работы на четырех строящихся объектах. В фирме имеется 4 бригады бетонщиков, которые могут выполнить эту работу. Бригадиры каждой бригады побывали на объектах, оценили объемы работ и рассчитали сроки, за которые они могут выполнить работы. Сроки (в рабочих днях) выполнения работ каждой бригадой приведены в табл. 14.
Таблица 14
Сроки выполнения работ
Бригада
Объект
1 2
3 4
№ 1 30 40 50 60
№ 2 36 41 52 58
№ 3 28 44 49 57
№ 4 35 39 49 63
Распределите бригады по объектам таким образом, чтобы суммарный срок выполнения всех работ был минимальным.
10. Фирма производит два вида продукции: столы и стулья. Для изготовления одного стула требуется 3 кг древесины, а для изготовления одного стола – 7 кг. На изготовление одного стула уходит два часа рабочего времени, а на изготовление стола – 8 часов. Каждый стул приносит прибыль, равную 1 у. е., а каждый стол – 3 у. е. Сколько стульев и сколько столов должна изготовить эта фирма, если она располагает 420 кг древесины и 400 часами рабочего времени и хочет получить максимальную прибыль?
11. На ферме в качестве корма для животных используются два продукта – M и N. Сбалансированное питание предполагает, что каждое животное должно получать в день не менее 200 ккалорий, причем потребляемое при этом количество жира не должно превышать 14 единиц. Подсчитано, что в 1 кг каждого продукта содержится:
 в продукте M – 150 ккалорий и 14 единиц жира;
 в продукте N – 200 ккалорий и 4 единицы жира.

90
Разработать максимально дешевый рацион откорма животных, отвечающий этим условиям, если стоимость 1 кг продукта М составляет
1,5 руб, а 1 кг продукта N – 2,3 руб.
12. На мебельной фабрике изготавливается пять видов продукции: столы, шкафы, диван-кровати, кресла-кровати и тахты. Нормы затрат ресурсов – труда, древесины и ткани – на производство единицы продукции каждого вида приведены в табл. 15.
Таблица 15
Затраты ресурсов
Наименование ресурса
Расход ресурса на единицу продукции
(в указанных единицах измерения)
Запас ресурса стол шкаф диван- кровать кресло- кровать тахта
Трудозатраты (чел.-ч.)
4 8
12 9
10 3690
Древесина (м3)
0,4 0,6 0,3 0,2 0,3 432
Ткань (м)
0 0
6 4
5 2400
Прибыль от выпуска 1 изделия (у. е.)
8 10 16 13 17

Предельный объем выпуска (шт.)
480 80 180 120 100

В этой же таблице указаны запасы ресурсов, которые могут быть использованы в течение рабочего дня, величины прибыли (в условных единицах) от выпуска одного изделия каждого вида, а также заданы пределы объемов изготовления каждого вида продукции.
Требуется определить объемы производства продукции мебельной фабрикой в течение рабочего дня, гарантирующие ей максимальную прибыль.
13. На фабрике по производству микросхем четыре техника (A, B, C и D) производят три продукта (продукты 1, 2 и 3). Производитель микросхем может продать в этом месяце 80 единиц продукта 1, 50 единиц продукта 2 и, самое большее, 50 единиц продукта 3. Техник A может производить только продукты 1 и 3. Техник B может производить только продукты 1 и 2. Техник C может производить только продукт 3. Техник D может

91 производить только продукт 2. Каждая произведенная единица продукта дает следующую прибыль: продукт 1: 6 руб.; продукт 2: 7 руб.; продукт 3:
10 руб. Время (в часах), требуемое каждому из техников для производства продукта, показано в табл. 16.
Таблица 16
Время производства продукта
Продукт
Техник A
Техник B
Техник C
Техник D
1 2
2,5
Не может
Не может
2
Не может
3
Не может
3,5 3
3
Не может
4
Не может
Каждый техник может работать до 120 часов в месяц. Как производитель микросхем может добиться максимальной ежемесячной прибыли?
14. Завод по производству компьютеров производит мыши, клавиатуры и джойстики для видеоигр. Прибыль на единицу продукта, трудозатраты на единицу продукта, ежемесячный спрос и машинное время на единицу продукта приведены в табл. 17.
Таблица 17
Затраты производства
Мышь
Клавиатура
Джойстик
Прибыль на единицу, руб.
8 11 9
Трудозатраты на единицу, час.
0,2 0,3 0,24
Машинное время на единицу, час.
0,04 0,055 0,04
Ежемесячный спрос, шт.
15 000 25 000 11 000

Каждый месяц суммарно доступно 13000 человеко-часов и 3000 часов машинного времени.
Как производитель может получить максимальную прибыль от своей фабрики?

92 15. В хозяйстве имеется пять складов минеральных удобрений и четыре пункта, куда их необходимо доставить. Потребность каждого пункта в минеральных удобрениях различна, и запасы на каждом складе ограничены. Требуется определить, с какого склада, в какой пункт поставлять, сколько минеральных удобрений для минимизации грузооборота перевозок.
Исходные данные представлены в таблицах 18–20.
Таблица 18
Наличие минеральных удобрений на складах
Склады
Наличие удобрений, т.
Склад № 1 200
Склад № 2 190
Склад № 3 220
Склад № 4 145
Склад № 5 280
Таблица 19
Потребность в минеральных удобрениях на различных пунктах
Пункты
Потребность в удобрениях, т.
1 пункт
200 2 пункт
150 3 пункт
220 4 пункт
330
Таблица 20
Расстояния между складами и пунктами доставки

Пункт 1
Пункт 2
Пункт 3
Пункт 4
Склад № 1 6
4 5
11
Склад № 2 12 6
4 9
Склад № 3 15 7
10 4
Склад № 4 9
5 12 5
Склад № 5 3
7 12 11


93


Поделитесь с Вашими друзьями:
1   2   3   4   5


База данных защищена авторским правом ©nethash.ru 2017
обратиться к администрации

войти | регистрация
    Главная страница


загрузить материал