Для решения задачи симплекс-методом приведем систему неравенств

Задача №1.

Даны коэффициенты прямых затрат aij и конечный продукт Yi для двухотраслевой экономической системы. Данные приведены в таблице (используя личные числовые данные: m=4 и n=4).

1. Определить коэффициенты полных затрат, вектор валового выпуска, межотраслевые поставки продукции;

2. Проверить продуктивность матрицы коэффициентов прямых затрат;

3. Составить и заполнить таблицу межотраслевого баланса.

4. Найти матрицу косвенных затрат.

Отрасль	Коэффициенты прямых затрат aij	Конечный продукт Yi
	0,5	0,1
	0,3	0,2

 

Преобразуем табличные данные в матрицы:

1) Матрица коэффициентов прямых затрат А.

А=	0,5	0,1
0,3	0,2

2) Вектор конечной продукции Y.

Y=

 

Решение:

1. Определить коэффициенты полных затрат.

Необходимо найти матрицу полных затрат В=(E-А)^-1

1) Находим матрицу К=(Е-А)

 

Е - А =			-	0,5	0,1		0,500	-0,100
		0,3	0,2	=	-0,300	0,800

 

2) Для нахождения матрицы К^-1=(Е-А)^-1, необходимо вычислить определитель матрицы.

|К| =	0,500	-0,100	=0,370
-0,300	0,800

 

Так как |K|≠0, то существует матрица К^-1 = В обратная заданной матрице К.

Каждому элементу матрицы К находим алгебраическое дополнение

К₁₁ = (-1)^⁽¹⁺¹⁾* 0,800 = 0,800

К₁₂ = (-1)^⁽¹⁺²⁾* (-0,300) = 0,300

К₂₁ = (-1)^⁽²⁺¹⁾* (-0,100) = 0,100

К₂₂ = (-1)^⁽²⁺²⁾* 0,500 = 0,500

Элементы обратной матрицы получаются путем деления алгебраических дополнений на определитель

В= K-1 =	0,800	0,100	: 0,370 =	2,162	0,270	Коэффициенты полных затрат
0,300	0,500	0,811	1,351

 

 

Определить вектор валового выпуска X.

 

X = B*Y

В – матрица полных затрат;

Y – вектор конечной продукции.

	2,162	0,270				2351,351	Х1
X =	0,811	1,351	*		=	1756,757	Х2

 

Определить межотраслевые поставки продукции.

X_ij = α_ij * x_j

α_ij – коэффициенты прямых затрат

x_j - валовые объемы отраслей.

 

X₁₁ = a₁₁ * x₁ = 0,5*2351,351= 1175,676 X₂₁ = a₂₁ * x₁ = 0,3 *2351,351= 705,405

X₁₂ = a₁₂ * x₂ = 0,1*1756,757= 175,676 X₂₂ = a₂₂ * x₂ = 0,2*1756,757= 351,351

Проверить продуктивность матрицы коэффициентов прямых затрат

X ≥ A*X

	0,5	0,1		2351,351		1351,351
А*х =	0,3	0,2	*	1756,757	=	1056,757

2351,351	>	1351,351
1756,757	1056,757

 

Каждый элемент матрицы X, больше соответствующего элемента матрицы А*Х.

Условие выполнено, следовательно матрица продуктивна.

Составим и заполним таблицу межотраслевого баланса

потребляющие отрасли производящие отрасли			Конечная продукция Yi	Валовая продукция Хi
	1175,676	175,676	1000,000	2351,351
	705,405	351,351	700,000	1756,757
Zj (чистая продукция)	470,270	1229,730	1700,000
Xj (валовая продукция)	2351,351	1756,757		4108,108

 

Zj= Хi- ∑Хij

Z₁= 2351,351- (1175,676+705,405) =470,270

Z₂ = 1756,757 - (175,676 + 351,351)=1229,730

∑ Zj= ∑ Yj =1700 - первое балансовое отношение

∑ Xj= ∑ Xi = 4108,108 - второе балансовое отношение

 

 

Найти матрицу косвенных затрат

 

Матрицу косвенных затрат найдем по формуле: С=В-Е-А

