Динамическое программирование

Эквивалентная замена дробно-линейной модели на линейную модель.

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

 

 

 

Экономико-математическая модель с набором ограничений и с критерием выбора производственной программы представляет собой задачу     дробно-линейного программирования. Для того, что бы свести такую задачу необходимо ввести следующие замены переменных:

 

 

 

 

Умножим все ограничения на t0 > 0,что сохраняет направленность всех неравенств и делает замену переменных, при этом получаем дополнительные ограничения.

 

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

 

 

Выразим из дополнительных ограничений

 

 

 

 

Подставим t0 в целевую функцию и ограничения и получим.

 

 

Запишем задачу линейного программирования в стандартной форме.

 

 

Решим систему графическим методом.

1)

	0	3,86
	6,65	0

 

2)

	0	2,94
	5,24	0

 

3)

	0	2,38
	4,32	0

 

4)

	0	2,94
	4,32	0

 

5)

	0	2,38
	3,2	0

 

6)

	0	2,79
	6,49	0

 

В результате решения графическим методом  получим

 

 

Сделаем обратную замену переменных, для чего найдем значение переменной t0.

 

 

 

Максимизация по дробно-линейному уравнению показывает, что максимальное отношение дохода на один рубль затрат Zmax=0,0532 возможен при программе х*=(147; 0).   Понятно, что компанию не удовлетворяет такой ожидаемый результат ее производственной деятельности.

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

 

Показатели недельной производственной программы компании	При максимуме объема продаж	При минимуме совокупности затрат	При максимуме чистого дохода на руб. затрат
Объем выпуска продукта А	200	100	147
Объем выпуска продукта В	0	0	0
Уровень объема продаж (руб.)	71648	35824	52661
Уровень совокупных затрат (руб.)	67820	42000	54135
Уровень чистого дохода на один руб. затрат	0,056	-0,147	-0,027

 

 

 

 

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

Из листа стекла размером 4×8 метра требуется нарезать заготовки размерами 2×2 метра и 5×0,5 метра в количестве 100 и 200 штук соответственно.

Для решения задачи рассмотрим 4 схемы раскроя.

1.                                                        2.

   

 

 

 

3.                                                        4.                              
   

 

 

 

 

Согласно первой схеме раскроя получаем 6 листов первого типа, 3 листа второго типа и отходов 0,5 м2.

При второй схеме раскроя получаем 8 листов первого типа, 0 листов второго типа и отходов 0 м2.

При третьей схеме раскроя получаем 0 листов первого типа, 12 листов второго типа и отходов 2 м2.

При четвертой схеме раскроя получаем 2 листа первого типа, 9 листов второго типа и отходов 1,5 м2.

Для формализации задачи обозначим:

Хi – число листов стекла раскроенных по i методу;

ai и bi - число заготовок первого и второго типа раскроенных по i способу;

А – необходимое количество заготовок первого типа;

В – необходимое количество заготовок второго типа.

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

 

Матрица раскроя

Типы заготовок	Способы раскроя и число заготовок
	1 схема	2 схема	3 схема	4 схема
1 тип	6	8	0	2
2тип	3	0	12	9

 

Целевая функция может быть определена по-разному.  Например, требуется найти такое решение, которое бы давало минимальное число используемых листов или минимальное количество отходов. Эти две постановки не эквивалентны, так как требования минимальности отходов дает большее количество и соответственно требует расхода большего количества используемого материала.

Допустим, требуется использовать минимальное количество листов, тогда целевая функция будет иметь вид:

 

                                       

 

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

                                      

 

Приведем исходную задачу к канонической форме.

 

 

 

 

			-1	-1	-1	-1	0	0
