Контрольная работа по "Высшей математики"

 

Итерация: 1  Заполним клетку a1,b5.

Сравним значения остатков для производителя a1 и потребителя b5.

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

Ненулевое значение остатка по запасам для a1 показывает, сколько единиц продукции у него осталось не потребленной.

	= 120	= 80	80	= 70	= 90
= 150					90       0	60
= 130			X       3			130
= 160						160
	120	80	80	70	0

 

Итерация: 2  Заполним клетку a2,b3.

Сравним значения остатков для производителя a2 и потребителя b3.

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

Ненулевое значение остатка по запасам для a2 показывает, сколько единиц продукции у него осталось не потребленной.

	= 120	= 80	80	= 70	= 90
= 150					90       0	60
= 130			80       3			50
= 160				X         3		160
	120	80	0	70	0

 

Итерация: 3

	= 120	= 80	80	= 70	= 90
= 150					90       0	60
= 130	X         5		80       3			50
= 160				70         3		90
	120	80	0	0	0

 

Итерация: 4

	= 120	= 80	80	= 70	= 90
= 150	X          7				90       0	60
= 130	50         5		80       3			0
= 160				70         3		90
	70	80	0	0	0

 

Итерация: 5

	= 120	= 80	80	= 70	= 90
= 150	60          7				90       0	0
= 130	50         5		80       3			0
= 160		X           8		70         3		90
	10	80	0	0	0

 

Итерация: 6

	= 120	= 80	80	= 70	= 90
= 150	60          7				90       0	0
= 130	50         5		80       3			0
= 160	X         13	80          8		70         3		10
	10	0	0	0	0

 

Итерация: 7

	= 120	= 80	80	= 70	= 90
= 150	60				90	0
= 130	50		80			0
= 160	10	80		70		0
	0	0	0	0	0

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

	= 120	= 80	80	= 70	= 90
= 150	60				90
= 130	50		80
= 160	10	80		70

 

3) Проверим полученный опорный план на не вырожденность. Количество заполненных клеток N должно удовлетворять условию N=n+m-1. В нашем случае N=7, n+m=5+3=8 , что удовлетворяет условию не вырожденности плана.

4) Вычислим общие затраты на перевозку всей продукции. Для этого запишем транспортную таблицу в которой совместим найденный опорный план с величинами издержек. В левом верхнем углу каждой клетки будем указывать количество единиц продукции а в правом нижнем затраты на перевозку единицы продукции.

	= 120	= 80	80	= 70	= 90
= 150	60          7				90       0
= 130	50         5		80       3
= 160	10        13	80          8		70         3

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

= 890

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

Итерация: 1 Составим вспомогательную рабочую матрицу затрат. Она строится из исходной матрицы издержек (см. Таблицу 3) путем переноса только тех ячеек Pij которые соответствуют заполненным клеткам транспортной таблицы. Остальные ячейки остаются пустыми.

Кроме того, введем вспомогательный столбец в который внесем значения неизвестных U1 ... U3 (3,это m - число складов) и вспомогательную строку в которую внесем значения неизвестных V1 ... V5 (5,это n - число потребителей). На рисунке они представлены желтым цветом. Эти n+m неизвестных должны для всех (i,j), соответствующих загруженым клеткам, удовлетворять линейной системе уравнений

Ui+Vj=Pij

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

Рабочая матрица затрат с рассчитанными потенциалами представлена ниже.

	7				0	= 0
	5		3			= -2
	13	8		3		= 6
	= 7	= 2	= 5	= -3	= 0

 

Порядок вычисления потенциалов был следующий:

1) Пусть V5 = 0 ;

2) U1 = P1,5 - V5 ;

3) V1 = P1,1 - U1 ;

4) U2 = P2,1 - V1 ;

5) V3 = P2,3 - U2 ;

6) U3 = P3,1 - V1 ;

7) V2 = P3,2 - U3 ;

8) V4 = P3,4 - U3 ;

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

	7	10	-1	9	0	= 0
	5	6	3	9	2	= -2
	13	8	-4	3	-6	= 6
	= 7	= 2	= 5	= -3	= 0