ПРИ ОГРАНИЧЕННЫХ РЕСУРСАХ

Поиск оптимальных решений

При создании продукции

Методическое указание к выполнению практических работ

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

магистра 15.04.02 «Технологические машины и оборудование»

 

 

 

 

Брянск 2015

 

 

Федеральное государственное бюджетное образовательное

учреждение высшего профессионального образования

 

«Брянская государственная

инженерно-технологическая академия»

(ФГБОУ ВПО «БГИТА»)

 

Кафедра «Технический сервис»

 

 

Утверждены Научно-методическим советом БГИТА Протокол № ______________________ от "____" __________________ 2015 г.

 

 

Поиск оптимальных решений

При создании продукции

Методическое указание к выполнению практических работ

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

магистра 15.04.02 «Технологические машины и оборудование»

 

Брянск 2015

 

УДК. 519.6 (075.8)

 

 

Поиск оптимальных решений при создании продукции. Методическое указание к выполнению практических работ магистрами очной формы обучения направления подготовки магистров 15.04.02 «Технологические машины и оборудование» / Брянск. гос. технол. акад. Сост. П.В. Тихомиров, Г.А. Пилюшина, Е.В. Лемешева.- Брянск: БГИТА, 2015 – 56 с.

 

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

Библиограф. 4 назв.

 

 

Рецензент:

к.т.н., проф. кафедры «Детали машин», БГТУ, Стриженок А.Г.

 

Рекомендованы редакционно-издательской и методической комиссиями

механико-технологического факультета БГИТА

 

Протокол №____ от «____»_________2015 г.

Содержание

Введение………………………………………………………………………...
Практическая работа №1 Оптимизация плана выпуска продукции при ограниченных ресурсах ……………………………………………………
Практическая работа №2 Оптимизация раскроя древесностружечных плит ……………………………………………………………………………..
Практическая работа №3 Транспортная задача.……………………………….
Практическая работа №4 Закрепление продавцов за товарами ………………
Практическая работа №5 Распределение производственной программы …
Список использованных источников ………………………………………..
Приложение …………………………………………………………………….

 

Введение

 

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

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

· умение самостоятельно описывать реальные экономические задачи на языке математики, т.е. составлять математические модели;

· применять для их решения надлежащие программные средства;

· интерпретировать полученные результаты оптимизации;

· проводить исследование математической модели и результатов решения.

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

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

Отчет по каждому заданию должен быть выполнен в тетради для практических работ. Его содержание приведено в заключительной части каждого задания данного руководства. В нем должны быть даны все необходимые пояснения и формулы Excel, используемые в работе. Распечатки по задачам вклеиваются в тетрадь. Магистрант получает зачет по практической работе только после представления отчета и собеседования с преподавателем по теоретической части изучаемого раздела курса.

 

 

 

Практическая работа № 1 (4 часа)

ОПТИМИЗАЦИЯ ПЛАНА ВЫПУСКА ПРОДУКЦИИ

ПРИ ОГРАНИЧЕННЫХ РЕСУРСАХ

 

1.1 Цель работы: изучение методики оптимизации плана выпуска продукции при ограниченных ресурсах.

 

1.2 Теоретическая часть

 

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

 

(1.1)

 

достигает наибольшего (наименьшего) значения, и при этом выполняются условия

. (1.2)

 

Функция (1.1) носит название целевой функции или функции цели, неравенства (1.2) образуют систему ограничений. В этой системе могут быть также неравенства вида , или равенства.

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

Количество ограничений и число неизвестных характеризуют размерность задачи оптимизации.

Таким образом, в состав моделей оптимизации входят:

· целевая функция, выражающая в математической форме поставленную цель с точки зрения выбранного критерия оптимальности;

· система ограничений, то есть соотношения, которым должно удовлетворять решение данной задачи.

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

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

В зависимости от вида целевой функции и ограничительных условий в задачах оптимизации принято выделять следующие разделы:

