Лабораторная работа №4_Поиск решения. Лабораторная работа 4. Решение задач оптимизации

• Название: Лабораторная работа 4. Решение задач оптимизации
• Дата: 13.10.2021
• Размер: 409.97 Kb.
• Имя файла: Лабораторная работа №4_Поиск решения.docx
• Тип: Лабораторная работа; #246640

Лабораторная работа №4. Решение задач оптимизации

Задачи оптимизации занимают очень важное место в бизнесе, производстве, прогнозировании. Условно эти задачи можно разделить на следующие категории:

• 
  транспортная задача – минимизация расходов на транспортировку товаров;
  
• 
  задача о назначениях – составление штатного расписания с минимизацией денежных затрат на заработную плату или времени выполнения работ;
  
• 
  задачи оптимизации производства – максимизация выпуска товаров при ограничениях на сырье для производства этих товаров.
  

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

Задача оптимизации в общем виде формулируется следующим образом. Найти значения переменных x₁, x₂, … , x_n, такие, что целевая функция f(x₁,

x₂, … , x_n) примет максимальное, минимальное или заданное значения при ограничениях вида g(x₁, x₂, … , x_n).

Таким образом, задача оптимизации содержит три основных компонента:

• 
  переменные x₁, x₂, … , x_n – определяемые величины;
  
• 
  целевая функция – это цель, записанная математически в виде функции от переменных, принимающая максимальное, минимальное или заданное значения;
  
• 
  ограничения – условия или соотношения, которым должны удовлетворять переменные.
  

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

Пример 1.

Цех выпускает детали А и В. На производство детали А рабочий тратит 3 часа, на производство детали В - 2 часа. От реализации детали А предприятие получает прибыль 80 ден. ед., В - 60 ден. ед. Цех должен выпустить не менее 100 штук деталей А и не менее 200 штук деталей В. Сколько деталей каждого вида надо выпустить для получения наибольшей прибыли, если фонд рабочего времени составляет 900 человеко-часов.

Математическая модель задачи.

Обозначим за x₁ и x₂ количество изделий А и В в оптимальном плане производства.



Решение задачи в MS Excel.

Модели всех задач на оптимизацию состоят из следующих элементов:

1. Переменные - неизвестные величины, которые нужно найти при решении задачи.

2. Целевая функция - величина, которая зависит от переменных и является целью, ключевым показателем эффективности или оптимальности модели.

3. Ограничения - условия, которым должны удовлетворять переменные.

В качестве переменных х₁ и х₂ будем использовать ячейки E2 и E3 соответственно. Для значения целевой функции будем использовать ячейку E9:



Рис. 39

Далее выбираем пункт меню Данные/Поиск решения:



Рис. 40

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

В поиске решения указываем, что нам необходимо установить ячейку $E$9 максимальному значению, изменяя ячейки $E$2:$E$3. Далее нажимаем кнопку Добавить для добавления ограничений. И добавляем следующие ограничения:



Рис. 41 - Ограничения по фонду рабочего времени


Рис. 42 - Ограничения по минимальному плану производства


Рис. 43 - Количество изделий должно быть целым числом
После ввода каждого ограничения нажимаем кнопку Добавить. После ввода последнего ограничения нажимаем кнопку OK. И диалоговое окно Поиск решения принимает следующий вид:



Рис. 44

Нажимаем кнопку Выполнить. И перед нами открывается диалоговое окно Результаты поиска решения:



Рис. 45
Выбираем создание отчёта по результатам. Отчеты по устойчивости и пределам не создаются при использовании целочисленных ограничений на переменные. После нажатия кнопки OK в рабочей книге появляется новый лист с названием Отчет по результатам 1 содержащий отчёт по результатам, и получаем следующие результаты:

Деталь	Затраты времени на производсво одной детали, ч.	Прибыль от реализации одной детали, ден. ед.		Минимальный план выпуска, штук		Оптимальный план производства, штук
А	3	80		100		100
В	2	60		200		300
Фонд рабочего времени, человеко-часов
составляет			900
задействовано			900
Максимальная прибыль от реализации, ден. ед.								26000

Отчёт по результатам.

Целевая ячейка (Максимум)
	Ячейка__Имя__Исходное_значение'>Ячейка	Имя	Исходное значение	Результат
	$E$9	Максимальная прибыль от реализации, ден. ед. Оптимальный план производства, штук	0	26000