Б	Св	Х¯	А1	А2	А3	А4	А5	А6
Х5	0	-100	-6	-8	0	-2	1	0
Х6	0	-200	-3	0	-12	-9	0	1
Δ			1	1	1	1	0	0
Х5	0	-100	-6	-8	0	-2	1	0
Х3	-1	50/3	1/4	0	1	3/4	0	-1/12
Δ			3/4	1	0	1/4	0	1/12
Х2	-1	12,5	3/4	1	0	1/4	-1/8	0
Х3	-1	50/3	1/4	0	1	3/4	0	-1/12
Δ		-175/6	0	0	0	0	1/8	1/12

 

Таким образом оптимальное решение имеет вид:

Х = (0; 12,5; 50/3; 0).

Это означает, что по первой схеме раскроя должно быть разрезано 12,5          листов, а по третьей схеме листа.

Такой раскрой даст заготовок первого типа,                              – второго типа.

Сверхплановых заготовок нет, так как Х5=0, Х6=0.

Отходы составляют: м2.

 

 

 

 

 

 

 

 

 

 

 

2.4. Анализ управленческих решений методами нелинейного программирования

Производственная фирма может выпускать изделий двух видов: А и Б. Статистическое исследование показало, что из-за брака в процессе производства, средний расход сырья и средняя себестоимость в расчете на 1000 изделий А и Б не остаются постоянными, а зависят от достигнутого уровня производства. Регрессионным анализом установлено, что средний расход сырья и средняя себестоимость в расчете на 1000 выпускаемых изделий А линейно зависит от достигнутого объема производства x1 изделий А по формулам:

 

 

где  а1 – 49 тонн, расход сырья, на 1-ю тыс. шт. изделий А;

S1 – 151 тыс.руб., себестоимость 1-ой тыс. шт. изделий А.

Аналогично средний расход сырья и среднюю себестоимость в расчете на тысячу изделий выпущенного объема x2 изделий Б нужно считать по формулам:

 

 

 

где  а2 – 145 тонн, расход сырья, на 1-ю тыс. шт. изделий Б;

S2 – 21 тыс.руб., себестоимость 1-ой тыс. шт. изделий Б.

Пусть сбыт изделий фирмы гарантированно ценам с1=174 тыс. руб., с2=92 тыс. руб. на каждую тысячу штук изделий А и Б соответственно.

Фирма располагает сырьем b=7200 тонн, продукция может выпускаться в любых пропорциях, но изделий А должно быть изготовлено не менее 1 тысячи штук. В каком количестве следует производить названное изделие в этих условиях, чтобы прибыль фирмы достигла максимума?

Составим экономико-математическую модель расчета производственной программы, максимизирующую прибыль предприятия в условиях непропорционального роста затрат ресурса и себестоимости выпускаемых продуктов. Формула расхода сырья на изготовление планируемых выпускаемых объемов x1 и х2 тысяч единиц изделий А и Б имеет вид:

 

 

В результате реализации х1 единиц изделий А предприятие получит среднюю прибыль:

 

В результате реализации х2 единиц изделий Б предприятие получит среднюю прибыль:

 

Тогда суммарную прибыль предприятия можно получить по формуле:

 

Получим задачу нелинейного программирования.

Графический анализ задачи нелинейного программирования:

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

+

 

 

 

 

 

 

 

 

 

 

 

 

 

Продифференцируем по х1:

 

 

 

2.   
   

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Таким образом, оптимальной производственной программой будет выпуск изделий А в количестве 12 тыс. шт., а Б – 36 тыс. шт. При этом будет достигнут максимум прибыли в размере 1440 тыс. руб.

Расчет оптимального управляющего решения методом множителей Лагранжа

Функция Лагранжа:

 

 

 

Составим функцию Лагранжа:

)

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

.

 

Ответ:

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Заключение

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

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

- в экономике - для решения больших макроэкономических моделей (типа модели Леонтьева и др.), микроэкономических моделей или моделей предпринимательства, для оптимизации технико-экономических систем (планирование, эконометрика), транспортные задачи, в теории принятия решений, теории игр и т.п.;

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