B-Е-А=	2,1622	0,2703	-	1,0000	0,0000	-	0,5	0,1	=	0,6622	0,1703	косвенные затраты
0,8108	1,3514	0,0000	1,0000	0,3	0,2	0,5108	0,1514

Ответ:

1. Коэффициенты полных затрат В:

2,1622	0,2703
0,8108	1,3514

 

2. Вектор валового выпуска:

2351,351	Х1
1756,757	Х2

 

3. Межотраслевые поставки продукции:

x11 = a11 * x1 =	1175,676
x21 = a21 * x1 =	705,405
x12 = a12 * x2 =	175,676
x22 = a22 * x2 =	1018,182

4. матрица продуктивна.

5. Таблица межотраслевого баланса:

потребляющие отрасли производящие отрасли			Конечная продукция Yi	Валовая продукция Хi
	1175,676	175,676	1000,000	2351,351
	705,405	351,351	700,000	1756,757
Zj (чистая продукция)	470,270	1229,730	1700,000
Xj (валовая продукция)	2351,351	1756,757		4108,108

 

6. Матрица косвенных затрат С:

0,6622	0,1703
0,5108	0,1514

Задача №2.

Предприятие планирует выпуск двух видов продукции: I и II. На производство расходуется три вида сырья: А,В и С.Потребность a_ij на каждую единицу j- го вида продукции i-го вида сырья, запас b_i соответствующего вида сырья и прибыль c_j от реализации единицы j-го вида продукции заданы таблицей:

виды продукции Виды сырья			Запас сырья
Прибыль
План (ед.)	X1	X2

Предполагая, что требуется изготовить в сумме не менее 2 единиц обоих видов сырья.

Решение:

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

При ограничениях

2х₁ +2х₂ ≤ 20

х₁ +х₂ ≤ 10

2х₁ +6х₂ ≤ 36

х₁ +х₂ ≥ 2

х₁;х₂ ≥ 0

Найти максимум линейной функции:

Z= 7х₁ +3х₂ → max прибыль

Z= 7х₁ +3х₂ → max

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

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

2х₁ +2х₂ = 20

х₁ +х₂ = 10

2х₁ +6х₂ = 36

х₁ +х₂ = 2

х_i ≥ 0

 

1) 2х₁ +2х₂ –20 =0

х₁ = 0 х₂ = 10

х₁ = 10 х₂ = 0

 

2) х₁ +х₂ –10 = 0

х₁ = 0 х₂ = 10

х₁ = 10 х₂ = 0

 

3) 2х₁ +6х₂ –36 = 0

х₁ = 0 х₂ = 6

х₁ = 18 х₂ = 0

 

4) х₁ +х₂ = 2

х₁ = 0 х₂ = 2

х₁ = 2 х₂ = 0

Получаем пятиугольник АВСDE.

Приравнивая целевую функцию к нулю, получаем первую опорную прямую(z):

7х₁ +3х₂ = 0

х₁ = 0 х₂ = 0

х₁ = 3 х₂ = -7

Из точки начала координат строим вектор n (7;3), перпендикулярно опорной прямой.

Далее, передвигая линию Z в направлении возрастания (в сторону вектора n). В последней пересекаемой вершине D получаем наибольшее значение z.

Вершина D- это точка пересечения прямых L₁ и L₂ с осью ОХ₁.

Координаты т.D: (точка max) – при которой достигается максимальное значение.

х₁ = 10 х₂ = 0

При этих значениях функция будет равна:

Z= 7х₁ +3х₂ = 70

Т.к. одна из переменных = 0, необходимо оптимизировать производство.

Передвигая линию Z в направлении убывания (по вектору n), перемещаемся в вершину С получаем оптимальное значение z.

Вершина С- это точка пересечения прямых L₁ и L₃.

Находим координаты точки С из системы:

2х₁ +2х₂ ≤ 20

2х₁ +6х₂ ≤ 36

 

по методу Крамера находим Δ, ΔX₁ и ΔX₂.

 

Сначала строим матрицу по левой части уравнения и находим:

Определитель Δ=			=8

Затем в основной матрице столбец (с Х₁) заменяем на данные правой части уравнения и находим:

