Курсовая работа по дисциплине «Прикладная математика» (стр. 2 )

x2 = 14

 

Оптимальный план в точке Q(28;14) I

Zmax=26x28+35x14=1,5 58 x1

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

Для того, чтобы убедиться в правильности полученного решения, следует проверить отношение Н = Q-1 * В:

2. Двойственная задача

Некое предприятие, использующее те же ресурсы что и предприятие из предыдущей задачи, желает приобрести все эти ресурсы. Оно желает приобрести их по ценам y1, y2 и y3 соответственно за единицу каждого из трёх ресурсов. Из условий предыдущей задачи нам известны затраты всех 3-х ресурсов для производства для каждого из 4-х видов продукции, количество ресурсов на производстве и прибыль от единицы каждой продукции:

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

Для производства продукции 1-ого вида требуется 2 единиц 1-ого ресурса, 3 единицы 2-ого ресурса и 2 единицы 3-его ресурса, что соответствует элементам 1-ого столбца матрица А. Прибыль от продажи продукции 1-ого вида равна 26. Следовательно, для целесообразности продажи ресурсов прибыль от продажи 2 единиц 1-ого ресурса, 3-х единиц 2-ого ресурса и 2-х единиц 3-его ресурса должна быть больше, либо равна 26, т. е. прибыли от продажи продукции 1-ого вида:

Соответственные условия должны выполняться и для продукции других видов. Им соответствуют 2-ой, 3-ий и 4-ый столбцы матрицы А, а также 2-ой, 3-ий и 4-ый элементы матрицы-строки прибыли С:

Но при продаже требуется учитывать и интересы покупателя. Естественным желанием покупателя является снижение расходов. Так как предприятие желает закупить весь объём имеющихся ресурсов, то его затраты при ценах y1, y2 и y3 составят , где коэффициенты при y1, y2 и y3 - количество имеющихся ресурсов. Таким образом:

Кроме того, так как цены не могут быть отрицательными, то .

Решение полученной задачи легко найти с помощью второй основной теоремы двойственности, согласно которой для оптимальных решений х(х1,х2,х3) и у(у1,у2,у3) пары двойственных задач необходимо и достаточно выполнение условий:

и

Ранее (см. Задачу 1) было найдено, что в решении исходной задачи х1>0 и х2>0. Поэтому

Учитывая, что 3-ой ресурс был избыточным, то, согласно теореме двойственности, его двойственная оценка , получим систему:

откуда следует

у1 = 7,

у2 = 4.

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

у1 = 7, у2 = 4, у3 = 0,

причем общая оценка всех ресурсов равна

fmin = 1218

Заметим, что это решение содержалось в последней строке симплексной таблицы исходной задачи.

Данные значения y1, y2 и y3 являются двойственными оценками соответствующих ресурсов, т. е. оценка единицы 1-ого ресурса равна 7, оценка единицы 2-ого ресурса равна 4, а оценка 3-его ресурса равна 0. Эти оценки являются «теневыми» ценами ресурсов. Экономически они указывают, на сколько увеличится прибыль при выполнении оптимальной производственной программы, если количество соответствующего ресурса увеличить на единицу, при неизменном количестве остальных ресурсов.

Используя задачу 1, мы можем найти оценку технологии, т. е. насколько уменьшится прибыль, если будет произведена 1 единица продукции не по оптимальной программе. Оценки технологий получились в конечной симплексной таблице как коэффициенты при соответствующих x в целевой функции. Таким образом, при производстве единицы 3-й продукции прибыль упадёт на 17, а для 4-ей продукции падение составит 6.

3. Расшивка узких мест

Таблица №3

			26	35	18	30	0	0	0
С	Б	Н	x1	x2	x3	x4	x5	x6	x7
35	x2	14	0	1	-11/15	8/15	1/5	-2/15	0
26	x1	28	1	0	7/3	2/3	0	1/3	0
0	x7	5	0	0	1/15	-28/15	-1/5	-8/15	1
	P	1218	0	0	17	6	7	4	0

При выполнении оптимальной производственной программы первый и третий ресурсы используются полностью, т. е. образуют «узкие места производства». Будем их заказывать дополнительно. Пусть – вектор дополнительных объемов ресурсов. Так как мы будем использовать найденные двойственные оценки ресурсов, то должно выполняться условие , где Н – значения базисных переменных в последней симплексной таблице, а Q-1 – обращенный базис, который образуют столбцы при балансовых переменных в этой таблице. Задача состоит в том, чтобы найти вектор , максимизирующий суммарный рост прибыли