· линейное программирование, в котором целевая функция, а также уравнения и неравенства системы ограничений линейны;

· квадратичное программирование, в котором целевая функция квадратична и выпукла, а допустимое множество определяется линейными равенствами и неравенствами;

· выпуклое программирование, в котором целевая функция и допустимое множество выпуклы;

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

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

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

· стохастическое программирование, в котором информация о задаче оптимизации носит элементы неопределенности, и некоторые ее параметры являются случайными величинами.

 

Основным и важнейшим методом линейной оптимизации является в настоящее время симплексный метод или метод последовательного улучшения базисного плана. Метод был разработан Дж.Данцигом в 1949 году. Но еще раньше, в 1939 году, советским ученым академиком Л.В.Канторовичем для решения задач линейного программирования был предложен так называемый метод разрешающих множителей, незначительно отличающийся от симплексного метода. Симплекс-метод дает возможность решать задачи линейного программирования как вручную, так и на вычислительных машинах. Через конечное число шагов (симплексных таблиц) или получается оптимальное решение или обнаруживается неразрешимость задачи линейного программирования.

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

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

· методы первого порядка, при которых используются значения целевой функции и ее первых частных производных;

· методы второго порядка, при которых используются значения целевой функции и ее первых и вторых частных производных;

 

К методам поиска относятся: метод покоординатного спуска Пауэлла, метод Хука-Дживса, метод Розенброка, метод деформируемого многогранника (симплексный метод Нелдера и Мида) и его модификация в виде комплексного метода Бокса для нелинейной оптимизации с ограничениями, методы случайного поиска.

К методам 1-го порядка относятся градиентные методы, метод сопряженных направлений, метод переменной метрики (Дэвидона-Флетчера-Пауэлла).

К методам 2-го порядка относится метод Ньютона.

Характерной особенностью вычислительной стороны методов решения задач оптимизации является то, что практическое использование этих методов требует огромной вычислительной работы, которую без ЭВМ реализовать крайне трудно, а в ряде случаев – невозможно. В первую очередь это связано с тем, что задачи оптимизации, формализующие реальные производственные ситуации, являются задачами большой размерности, недоступными для ручного счета.

Практическую реализацию методов оптимизации для учебных задач невысокой размерности удобно проводить средствами табличного процессора Microsoft Excel. Вычислительные возможности оптимизации объединены здесь с большим набором функций, присущих текстовому и графическому редакторам и другим приложениям пакета Microsoft Office. Excel позволяет выполнять линейную и нелинейную оптимизацию (для достаточно гладких функций и , входящих в задачу), осуществлять прогнозирование и поддержку принятия решений.

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

 

 

1.3 Пример выполнения работы

Данные о задаче содержатся в таблице 1.1

 

Таблица 1.1 – Пример данных к задаче

 

Оборудование	Затраты машинного времени на обработку единицы продукции, ч	Эффективный фонд времени станков, ч	Цена за простой единицы оборудования, ден.ед.
Шкаф	Стол
- строгальный станок
- фрезерный станок
- шлифовальный станок
Прибыль от реализации единицы продукции, ден.ед.

 

Пусть

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

– общая прибыль от реализации готовой продукции,

– суммарные издержки (штраф) предприятия за простой оборудования,

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

 

1.3.1. Математическая модель максимизации прибыли

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

 

. (1.3)

 

Неизвестные, очевидно, должны быть неотрицательными:

, . (1.4)

 

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

 

. (1.5)

 

Таким образом, математическая модель задачи по критерию максимальной прибыли состоит в определении чисел и , удовлетворяющих системе ограничений (1.3)-(1.4), для которых значение функции (1.5) будет максимальным. Это есть задача линейной оптимизации.

 

1.3.2. Математическая модель минимизации штрафа

 

Составим математическую модель для второго критерия. Из ограничений (1.1) следует, что время простоя станков равно:

– для строгальных станков,

– для фрезерных станков,

– для шлифовальных станков,