ΔX1=			=48

После в основной матрице столбец (с Х₂) заменяем на данные правой части уравнения и находим:

ΔX2=			= 32

 

Получаем координаты т.С– при которой достигается оптимальное значение.

 

X₁ = ΔX₁/ Δ = 48/8 = 6

X₂ = ΔX₂/ Δ = 32/8 = 4

 

Для графического определения координаты т.С, необходимо опустить перпендикуляры на оси X₁ и X₂.

 

Координаты т.С: (точка opt) – при которой достигается оптимальное значение.

х₁ = 6 х₂ = 4

 

При этих значениях функция будет равна:

Z= 7х₁ +3х₂ = 54

 

Для решения задачи симплекс-методом приведем систему неравенств

 

2х₁ +2х₂ ≤ 20

х₁ +х₂ ≤ 10

2х₁ +6х₂ ≤ 36

х₁ +х₂ ≥ 2

х₁;х₂ ≥ 0

 

к форме равенств с помощью неотрицательных дополнительных переменных Y_i(i=1;2;3;4):

2х₁ +2х₂ +y₁ = 20

х₁ +х₂ +y₂ = 10

2х₁ +6х₂+y₃ = 36

-х₁ -х₂ + y₄= -2

-7х₁ -3х₂+Z = 0

При этом X_j≥0 (j=1;2); Y_i ≥0 (i=1;2;3;4).

 

Для решения задачи запишем систему с помощью полных симплекс таблиц (Таблица 1):

 

						Таблица 1
	вi	х1	х2	y3	y4	y5	y6	вi/ х1	Решение
Sy3									х= (0;0;20;10;36;-2)
Sy4									Z=0
Sy5
Sy6	-2	-1	-1
Z		-7	-3

 

1) выбираем строку с отрицательным свободным элементом (Sy₆) –«-2»

2) выбираем отрицательный свободный элемент-«-1» в столбце (Х₁)- «разрешающий столбец»

3) свободные члены столбца в_i делим на соответствующие элементы разрешающего столбца (X₁), и наименьшее положительное число будет соответствовать разрешающей строке – «Sy₆»

4) на пересечении находится разрешающий элемент – «-1».

Таблицу №2 заполняем по правилу:

1) на месте разрешающего элемента стоит величина ему обратная

2) элементы разрешающей строки делятся на разрешающий элемент

3) элементы разрешающего столбца делятся на разрешающий элемент и знак меняется

4) остальные элементы новой таблицы находятся по формуле прямоугольника:

новый элемент=старый элемент -(соотв.элемент разреш.строки*соотв.элемент разреш.столбца) /(разрешающий элемент).

Таблица 2;3; – избавляемся от отрицательных чисел в строке Z, по отрицательному числу определяется разрешающий столбец, а далее см. описание выше.

 

Таблица 2
	вi	Sy6	х2	y3	y4	y5	y6	вi/ Sy6	Решение
Sy3									x=(2;0;16;8;32;0)
Sy4									z=14
Sy5									т.Е(2;0)
х1		-1					-1	-2
Z		-7					-7
Таблица 3
	вi	Sy3	х2	y3	y4	y5	y6	вi/ х2	Решение
Sy6		-2			-2			-	x=(10;0;0;8;16;0)
Sy4		0,5						-	z=70
Sy5		-2			-2				т.D(10;0)
х1
Z
В таблице 3 найдено максимальное решение и координаты т.D (т.max). В таблице 3 в строке Z отсутствуют отрицательные элементы, но х2 располагается в столбце, поэтому, столбец Х2 принимаем за разрешающий, и оптимизируем план. Таблица 4
	вi	Sх3	Sх4	y3	y4	y5	y6		Решение
Sy6		-2			-2				x=(6;4;0;8;0;0)
х2		0,5							z=54
Sy5		-0,5	0,25		-0,5	0,25			т.С(6;4)
х1		1,5	-0,25		1,5	-0,25
Z			-1			-1

 

Оптимальный план производства продукции (т.С(6;4));

Оптимальная прибыль Z=54

Остатки каждого вида сырья (0;8;0)

 

Поделиться:

Воспользуйтесь поиском по сайту: