Me-02_Gavrilyak (2)

Двойственная задача:

f(x)=50у1+27у2+34у3+54у4--->max
5у1+4у2+6у3+7у4≤275
2у1+4у3+2у4≤100
3у1+2у2+у4≤85
b=(50,27,34,54)
	275
c=	100
	85
			5 2 3
	5 4 6 7		4 0 2
At=	2 0 4 2		6 4 0
	3 2 0 1		7 2 1
	f(x)=275х1+100х2+85х3--->min
	5х1+2х2+3х3 ≥ 50
	4х1+2х3≥ 27
	6х1+4х2 ≥ 34
	7х1+2х2+х3 ≥ 54

3. Наличие некоторого товара на складах А1, А2, А3 и его потребности в пунктах потребления В1, В2, В3, В4, В5, цена перевозки единицы товара - в таблице. Составить оптимальный план его перевозок, минимизирующий транспортные расходы, проверить единственность плана.	Вариант задачи
		В1	В2	В3	В4	В5	Наличие
	А1	7	4	15	9	14	120
	А2	11	2	7	3	10	150
	А3	4	5	12	8	17	100
	Потребность	65	90	60	70	300

Метод северо-западного угла

	В1	В2	В3	В4	В5	Наличие
А1	1) 7	2) 4	15	9	14	120(55,0)
	65	55
А2	11	3) 2	4) 7	5) 3	10	150(115,55,0)
		35	60	55
А3	4	5	12	6) 8	7) 17	100(85,0)
				15	85
Потребность	65(0)	90(35,0)	60(0)	70(15,0)	300(215)
	В1	В2	В3	В4	В5	Наличие
А1	1) 7	2) 4	15	9	14	120(55,0)
	65	55
А2	11	3) 2	4) 7	5) 3	10	150(115,55,0)
		35	60	55
А3	4	5	12	6) 8	7) 17	100(85,0)
				15	85
А4	0	0	0	0	8) 0	215(0)
					215
Потребность	65(0)	90(35,0)	60(0)	70(15,0)	300(215,0)

Метод наименьшей стоимости

	В1	В2	В3	В4	В5	Наличие
А1	7	4	8) 15	9	7) 14	120(35,0)
			35		85
А2	11	2) 2	7	3) 3	10	150(60,0)
		90		60
А3	4) 4	5	6) 12	5) 8	17	100(35,25,0)
	65		25	10
А4	0	0	0	0	1) 0	215(0)
					215
Потребность	65(0)	90(0)	60(35,0)	70(10,0)	300(85,0)

а1=0			ɣ11=7-(0+7)=0
а1+в3=15	0+в3=15	в3=15	ɣ12=4-(0+10)=-6
а1+в5=14	0+в5=14	в5=14	ɣ14=9-(0+11)=-2
а2+в2=2	(-8)+в2=2	в2=10	ɣ21=11-(-8+7)=12
а2+в4=3	а2+11=3	а2=-8	ɣ23=7-(-8+15)=0
а3+в1=4	(-3)+в1=4	в1=7	ɣ25=10-(-8+14)=4
а3+в3=12	а3+15=12	а3=-3	ɣ32=5-(-3+10)=-2
а3+в4=8	(-3)+в4=8	в4=11	ɣ35=17-(-3+14)=6
а4+в5=0	а4+14=0	а4=-14	ɣ41=0-(-14+7)=7
			ɣ42=0-(-14+10)=4
			ɣ43=0-(-14+15)=-1
			ɣ44=0-(-14+11)=3

	В1	В2	В3	В4	В5	Наличие
А1	7	4	15	9	14	120
		10 +	25 -		85
А2	11	2	7	3	10	150
		80 -		70 +
А3	4	5	12	8	17	100
	65		35 +	-
А4	0	0	0	0	0	215
					215
Потребность	65	90	60	70	300	мин 10

а1=0			ɣ11=7-(0+7)=0
а1+в2=4	0+в2=4	в2=4	ɣ14=9-(0+5)=4
а1+в3=15	0+в3=15	в3=15	ɣ21=11-(-2+7)=6
а1+в5=14	0+в5=14	в5=14	ɣ23=7-(-2+15)=-6
а2+в2=2	а2+4=2	а2=-2	ɣ25=10-(-2+14)=-2
а2+в4=3	(-2)+в4=3	в4=5	ɣ32=5-(-3+4)=4
а3+в1=4	(-3)+в1=4	в1=7	ɣ34=8-(-3+5)=6
а3+в3=12	а3+15=12	а3=-3	ɣ35=17-(-3+14)=6
а4+в5=0	а4+14=0	а4=-14	ɣ41=0-(-14+7)=7
			ɣ42=0-(-14+4)=10
			ɣ43=0-(-14+15)=-1
			ɣ44=0-(-14+5)=9

	В1	В2	В3	В4	В5	Наличие
А1	7	4	15	9	14	120
		35 +	-		85
А2	11	2	7	3	10	150
		55 -	25 +	70
А3	4	5	12	8	17	100
	65		35
А4	0	0	0	0	0	215
					215
Потребность	65	90	60	70	300	мин 25

а1=0			ɣ11=7-(0+1)=6
а1+в2=4	0+в2=4	в2=4	ɣ13=15-(0+9)=6
а1+в5=14	0+в5=14	в5=14	ɣ14=9-(0+5)=4
а2+в2=2	а2+4=2	а2=-2	ɣ21=11-(-2+1)=12
а2+в3=7	(-2)+в3=7	в3=9	ɣ25=10-(-2+14)=-2
а2+в4=3	(-2)+в4=3	в4=5	ɣ32=5-(3+4)=-2
а3+в1=4	3+в1=4	в1=1	ɣ34=8-(3+5)=0
а3+в3=12	а3+9=12	а3=3	ɣ35=17-(3+14)=0
а4+в5=0	а4+14=0	а4=-14	ɣ41=0-(-14+1)=13
			ɣ42=0-(-14+4)=10
			ɣ43=0-(-14+9)=5
			ɣ44=0-(-14+5)=9

	В1	В2	В3	В4	В5	Наличие
А1	7	4	15	9	14	120
		90 +			30 -
А2	11	2	7	3	10	150
		-	25	70	55 +
А3	4	5	12	8	17	100
	65		35
А4	0	0	0	0	0	215
					215
Потребность	65	90	60	70	300	мин 55