Изменяемые ячейки
	Ячейка	Имя	Исходное значение	Результат
	$E$2	А Оптимальный план производства, штук	0	100
	$E$3	В Оптимальный план производства, штук	0	300
Ограничения
	Ячейка	Имя	Значение	Формула	Статус	Разница
	$C$7	задействовано Прибыль от реализации одной детали, ден. ед.	900	$C$7<=$C$6	связанное	0
	$D$2	А Минимальный план выпуска, штук	100	$D$2<=$E$2	связанное	0
	$D$3	В Минимальный план выпуска, штук	200	$D$3<=$E$3	не связан.	100
	$E$2	А Оптимальный план производства, штук	100	$E$2=целое	связанное	0
	$E$3	В Оптимальный план производства, штук	300	$E$3=целое	связанное	0

Анализ отчета показывает, что фонд рабочего времени задействован на 100%.

Рис. 46 - Электронная таблица в режиме формул.


Рис. 47 Электронная таблица в режиме значений.
Пример 2. Компания «Атлант» хранит свою продукцию на трех складах (первом, втором и третьем), расположенных в разных частях города. На этих складах хранится продукция в количествах 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₁₁, x₁₂, x₁₃, x₁₄, x₂₁, x₂₂, x₂₃, x₂₄, x₃₁, x₃₂, x₃₃, x₃₄– количество продукции, перевозимой со складов компании на соответствующие склады покупателей;

− z=50x₁₁+150x₁₂+60x₁₃+75x₁₄+100x₂₁+30x₂₂+100x₂₃+40x₂₄+

+70x₃₁+180 x₃₂ + 210 x₃₃ + 120 x₃₄– целевая функция, общая стоимость доставки грузов покупателям;

− x₁₁ + x₁₂ + x₁₃ +x₁₄=1000, x₂₁ + x₂₂ +x₂₃+x₂₄=3000,

x₃₁+x₃₂ + x₃₃ + x₃₄=2500 – ограничения для складов компании;

− x₁₁+ x₂₁ + x₃₁=1300, x₁₂ + x₂₂ + x₃₂=800, x₁₃ + x₂₃ +x₃₃=2700,

x₁₄+ x₂₄+ x₃₄=1700 – ограничения для складов покупателей.

2. 
   Имеем сбалансированную транспортную задачу, так как спрос покупателей (1300+800+2700+1700=6500) равен предложению производителей (1000+3000+2500=6500).
   
3. 
   Запустите табличный процессор MS Excel. Переименуйте Лист1в
   

Сбалансированная модель.

4. 
   Составьте табличную модель Excel (рис. 48).
   

Рис. 48. Сбалансированная модель

5. 
   Обратите внимание, что в ячейках F13:F15 и B17:E17 находятся формулы! А в ячейках G13:G15 и B18:E18 числа, без знака «=»
   
6. 
   Последняя таблица не обязательна. Целевую функцию можно было вычислить по формуле:
   

=СУММПРОИЗВ(В4:Е6;В13:Е15).

7. 
   Выделите целевую ячейку и запустите надстройку Поискрешения(Данные
   

 Анализ  Поиск решения).

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




Рис. 49. Диалоговое окно «Поиск решения»

8. 
   В диалоговом окне параметры Поиска решения установите флажки Линейная модель, Неотрицательные значения и Автоматическое масштабирование.
   
9. 
   В диалоговом окне Поиск решения нажмите кнопку Выполнить. 10. Получаем оптимальное решение задачи (рис. 50).
   

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

11. 
    Скопируйте полученную табличную модель на Лист 2 рабочей книги и переименуйте его в Несбалансированнаязадача.
    
12. 
    Решим эту же задачу, немного изменив условие.
    

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

Рис. 51. Поиск решения




Рис. 52. Оптимальное решение задачи
Пример 3. Частным случаем транспортной задачи является задача о назначениях. В общем виде она формулируется следующим образом: имеется n различных работ и n рабочих. Известны стоимости выполнения каждого вида работ каждым работником. Необходимо так составить штатное расписание, чтобы все работы были выполнены, на выполнение каждой работы назначался только один работник, а затраты на заработную плату были минимальными. В данном случае задача является сбалансированной, так как количество работников равно количеству работ. Ограничения записываются в виде следующих равенств.

x₁₁ + x₁₂ + …+ x_1n=1, x₂₁ + x₂₂ +… +x_2n=1,

…

x_n1+x_n2 + … + x_nn=1 – ограничения для работников (каждый работник может выполнять только один вид работ).

x₁₁ + x₂₁ + …+ x_n1=1, x₁₂ + x₂₂ +… +x_n2=1,