поэтому суммарные издержки предприятия за простой оборудования (цель 2) составляют:

 

, (1.6)

 

или

. (1.7)

 

Таким образом, математическая модель задачи по второму критерию состоит в минимизации целевой функции (1.7) при условиях, что неизвестные и удовлетворяют системе ограничений (1.3) и неравенствам (1.4). Это также есть задача линейной оптимизации.

 

1.3.3. Графическое решение задачи максимизации прибыли

На рисунке 1.1 приведено графическое решение задачи по критерию (1.5). На основе системы ограничений (1.3)–(1.4) строится допустимая область в виде многоугольника OABCD. Покажем, например, как построена прямая I. В уравнении положим , тогда получим . Затем положим , тогда . Через две точки проведем прямую I. Неравенство определяет полуплоскость, расположенную ниже этой прямой. Аналогично неравенство задает полуплоскость, расположенную под прямой II, а неравенство – полуплоскость, расположенную левее прямой III. Условия неотрицательности (1.4) в совокупности определяют первый квадрант координатной плоскости.

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

Рисунок 1.1. - Графическое решение задачи по первому критерию

 

Таким образом, выпуск продукции в количествах 36 и 21 ед. соответственно обеспечивает предприятию максимальную общую прибыль. Построение допустимой области можно выполнить в Excel. Для этого в соответствии с уравнениями системы (1.3) образуем таблица 1.2. В блок ячеек A3: A14 введем значения аргумента , изменяющегося от нуля до .

Таблица 1.2 - Загрузка оборудования по каждой группе

 

№	A	B	C	D
	Прямая I	Прямая II	Прямая III

Продолжение таблицы 1.2

 

№	A	B	C	D
		54,43
		45,14	38,9
		35,86	34,8
		26,57	30,7	52,5
		17,29	26,6
			22,5	–53
		–1,29	18,5	–105
		–10,6	14,4	–158
		–19,9	10,3	–210
		–29,1	6,18	–263
		–38,4	2,09	–315
		–47,7	–2	–368

 

В ячейки B3, C3 и D3 введем формулы из таблицы 1.3, которые копируются на блок ячеек B4: D14.

 

Таблица 1.3 – Ввод формул

 

B3	= (762 – 13 * A3) / 14
C3	= (946 – 9 * A3) / 22
D3	= (840 – 21 * A3) / 4

 

С помощью мастера диаграмм и блока ячеек B3: D14 из таблицы 1.2 строятся графики прямых линий I, II и III. Используя пункт меню «Ряд» и «Подписи оси x», указывают значения аргумента , содержащиеся в блоке ячеек A3: A14. После построения прямых следует выделить допустимую область, ограничив диаграмму снизу и сверху по вертикальной оси. Путем изменения размеров графика необходимо добиться, чтобы масштаб по осям координат был одинаковым. Подписи данных удобно сделать, используя пункт меню «Вид / Панели инструментов / Рисование».

 

1.3.4 Оптимизация общей прибыли в Excel

 

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

 

 

Таблица 1.4 – Организация данных для решения задачи

по первому критерию

 

	A	B	C	D	E	F	G
	Целевая функция 1 – прибыль от реализации готовой продукции
	Продукция	Шкаф	Стол
	Значение
					Ограничения
	Станки			Левая часть	Знак	Правая часть	Штраф
	Строгальные				<=
	Фрезерные				<=
	Шлифовальные				<=
				ЦФ1->max		ЦФ2
	Прибыль

 

Вначале ячейки B4: C4 – пустые, они предназначены для записи решения задачи. В ячейке D7 записана формула

 

= СУММПРОИЗВ(B7: C7; $B$4: $C$4).

 

Содержимое ячеек D8, D9, D11 получено копированием формулы из D7.

В ячейке G10 записана формула

 

= СУММПРОИЗВ(G7: G9; F7: F9 – D7: D9),

 

характеризующая суммарный штраф за простой оборудования, как это следует из формулы (1.6).

