Контрольная работа по "Матиматике"

Итерация: 4

	200	400	100	200
200	200				0
100		100			0
200		200			0
400		100	X		300
	0	0	100	200

Итерация: 5

	200	400	100	200
200	200				0
100		100			0
200		200			0
400		100	100	X	200
	0	0	0	200

Итерация: 6

	200	400	100	200
200	200				0
100		100			0
200		200			0
400		100	100	200	0
	0	0	0	0

Получено допустимое начальное решение (опорный план), удовлетворенны нужды всех потребителей и использованы все запасы производителей.

	200	400	100	200
200	200
100		100
200		200
400		100	100	200

3. Проверим  полученный опорный план на невырожденность. Количество заполненных клеток N должно удовлетворять условию N=i+j-1 . В нашем случае N=6, i+j=4+4=8 , план является вырожденным. Прежде чем двигаться дальше выберем одну незаполненную клетку и запишем в нее число ноль, осуществив нуль-загрузку.

	200	400	100	200
200	200	0
100		100
200		200
400		100	100	200

 

4. Совместим найденный опорный план с величинами издержек

	200	400	100	200
200	200     1	0     7
100		100     3
200		200     5
400		100     4	100     3	200     8

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

Рнач=200*1+0*7+100*3+200*5+100*4+100*3+200*8=3800

 

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

Итерация: 1 Составим вспомогательную рабочую матрицу. Она строится из исходной матрицы издержек путем переноса только тех ячеек Pij которые соответствуют заполненным клеткам транспортной таблицы. Остальные ячейки остаются пустыми. Кроме того, введем вспомогательный столбец в который внесем значения неизвестных U1 ... U4 (4,это i) и вспомогательную строку в которую внесем значения неизвестных V1 ... V4 (4,это j). Эти n+m неизвестных должны для всех (i,j), соответствующих загруженным клеткам, удовлетворять линейной системе уравнений

Ui+Vj=Pij

Эту систему всегда можно решить следующим способом: На первом шаге полагают V4=0. Если на k-м шаге найдено значение неизвестной, то в системе всегда имеется еще не определенная неизвестная, которая однозначно может быть найдена на (k+1)-м шаге из уравнения Ui+Vj=Pij, так как значение другой неизвестной в этом уравнении уже известно. То какую неизвестную можно найти на (k+1)-м шаге, определяют методом проб. Переменные Ui и Vj называются потенциалами.

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

	b1	b2	b3	b4
a1	1	7			u1= 11
a2		3			u2= 7
a3		5			u3= 9
a4		4	3	8	u4= 8
	v1= -10	v2= -4	v3= -5	v4= 0

 

Порядок вычисления потенциалов:

1) Пусть  V4 = 0;

2) U4 = P4,4 - V4 ;

3) V2 = P4,2 - U4 ;

4) V3 = P4,3 - U4 ;

5) U1 = P1,2 - V2 ;

6) U2 = P2,2 - V2 ;

7) U3 = P3,2 - V2 ;

8) V1 = P1,1 - U1 ;

Теперь для всех свободных клеток рабочей матрицы затрат вычислим оценки Sij, по формуле Sij = Pij – Ui - Vj. Каждая такая оценка показывает на сколько изменятся общие транспортные затраты при загрузке данной клетки единицей груза. Таким образом, если среди оценок имеются отрицательные (затраты уменьшаются) то данный план можно улучшить переместив в соответствующую клетку некоторое количество продукции. Если же среди оценок нет отрицательных - план является оптимальным.

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

	b1	b2	b3	b4
a1	1	7	6	-9	u1= 11
a2	5	3	6	-3	u2= 7
a3	4	5	0	-3	u3= 9
a4	6	4	3	8	u4= 8
	v1= -10	v2= -4	v3= -5	v4= 0