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

Y=(0, 0, 0,0,3,5, 7, 9;11 )

Составляем симплексную таблицу  I итерации и подсчитываем значения

F₀,  z_j – c_j.

Проверяем исходный план на оптимальность:

F₀ = (C,P₀) = 0; z₁ = (C,P₁) = 0 ; z₂ = (C,P₂) = 0; z₃ = (C,P₃) = 0; z₄ = (C,P₄) = 0

z₁ – c₁ = 0 = ; z₂ – c₂ = 0 = ; z₃ – c₃ = 0 = ;

z₄ – c₄ = 0 =  .

Для векторов базиса z_i – c_i = 0 (j = 5,6,7,8).

Составим таблицу I итерации

                                                                                                                     Таблица I

j	Базис	Сб	P0	35	50	100	0	0	0	0	0
				P1	P2	P3	P4	P5	P6	P7	P8
1	P5	0	-3/5	-6	-10	-4	0	1	0	0	0
2	P6	0	-7	-3	-5	-6	0	0	1	0	0
3	P7	0	-9	-1	-2	-15	0	0	0	1	0
4	P8	0	-11	-8	-9	-10	0	0	0	0	1
5			0	35	50	100	0	0	0	0	0

Из базиса выводится 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₁ из дальнейшего рассмотрения (серый фон).