Линейное программирование (Составление суточного рациона для скота), страница 4

Начальный план определим методом Северо-Западного угла.

Fнач = 90*6+60*7+50*5+110*4+150*7+30*8+70*11+180*0=3710

После того как начальный план транспортной задачи определён, производится его проверка на оптимальность, для этого:

1.  Определяют потенциалы Ui каждого поставщика, Vj – каждого потребителя . Для каждой заполненной клетки составляют уравнение

Ui+Vj=Cij для xij>0

Так как заполненных клеток m+n-1 , не заполненных m+n , то U1 называют сами , U=0. Из полученной системы определяют потенциалы.

2.  Для каждой не заполненной клетки находят так называемые косвенные тарифы Cij , которые определяются так же Cij=Ui+Vj

Они записываются ниже.

3.  Производится проверка плана на оптимальность по условию Cij<=Cij

Если условие нарушается ,то план усовершенствуется следующим образом:

4.  Помечаем клетку наибольшей положительной разностью Cij-Cij и считаем её заполненной.

5.  Составим цикл от помеченной клетки по заполненным вершинам с этой же самой клеткой. В цикле не участвуют строки и столбцы с одной заполненной клеткой.

6.  Расставим знаки + и – на вершинах цикла в любом направлении начиная пометки со знака +.

7.  В клетках помеченных – выбираем минимальное число θ = min{xij}

8.  Вершины цикла меняются на величину θ в соответствии с поставленным знаком, при этом получается новый план для которого нужно сосчитать величину целевой функции F и т.д

9.  Если всё правильно выполнять по целевая ф-ция убывает.

	6		7		7		5		9		0
90		-	2	60		50		-	6	-	-5	U1=	0
	m		4		m		7		8		0
-		110		-		150		30		-	-3	U2=	2
	7		6		6		8		11		0
-	11	-	7	-	12	-	10	70		180		U3=	5
V1=	6	V2=	2	V3=	7	V4=	5	V5=	6	V6=	-5
F1=	3710
E=	min(60,150,70)		E=60
	6		7		7		5		9		0
90		-	2	0		110		-	6	-	-5	U1=	0
	m		4		m		7		8		0
-		110		-		90		90		-	-3	U2=	2
	7		6		6		8		11		0
-	11	-	7	60		-	10	10		180		U3=	5
V1=	6	V2=	2	V3=	1	V4=	5	V5=	6	V6=	-5
F1=	3350
E=	min(90,10)		E=10
	6		7		7		5		9		0
80		-	2	0		120		-	6	-	-1	U1=	0
	m		4		m		7		8		0
-		110		-		80		100		-	1	U2=	2
	7		6		6		8		11		0
10		-	3	60		-	6	0		180		U3=	1
V1=	6	V2=	2	V3=	5	V4=	5	V5=	6	V6=	-1
F1=	3310
E=	min(80,100)		E=80
	6		7		7		5		9		0
0		-	2	0		200		-	6	-	-2	U1=	0
	m		4		m		7		8		0
-		110		-		0		100		80		U2=	2
	7		6		6		8		11		0
90		-	4	60		-	7	0		100		U3=	2
V1=	5	V2=	2	V3=	4	V4=	5	V5=	6	V6=	-2
F1=	3230

Ответ: оптимальный план F=3230

3.3 Для реализации на ПК была использована программа Microsoft Excel

4  Заключение

В результате проделанной работы была изучена система линейного программирования и освоены следующие методы решения задач линейного программирования :

ü Аналитический

ü Симплекс-метод

ü Графический

В работе использовались следующие прикладные пакеты :

Ø Excel

Ø World

Ø Per

Использование выше перечисленных прикладных программ значительно упрощает вычислительные процессы.