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

Из базиса выводится P₈ и вводится P₁. 
Таблица II итерации будет иметь вид:

j	Базис	Сб	P0	35	50	100	0	0	0	0	0
				P1	P2	P3	P4	P5	P6	P7	P8
1	P5	0	4,75	0	-13/4	7/2	0	1	0	0	-3/4
2	P6	0	-23,8	0	-13/8	-9/4	0	0	1	0	-3/8
3	P7	0	-61,8	0	-7/8	-55/4	0	0	0	1	-1/8
4	P1	35	11/8	1	9/8	5/4	0	0	0	0	-1/8
5			-385/8	0	85/8	225/4	0	0	0	0	35/8

Из базиса выводится P₇ и вводится P₃.

Таблица III итерации будет иметь вид:

j	Базис	Сб	P0	35	50	100	0	0	0	0	0
				P1	P2	P3	P4	P5	P6	P7	P8
1	P5	0	2,81	0	-191/55	0	0	1	0	14/55	-43/55
2	P6	0	-179/110	0	-163/110	0	0	0	1	-9/55	-39/110
3	P3	100	61/110	0	7/110	1	0	0	0	-4/55	1/110
4	P1	35	15/22	1	23/22	0	0	0	0	1/11	-3,22
5			-1745/22	0	155/22	0	0	0	0	45/11	85/22

 

Из базиса выводится P₆ и вводится P₂.

Таблица IV итерации будет иметь вид:

j	Базис	Сб	P0	35	50	100	0	0	0	0	0
				P1	P2	P3	P4	P5	P6	P7	P8
1	P5	0	6,62	0	0	0	0	1	-382/163	104/163	8/163
2	P2	50	179/163	0	1	0	0	0	-110/163	18/163	39/163
3	P3	100	79/163	0	0	1	0	0	7/163	-13/163	-1/163
4	P1	35	-76/163	1	0	0	0	0	115/163	-4/163	-63/163
5			-14190/163	0	0	0	0	0	775/163	540/163	355/163

 

Из базиса выводится P₁ и вводится P₈.

Таблица IV итерации будет иметь вид:

j	Базис	Сб	P0	35	50	100	0	0	0	0	0
				P1	P2	P3	P4	P5	P6	P7	P8
1	P5	0	6,56	8/63	0	0	0	1	-142/63	40/63	0
2	P2	50	17/21	13/21	1	0	0	0	-5/21	2/21	0
3	P3	100	31/63	-1/63	0	1	0	0	2/63	-5/63	0
4	P8	0	76/63	-163/63	0	0	0	0	-115/63	4/63	1
5			-5650/63	355/63	0	0	0	0	550/63	200/63	0

 

Решение оптимальное.

 
Умножим целевую функцию на -1. 
S = 5650/63 
Y = ( 0; 17/21; 31/63 )

 

 

 

 

 

Задача 3

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

С =

 

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

	B1	B2	B3	B4
A1	5	7	3	5	100
A2	1	2	5	6	150
A3	3	4	1	2	50
	75	80	60	85

 

С =

 

 

 

Решение:

Имеется 3 склада содержащие некоторое  количество единиц однотипной продукции , имеется также 4 потребителя нуждающиеся в определенном количестве данной продукции. При перевозке одной единицы продукции со склада i потребителю j возникают издержки P_ij. Величины издержек приведены в таблице 3. При перевозке K единиц продукции со склада i потребителю j суммарные затраты на перевозку составляют K*P_ij. 
 
Требуется найти такой план перевозок при котором общие затраты на перевозку всей продукции, по всем потребителям, будут минимальны. 
Таблица 3 
Издержки на перевозку единицы продукции со склада i потребителю j

 

 

Склад №	Потребители
	1	2	3	4
1	5	7	3	5
2	1	2	5	6
3	3	4	1	2

 
Шаг:1 
Проверка на сбалансированность

Общее число запасов на складах: 300 Общая потребность: 300 
Задача является закрытой (сбалансированной).

 
Шаг:2 
Отыскание начального решения. Метод северо-западного угла

Запишем настоящую задачу в виде транспортной таблицы. В верхней  строке перечислим потребности потребителей по порядку номеров. В левом столбце  перечислим имеющиеся запасы на складах. На пересечении j-го столбца и i-й строки будем записывать количество продукции, поставляемое с i-го склада j-му потребителю. Пока начальное решение не найдено, оставим эти клетки пустыми.

 

	b1= 75	b2= 80	b3= 60	b4= 85
a1 = 100
a2 = 150
a3 = 50

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

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

 

	b1= 75	b2= 80	b3= 60	b4= 85
a1 = 100	X				100
a2 = 150					150
a3 = 50					50
	75	80	60	85

 

Итерация: 1

Заполним клетку a₁,b₁.

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

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

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

 

 

	b1= 75	b2= 80	b3= 60	b4= 85
a1 = 100	75	X			25
a2 = 150					150
a3 = 50					50
	0	80	60	85

 

 
Итерация: 2

Заполним клетку a₁,b₂.

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

 

	b1= 75	b2= 80	b3= 60	b4= 85
a1 = 100	75	25			0
a2 = 150		X			150
a3 = 50					50
	0	55	60	85

 

 
Итерация: 3

 

 

	b1= 75	b2= 80	b3= 60	b4= 85
a1 = 100	75	25			0
a2 = 150		55	X		95
a3 = 50					50
	0	0	60	85