Далее идет обращение к процедуре «Поиск решения» в пункте меню «Сервис». Целевой ячейкой является D11. Оптимальный план выпуска продукции в количествах 36 и 21 ед. содержится в ячейках B4: C4, максимальная прибыль (ячейка D11) равна ден.ед. Штраф за простой оборудования составляет ден.ед.

 

1.3.5 Оптимизация штрафа в Excel

 

Решение задачи по второму критерию выполняется в Excel на другом листе аналогично (см. таблицу 1.5), но целевой ячейкой служит G10.

 

Таблица 1.5 – Организация данных для решения задачи

по второму критерию

 

	A	B	C	D	E	F	G
	Целевая функция 2 – штраф за простой станков
	Продукция	Шкаф	Стол
	Значение
					Ограничения
	Станки			Левая часть	Знак	Правая часть	Штраф
	Строгальные				<=
	Фрезерные				<=
	Шлифовальные				<=
				ЦФ1		ЦФ2->min
	Прибыль

 

Оптимальное решение по второму критерию (ячейки B4: C4) состоит в выпуске шкафов и столов в количествах 22 и 34 ед., минимальный штраф за простой оборудования (ячейка G10) составляет ден.ед., При этом прибыль (ячейка D11) равна ден.ед.

Полученные результаты оптимизации по двум критериям сведены в таблицу 1.6.

 

Таблица 1.6 - Результаты оптимизации по двум критериям

 

	Критерий оптимальности	Продукция	Значения целевых функций
	Вершина на рис.1	Шкаф	Стол	z, ден.ед.	w, ден.ед.
Прибыль от реализации продукции	C
Штраф за простой станков	B

 

На рисунке 1.1 оптимальному плану по прибыли соответствует вершина C(36;21), а оптимальному плану по штрафу – вершина B(22;34).

 

1.3.6 Математическая модель оптимизации прибыли с учетом штрафа

 

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

, (1.8)

 

при ограничениях (1.3)-(1.4).

Используя соотношения (1.3)-(1.4).

Используя соотношения (1.5) и (1.7), получим

 

.

Тогда модель задачи состоит в определении чисел и , удовлетворяющих системе ограничений (1.3)-(1.4), для которых целевая функция

 

, (1.9)

 

достигает максимума. Решение этой задачи выполним в Excel на третьем листе, как показано в табл. 1.7. Целевой ячейкой является G11, содержимое которой определяется формулой

= D11 – G10,

вытекающей из (1.8).

 

Таблица 1.7 - Математическая модель оптимизации прибыли

с учетом штрафа

 

	A	B	C	D	E	F	G
	Целевая функция 3 – прибыль - штраф
	Продукция	Шкаф	Стол
	Значение
					Ограничения
	Станки			Левая часть	Знак	Правая часть	Штраф
	Строгальные				<=
	Фрезерные				<=
	Шлифовальные				<=
				ЦФ1		ЦФ2
	Прибыль					ЦФ3->max

 

Поиск решения дает оптимальное решение по третьему критерию (ячейки B4: C4), которое состоит в выпуске шкафов и столов в количествах 22 и 34 ед. Максимальная прибыль с учетом штрафа за простой оборудования (ячейка G11) равна ден.ед.

Аналогично можно определить оптимальный план выпуска продукции с учетом штрафа, используя выражение (1.9).

 

1.4 Техническое обеспечение

 

1.4.1 Компьютеры и выход в сеть интернета.

 

1.5 Содержание отчета

1.5.1 Задание для проведение расчетов приведено в приложении 1.

1.5.2 Отчет должен содержать следующие пункты:

· задание на работу с конкретными исходными данными студента,

· математическую модель максимизации прибыли,

· математическую модель минимизации штрафа,

· графическое решение задачи максимизации прибыли,

· оптимизацию общей прибыли в Excel в табличном виде,

· оптимизацию штрафа в Excel в табличном виде,

· математическую модель и оптимизацию прибыли с учетом штрафа,

· выводы по работе.