…

x_1n+x_2n + … + x_nn=1 – ограничения для работ (каждый вид работ может быть выполнен только одним работником).

x_ij– это двоичные переменные, которые могут принимать только два значения: 1, если работник i назначается на выполнение работы j и 0, если не назначается.

Решение задачи о назначениях рассмотрим на примере.

Пример 2. В лингвистическом центре работают 4 преподавателя по следующим направлениям: «Английский для начинающих», «Деловой английский», «Подготовка к ЕГЭ» и «Английский для путешествий». Стоимость академического часа работы каждого преподавателя по каждому курсу представлена в таблице 8. Составьте оптимальное распределение нагрузки среди сотрудников таким образом, чтобы все курсы были проведены, каждый преподаватель был занят только на одном виде работ, а затраты на заработную плату были минимальными.

Таблица 8 Стоимость обучения

№ п/п	ФИО преподавателя	Название курса
		Английский для начинающих	Деловой английский	Подготовка к ЕГЭ	Английский для путешествий
1	Королев Д. А.	100	300	110	250
2	Воробьева А. С.	120	180	100	150
3	Соловьев Н. А.	200	200	80	170
4	Павлова Р. Г.	300	250	150	230

1. 
   Построим математическую модель задачи: определим переменные, целевую функцию и ограничения.
   

Пусть:

x₁₁, x₁₂, x₁₃, x₁₄, x₂₁, x₂₂, x₂₃, x₂₄, x₃₁, x₃₂, x₃₃, x₃₄– двоичные переменные, которые могут принимать два значения: 1, если преподаватель i назначается на чтение курса j и 0, если не назначается.

z=100 x₁₁ + 300 x₁₂ + 110 x₁₃ + 250 x₁₄ + 120 x₂₁ + 180 x₂₂ +100 x₂₃ +150x₂₄+

+200x₃₁+200x₃₂+80x₃₃+170x₃₄+300x₄₁+250x₄₂+150x₄₃+230x₄₄– целевая

функция (общая стоимость работ).

x₁₁ + x₁₂ + x₁₃ + х₁₄=1, x₂₁ + x₂₂ +x₂₃+ х₂₄=1, x₃₁ + x₃₂ +x₃₃+ х₃₄=1, x₄₁ + x₄₂ +x₄₃+ х₄₄=1, x₁₁ + x₂₁ + x₃₁ + х₄₁=1, x₂₁ + x₂₂ +x₂₃+ х₂₄=1, x₁₃ + x₂₃ +x₃₃+ х₄₃=1,

x₁₄ + x₂₄ +x₃₄+ х₄₄=1 – ограничения (каждый преподаватель может быть задействован на чтении только одного курса и каждый курс должен быть проведен).

2. 
   На основе математической модели на рабочем листе Excel создадим табличную модель (рис. 53).
   

Рис. 53. Задача о назначениях

3. 
   Целевая функция в данном случае вычисляется по формуле
   

=СУММПРОИЗВ(C6:F9;C15:F18).

4. 
   Выделите целевую ячейку и запустите надстройку Поискрешения(Данные
   

 Анализ  Поиск решения).

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

Рис. 54. Поиск решения

7. 
   Получаем оптимальное решение задачи (рис. 55).
   

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

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

Нормы расхода сырья на производство 10 кг конфет каждого вида приведены ниже.

Сырье	Нормы расхода сырья			Запас сырья
	А	В	С
Какао	18	15	12	360
Сахар	6	4	8	192
Наполнитель	5	3	3	180
Прибыль	9	10	16

2. Для изготовления сплава из меди (Cu), олова (Sn) и цинка (Zn) в качестве сырья используют три сплава тех же металлов, отличающихся составом и стоимостью. Данные об этих сплавах приведены в таблице. Получаемый сплав должен содержать не более 4 кг меди, не менее 2,5 кг олова, а содержание цинка может составлять от 4 до 13 кг. Всего надо приготовить 13кг сплава. Определить количества Xj, (j = 1, 2, 3) сплавов каждого вида, обеспечивающие получение нового сплава с минимальными затратами на сырье.

3. Имеются три сплава. Первый сплав содержит 70% олова и 30% свинца, второй — 80% олова и 20% цинка, третий — 50% олова, 10% свинца и 40% цинка. Из них необходимо изготовить новый сплав, содержащий 15% свинца. Какое наибольшее и наименьшее процентное содержание олова может быть в этом сплаве?