Задачи по "Экономико-математическому моделированию"

Задание 1

 

Предприятие  выпускает  продукцию трех видов: П1, П2 и П3.  Норма  расхода  материала  М1, М2 и М3 в  расчете  на  одно  изделие,  плановая  себестоимость,  оптовая  цена  предприятия,  плановый  ассортимент  и трудоемкость  единицы  продукции  приведены  в  табл. 4.  При  этом  запас  материала М1, М2 и М3  - 180, 1500  и  124  ед. изм.  соответственно.  Плановый  фонд  рабочего  времени  26100  человеко-часов.

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

 

Показатели	Изделия
	П1	П2	П3
Норма расхода материала  М1, ед изм	0,052	0,034	0,138
Норма расхода материала М2, ед изм	0,120	0,120	0,018
Норма расхода материала  М3, ед изм	0,007	0,007	0,008
Трудоемкость,  чел-ч	12,3	8,4	6,2
Плановая  себестоимость,  ден ед	98,81	71,67	31,55
Оптовая  цена  предприятия,  ден ед	102,00	78,00	34,00
Плановый  ассортимент,  шт	380	310	1250

 

Плановая прибыль, ден.ед.

3,19

6,33

2,45

 

Обозначим через х₁ -  количество продукции вида П1, шт.

х₂ – количество продукции вида П2, шт.

х₃ – количество продукции вида П3, шт.

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

mах Z(x) = 3,19 х₁ + 6,33 х₂ + 2,45 х₃

при условиях

 
Задание 2

 

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

 

Z(х)=x₁+2x₂+12 max

Определим множество  решений  неравенств. Построим прямые по двум точкам. Затем определим  множество решений строгих неравенств.

(1)  -х₁ +2х₂=2, координаты точек    (х₁=0; х₂=1) и (х₁=0; х₂=-2)

(2)  2х₁ +х₂=4, координаты точек    (х₁=0; х₂=4) и (х₁=0; х₂=2)

(3)  х₁ +х₂=6,  координаты точек (х₁=0; х₂=6) (х₁=6; х₂=0)

(4)  х₁ =0, 

(5)  х₂ =0. 

 

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

Подставим координаты точки (1;1) во все неравенства.

1. 1≤2 – выполняется,
2. 3≤4 – выполняется,
3. 2≤6 – выполняется.

Заштрихуем общую область  для всех  неравенств. Найдем координаты получившегося многоугольника АВСО, решая систему уравнений.

А  А (0; 1)  В  В ( ) 

 

С  С (2; 0)   О  О (0; 0) 

 

Для определения направления  движения к оптимуму построим вектор-градиент , координаты которого являются частными производными =(c₁;с₂)=(1;2).  Построим линию уровня

х₁ +2 х₂+12=0 по двум точкам: (0;-6) и (6;0). Движение линии уровня будем осуществлять в направлении вектора-градиента до точки В ( ), где достигается максимум.

Решение ЗЛП:

 достигается при х₁=1,2; х₂=1,6.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Задание 3

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

Приведем ЗЛП к каноническому  виду и перейдем к задаче на максимум:

mах Z(X)= -x₁ - 3x₂ - x₃

при условиях:  

3x₁ + 7x₂ + x₃ –x₄        =24,

x₁ +  3x₂ +  -x₃                = 10,

2x₁ +         2x₃ +    х₅ =  8,

     х_1,2,3,4,5  ≥ 0.

Матрица условий не содержит три единичных вектора. Введем искусственные переменные y_1,2.    Для нахождения опорного плана переходим к  М-задаче:

max Z’(X,Y)= -x₁ - 3x₂ - x₃ –M (y₁+y₂)  

при условиях:  3x₁ + 7x₂ + x₃ –x₄  + y₁  24,

x₁ +  3x₂ +  -x₃     +    y₂ 10,

2x₁ +          2x₃ +    х₅ =  8,

     х_1,2,3,4,5  ≥ 0.

Дальнейшее решение  проводим в симплекс-таблицах.

№	0		0	-1	-3	-1	0	0	-М	-М
		базис	В	А1	А2	А3	А4	А5	Р1	Р2	Q
0	-М	P1	24	3	7	1	-1	0	1	0	3,4
	-М	P2	10	1	3	1	0	0	0	1	3,3
	0	А4	8	2	0	2	0	1	0	0
			-34М	-4М+1	-10М+3	-2М+1	М	0	0	0
1	-М	P1	0,67	0,67	0	-1,33	-1	0	1		1
	-3	А2	0,33	0,33	1	0,33	0	0	0		10
	0	А4	8	2	0	2	0	1	0		4
			-0,67М-0,99	-0,67М-0,01	0	-1,33М +0,99	М	0
2	-1	А1	1	1,00	0	-2	-2	0,00
	-3	А2	3	0,00	1	1	1	0,00
	0	А4	6	0,00	0	6	3	1,00			6,0
			-10	0,00	0	0	0	0,0

 

Во 2-й симплекс-таблице получен опорный план исходной ЗЛП; поскольку все оценки ∆j ≥0, то этот план является оптимальным, т.е. х₁=1, х₂=3, х₃=0 (исходные переменные), х₄=6, х₅=0 (дополнительные переменные), при этом maxZ’(X) = -10. Перейдем к задаче на минимум,  при этом

min Z(x) = - maxZ’(x) = - (-10) = 10.

 

 

 

 

 

Задание 4

 

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

Составьте  план  перевозок  продуктов  из n  пунктов  отправления  (А_i)  в m  пункты  назначения  (B_j).  План  должен  обеспечить  минимальные транспортные  издержки  и полностью удовлетворить спрос потребителей  на продукты.  Запас (а_i),  потребность  (b_j)  и стоимость перевозки 1  единицы измерения продуктов  (с_ij)  приведены  в табл.

 

 

 

Исходные данные варианта 10

Пункты отправления (Аi)	Пункты потребления (Bj)					Запас (аi)
	В1	В2	В3	В4	В5
	Стоимость перевозки 1 ед изм продуктов (сij)
А1	10	12	11	20	40	330
А2	14	8	9	11	15	270
А3	8	6	12	14	20	350
Потребность (bj)	220	170	210	150	200

 

 

 

1. метод северо-западного угла

 

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

Пункты  отправления		Пункты потребления
		В1	В2	В3	В4	В5
А1	330			11	20	40
А2	270	14				15
А3	350	8	6	12
		220	170	210	150	200

 

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

Так как заполнено не m+n-1 клеток поставим нулевую поставку.

Число занятых клеток     m+n-1= 3+5-1=7.

Опорный план

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

 

2) метод минимального  элемента 

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

Мощности             поставщиков		Мощности потребителей
		В1	В2	В3	В4	В5
А1	330		12		20	40
А2	270	14	8	9
А3	350			12		20
		220	170	210	150	200

 

Число занятых клеток     m+n-1= 3+5-1=7

Опорный план

Суммарные затраты на реализацию данного плана перевозок  составят 10220,  это меньше, чем по  методу северо-западного угла.

 

3) Проверка оптимальности  полученного плана

 

Мощности             поставщиков		Мощности потребителей
		В1	В2	В3	В4	В5	ui
А1	330		12		20	40	u1=0
А2	270	14	8	9			u2=5
А3	350			12		20	u3=2
		220	170	210	150	200
	vj	v1=10	v2=8	v3=11	v4=16	v5=20