Контрольная работа по "Методам принятия оптимальных решений"

В базисном столбце все элементы положительные.

Индексная строка не содержит положительных элементов.

Оптимальный план найден:

x₂=

x₁=1

F(min)=90*+72*1=86

 

F(max)=F(min)

 

Задание 3

 

Четыре предприятия данного  экономического района для производства продукции использует три вида сырья. Потребности в сырье каждого  из пред- приятий соответственно равны b1, b2, b3 и b4 ед. Сырье сосредоточено в трех местах его получения, а запасы соответственно равны a1, a2, a3 ед. На каждое из предприятий сырье может завозиться из любого пункта его получения. Тарифы перевозок являются известными величинами и задаются матрицей

c11	c12	c13	c14
c21	c22	c23	c24
c31	c32	c33	c34

 

C=

 

 

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

 

	B1	B2	B3	B4
A1	2	1	6	7	150
A2	5	3	11	2	60
A3	4	2	1	5	90
	40	120	60	80

 

Решение:

Заполним  данную таблицу методом северо-западного  угла.

	B1	B2	B3	B4
A1	2	1	6	7	150
	40	110
A2	5	3	11	2	60
		10	50
A3	4	2	1	5	90
			10	80
	40	120	60	80

Найдем  стоимость перевозки:

F(x)=2*40+1*110+3*10+11*50+1*10+5*80=1180

 

Проведем  поэтапное улучшение начального решения, используя метод потенциалов.

Составим  вспомогательную рабочую матрицу  затрат путем переноса только тех  ячеек P_ij которые соответствуют заполненным клеткам транспортной таблицы. Остальные ячейки остаются пустыми.

Введем  вспомогательные столбец и строку со значениями неизвестных U_i и  V_{j ,} которые находятся из уравнения: U_i+V_j=P_ij.

Для решения  положим что V₄=0:

Итерация: 1

	B1	B2	B3	B4
A1	2	1			U1=13
A2		3	11		U2=15
A3			1	5	U3=5
	V1=-11	V2=-12	V3=-4	V4=0

Теперь  для всех свободных клеток рабочей  матрицы затрат вычислим оценки S_ij, по формуле S_ij = P_ij – U_i - V_j

	B1	B2	B3	B4
A1	2	1	-3	-6	U1=13
A2	1	3	11	-13	U2=15
A3	10	9	1	5	U3=5
	V1=-11	V2=-12	V3=-4	V4=0

Среди оценок есть отрицательные, значит план неоптимален.

Выбираем  из них самую большую по модулю: -13.

Составляем  цикл пересчета:

	B1=40	B2=120	B3=60	B4=80
A1=150	40	110
A2=60		10	50  -	+
A3=90			10  +	80  -

М=50

	B1=40	B2=120	B3=60	B4=80
A1=150	40	110
A2=60		10		50
A3=90			60	30

Итерация: 2 
Рабочая матрица затрат с пересчитанными потенциалами и оценками:

	B1	B2	B3	B4
A1	2	1	10	7	U1=0
A2	1	3	13	2	U2=2
A3	-3	-4	1	5	U3=5
	V1=2	V2=1	V3=-4	V4=0

Ячейка а₃,b₂, транспортной таблицы, должна загрузиться.

 

Составляем  цикл пересчета:

 

	B1=40	B2=120	B3=60	B4=80
A1=150	40	110
A2=60		10 -		50  +
A3=90		+	60	30  -

М=10

	B1=40	B2=120	B3=60	B4=80
A1=150	40	110
A2=60				60
A3=90		10	60	20

 

Итерация: 3 
Рабочая матрица затрат с пересчитанными потенциалами и оценками:

	B1	B2	B3	B4
A1	2	1	6	3	U1=4
A2	5	4	13	2	U2=2
A3	1	2	1	5	U3=5
	V1=-2	V2=-3	V3=-4	V4=0

В таблице  нет отрицательных оценок, следовательно найдено оптимальное решение:

F(x) =40*2+110*1+60*2+10*2+60*1+20*5=490

 

Задание 4

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

F=4x₁-3x₂ → max,

4x₁+x₂ ≤6

2х₁+3х₂≤15

x₁ ≥ 0, x₂ ≥ 0,

x₁, x₂ – целые

X₂

 

6

 D(1,5;-2/3)

5 N

 D’ C (4;3)

4

3

 

2

p

_{1  M K}

 X₁

0            1 2 3 4 5 6 7 8

4x₁+x₂ ≤6

2х₁+3х₂≤15

Граничные точки:

N(0;5) M(0;1) P(1;1) K(1;0)

 

Граница области допустимых решений: NMPK

Построим  прямую D с уравнением F=2 или 4x₁-3x₂=2

Построенную прямую передвигаем в  направлении вектора C до тех пор, пока она не пройдет через последнюю общую точку с многоугольником OMPK.

Искомой является точка K(1;0) в которой целевая функция принимает максимальное значение:

Fmax=4*1-3*0=4