(1)

при условии сохранения двойственных оценок ресурсов (и, следовательно, ассортимента выпускаемой продукции)

(2)

предполагая, что можно надеяться получить дополнительно не более первоначального объема ресурса каждого вида (3)

причем по смыслу задачи , (4)

Переписав неравенства (2) и (3) в виде: (5)

; (6)

приходим к задаче ЛП: максимизировать (1) при условиях (5), (6) и (4).

Эту задачу легко решить графически: см. рис. Допустимое множество закрашено серым цветом. Программа «расшивки» имеет вид:

Ответ: максимальный прирост прибыли составит maxW=175.

4. Транспортная задача линейного программирования

Имеется 3 производителя однородной продукции, имеющие запасы этой продукции 60, 50 и 70 единицы соответственно. Также имеется 4 потребителя данной продукции. Их потребность составляет 56, 35, 48 и 30 единицы соответственно. Транспортная компания заключила контракт с поставщиками и потребителями на вывоз и поставку данной продукции от производителей к потребителям. При перевозке продукции от каждого производителя к каждому потребителю транспортная компания имеет определённые издержки на единицу продукции: 2 у. е. при перевозке от 1-ого производителя к 1-ому потребителю, 5 у. е. - от 1–ого производителя ко 2-ому потребителю, 1 у. е. – от 1-ого к 3-ему, 4 у. е. – от 1-ого к 4-ому, 4 у. е. – от 2-ого к 1-ому, 4 у. е. – от 2-ого ко 2-ому, 3 у. е. – от 2-ого к 3-ему, 2 у. е. – от 2-ого к 4-ому, 6 у. е. – от 3-его к 1-ому, 5 у. е. – от 3-его ко 2-ому, 4 у. е. – от 3-его к 3-ему, 3 у. е. – от 3-его к 4-ому. Так как естественным стремлением транспортной компании является максимизация прибыли, то требуется составить такой план перевозок, чтобы издержки были минимальными.

Можно записать эти издержки на единицу продукции в виде матрицы, где строка издержки при поставке от одного производителя к каждому потребителю, а столбец издержки при поставке к одному потребителю от каждого производителя:

Предложение производителей и спрос потребителей можно записать в виде векторов А и B соответственно:

и

Требуется найти план перевозок

X = (xij), i = 1,m; j = 1,n,

минимизирующий общую стоимость всех перевозок

L = ∑∑cijxij

При условии, что из любого пункта производства вывозится весь продукт

∑xij = ai, i = 1,m

И любому потребителю доставляется необходимое количество груза

∑xij = bj, j = 1,n

Причём по смыслу задачи

x11 > 0,…, xmn > 0

В нашей задаче 4 потребителя и 3 поставщика, причём суммарный объем производства Sai = 60 + 50 + 70 = 180 больше, чем требуется всем потребителям Sbi = 56 + 35 + 48 + 30 = 169. Суммарное предложение не больше суммарного спроса. Для того, чтобы они были равны введём фиктивного потребителя с потреблением равным разнице между предложением и спросом.. Фактически эта потребность будет указывать на количество продукции, которая не будет вывозиться от производителя. Для того, чтобы введение фиктивного потребителя не повлияло на решение, затраты на перевозку единицы продукции к фиктивному потребителю приравняем к 0. В действительности это будет также, так как транспортная компания не будет нести издержки за товар, который она никуда не возит. Тогда вектор В и матрица С будут выглядеть так:

и

56 + 35 + 48 + 30 + 11 = 60 + 50 + 70

ПН ПО	56	35	48	30	11	αi
60	2	2	5	5	4	1	3	4	0	0	α1 = 0
56	4
0		0		3		-1		0
50	1	4	4	4	3	3	2	2	-1	0	α2 = -1
	31	19
-3		0		0		0		-1
70	2	6	5	5	4	4	3	3	0	0	α3 = 0
		29	30	11
-4		0		0		0		0
βj	β1 = 2	β2 = 5	β3 = 4	β4 = 3	β5 = 0

Zопор = 112 + 20 + 124 + 57 + 116 + 90 = 519