Лабораторная работа: Расчет оптимизационных моделей

Лабораторная работа: Расчет оптимизационных моделей

Практическое занятие

“Расчет оптимизационных моделей”

Оптимизационные модели

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

Оптимизационная модель формируется в общем виде следующим образом: "Надо отыскать значения управляемых параметров (показателей) x1,x2,…..xn, характеризующих управляемый экономический объект или процесс, придающие максимальное или минимальное значение целевой функции F(x1,x2,…..xn,)при соблюдении ограничений, накладываемых на область изменения показателей x1,x2,…..xn,, и связей между ними в виде f(x1,x2,…..xn,)£a". Если целевая функция, ограничения, связи между искомыми показателями выражены в виде линейных зависимостей, то оптимизационная модель сводится к задаче линейного математического программирования и саму модель также называют линейной.

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

Задача 1. Простейшая задача на максимизацию прибыли компании

Компания производит два продукта в количестве x1 и x2 тонн за месяц соответственно. Тонна первого продукта приносит 12 тысяч гривен прибыли, а тонна второго продукта - 8 тысяч гривен. Производственные мощности компании позволяют выпускать не более 100 тонн двух продуктов вместе, при этом производство первого продукта не может превышать более чем в три раза производство второго. Надо определить оптимальный объем производства, приносящий компании максимальную прибыль.

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

F(x1, x2,…..xn,)=F(x1, x2)=12x1 +8x2 тысяч гривен

Объемы выпуска x1 и x2 есть заведомо положительные величины, то есть

x1 ³0; x2 ³0

Между значениями x1 и x2 имеются связи

x1 + x2 £100

x1 £ 3 x2

Таким образом, подходим к типичной задаче линейного математического программирования, когда надо отыскать значения управляющих параметров x1, x2, придающие максимальное значение целевой функции 12x1 +8x2 с учетом фиксированных связей и ограничений.

Постановку и решение этой задачи удобно проиллюстрировать графически, отобразив связи и ограничения в системе координат параметров x1, x2, как изображено на рис. 3.1.

0 20 40 60 75 80 100 120

Рисунок.3.1. - Графическая интерпретация задачи

В силу положительных значений параметров x1 и x2 (x1³0;x2³0) решение следует искать в первом квадранте. Ограничение по суммарному выпуску (x1 + x2 £100) сужает область поиска до находящейся внутри треугольника ОАС, ограниченного сверху прямой x1 + x2 =100. Ограничение x1 £ 3 x2 еще более сужает область допустимых по условию задачи значений x1 и x2, заключая ее в треугольник ОАВ, ограниченный снизу прямой x1 £ 3 x2. Среди всех значений x1 и x2, заключенных внутри ОАВ, оптимальным соответствует точка В. В этой точке, соответствующей координатам x1 = 75; x2 = 25, достигается наибольшее из допустимых значений x1 равное 75. К наибольшему же значению x1 и надо стремиться, так как первый вид продукции приносит в расчете на одну тонну больше прибыли, чем второй (12 > 8), то есть надо выбирать наибольшее из возможных, допустимых значений x1. Оптимальному решению соответствует, таким образом, точка В, в которой целевая функция достигает своего максимального значения

12x1 +8x2 =12×75+8× 25=1100 тысяч гривен

Легко проверить, что внутри треугольника ОАВ любое другое сочетание, кроме x1 = 75; x2 = 25, обеспечивает меньшую суммарную прибыль.

Задача 2. Постановка и решение транспортной задачи

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

Пусть имеется n поставщиков товара и m его потребителей. Каждый "i" поставщик способен поставлять потребителям за определенное время количество товара, равное Ni, а каждый "j" потребитель нуждается в количестве товара, равном Mj. Обозначим через xij количество товара, поставляемое "i" поставщиком "j" потребителю. Тогда общий объем поставок Q равный объему спроса всех потребителей, выразится соотношением:

, где

Nj =- есть сумма поставок всем m потребителям со стороны "i" поставщика.

Mj = - есть сумма потребностей "j" потребителя, удостоверяемых поставщиками всех n поставщиков.

Примем далее, что стоимость перевозки товара "i" поставщиком "j" потребителю равна cij. Тогда общая стоимость перевозок, зависящих от прикрепления "i" поставщика к "j" потребителю, то есть от значений xij равна

F (xij) = cij xij, i=1,2…..n, j=1,2,….m

Оптимизационная задача заключается в том, чтобы найти значения xij, то есть величины поставок (перевозок) товара от каждого поставщика к каждому потребителю, при которых общая стоимость перевозок F(x11, x12,….xij,.….xnm) будет минимальной. Решение задачи должно удовлетворять следующим ограничениям:

все значения xij неотрицательны, то есть xij³0

возможность перевозок и запросы потребителя удовлетворяются полностью

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

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

Таблица 2.

Потребители	Потребность в товаре, тонн	Поставщики	Возможность перевозки, тонн	Стоимость доставки единицы товара потребителю, грн за тонну
				Потребитель I	Потребитель II	Потребитель III
1	50	1	100	c11 = 10	c12 = 9	c13 = 11
2	70	2	60	c21 = 8	c22 = 10	c23 = 9
3	40

Задача заключается в том, чтобы найти значение объемов поставок X11, X12, X13 первого поставщика первому, второму и третьему потребителям и объемы поставок X21, X22, X23 второго поставщика соответственно первому, второму и третьему потребителям при которых суммарные затраты

F (X11, X12, X13, X21, X22, X23) = c11x11 + c12x12 + c13x13 + c21x21 + c22x22 + c23x23 = 10x11 + 9x12 +11x13 + 8x21 + 10x22 + 9x23 ® min

Одновременно должны соблюдаться условия:

x11 + x12 + x13 = 100

x21 + x22 + x23 = 60

x13 + x23 = 40

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

Т. к. самой дешевой является стоимость доставки ед. товара вторым поставщиком первому потребителю, то используем эту возможность полностью и примем x21 =50 т. и тем самым полностью удовлетворим его потребность. Оставшуюся возможность доставки 60-50=10т. товара со стороны второго поставщика представим третьему потребителю, т. е. x23 = 10, т. к. расход на доставку ему единицы товара (с23 = 9) < (с22 = 10), чем второму потребителю меньше чем доставка первым поставщиком (с13 = 11). Следовательно, x23 = 10.

Возможности второго поставщика на этом исчерпаны и оставшиеся потребности должны быть удовлетворены первым поставщиком. Он поставит второму потребителю x12 = 70т. и третьему потребителю x13 = 30т., т. к. 10 т. этот потребитель уже получил от второго поставщика. Поставки товара первым поставщиком первому потребителю, также как и поставки 2 поставщика 2 потребителю окажутся ненужными поэтому x11 = 0 и x22 = 0. В итоге искомое решение задачи имеет вид:

x11 = 0; x12 =70; x13 = 30

x21 =50; x22 =0; x23 = 10

Суммарный расход на поставку товара равны:

0×10 + 70×9 + 30×11 + 50×8 + 0×10 + 10×9 = 1450 грн. и являются минимально возможными. Средняя стоимость перевозки одной тонны товара составит

 грн. за тонну, при отсутствии оптимизации средняя цена равна

 грн./тонну

Задача. Фирма производит два вида изделий в количестве x1 и x2. Единица первого изделия приносит П1 – гривен прибыли, а второго П2 гривен прибыли. Производственные мощности позволяют выпускать не более N единиц двух наименований изделий вместе, при этом производство первого изделия не может превышать более чем в 4 раза производство второго изделия. Определить объем производства приносящей фирме максимальную прибыль. Построить график оптимизации прибыли. Варианты заданий приведены в таблице 1.

Таблица 1

№ вар.	П1 т. грн.	П2 т. грн.	N
1	24	16	200
2	28	20	250
3	36	24	300
4	48	28	400
5	54	32	450
6	66	36	500
7	72	40	550
8	78	48	600
9	84	52	650
10	90	56	700

Таблица 3.

Варианты заданий к решению транспортной задачи

№ вар.	Потребители	Потребность в товаре, т.тонн	Поставщики	Возможность перевозки, т.тонн	Стоимость доставки ед. товара потребителю, грн. за тонну
					Потребитель I	Потребитель II	Потребитель III
1	1 2 3	80 120 60	1 2	160 100	c11 =15 c21 =11	c12 =13 c22 =12	c13 =14 c23 =10
			1 2	180 120	c11 =17 c21 =13	c12 =15 c22 =14	c13 =13 c23 =11
2	1 2 3	100 130 70
			1 2	220 140	c11 =16 c21 =14	c12 =16 c22 =14	c13 =15 c23 =13
3	1 2 3	120 150 90
4	1 2 3	130 160 100	1 2	150 240	c11 =11 c21 =9	c12 =10 c22 =13	c13 =14 c23 =16
			1 2	210 240	c11 =19 c21 =14	c12 =21 c22 =16	c13 =17 c23 =15
5	1 2 3	150 180 120

Страницы: 1, 2