Линейное программирование (Составление плана использования технологических способов в производстве), страница 6

3.1 Нахождение начального плана транспортной задачи

3.1.1  Метод Северо-Западного угла

Данная задача не сбалансирована, и для того чтобы её сбалансировать, в таблицу добавляется лишний столбец.

1) Сравниваем величины a1 и b1, возможны три варианта:

•   al<bl, тогда => xl l=al, b1’= bl -а1

При этом первая строка выходит из рассмотрения.

•   bl <а1=>х11= bl, а1’=а1- bl

При этом первый столбец выходит из рассмотрения.

•    al=bl=>xll=al=bl

При этом и первая строка и первый столбец выходят из рассмотрения, и в дальнейшем будем иметь вырожденное решение.

2)  Выбирают следующую Северо-Западную клетку и аналогично сравнивают

a_iс Ь_г выбирая из них меньшее и т.д..

3)  Последняя клетка заполняется автоматически.

4)  Проверяем количество заполненных клеток в таблице, их должно быть m+n-1. Если количество заполненных клеток оказалось меньше, чем m+n-1, то решение вырождено и необходимо в этом случае дополнить недостающее количество, чтобы получилось m+n-1. Для этого в клетку ставят 0, считая эту клетку заполненной.

Внимание: При   постановке   0   не   должно   получаться   замкнутых прямоугольников.

	90	110	60	200	100	180
200	6 90	7 110	7	5	9	0
290	m	4 0	m 60	7 200	8 30	0
250	7	6	6	8	11 70	0 180

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

Fнач=90*6+110*7+200*7+30*8+60*100=8950

3.2. Нахождение оптимального плана методом потенциалов

После   того   как   начальный   план   транспортной   задачи   определен, производится его проверка на оптимальность, для этого: 1. Определяют потенциалы Ui каждого поставщика, Vj- каждого потребителя. Для этого для каждой заполненной клетки составляют уравнение

Ui+Vj=Cij  для  Vxij>0

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

Итерация 1:

	90	110	60	200	100	180
200	6 90	7 110	7 m-3	5 10	9 11	0 0	U1=0
290	m 3	4 0	-  m 60	7 200	+   8 30	0 -3	U2=-3
250	7 6	6 7	*     +    6 m-3	8 10	-           111 70	0 180	U3=0
	V1=6	V2=7	V3=m-3	V4=10	V5=11	V6=0

F=90*6+110*7+200*7+30*8+60*100=8950

= min {60;70}=60

Итерация 2:

	90	110	60	200	100	180
200	6 90	-              7 110	7 6	*    +    5 10	9 11	0 0	U1=0
290	m 3	+             4 0	m 3	-           7 200	8 90	0 -3	U2=-3
250	7 6	6 7	6 60	8 10	111 10	0 180	U3=0
	V1=6	V2=7	V3=6	V4=10	V5=11	V6=0