12. Свой-ва решений злп.

Угловая точка у=(0,0,800,640,145)

	800	8	25	1	0	0
	640	8	5	0	1	0
	145	1	5	0	0	1

	8	0	1	1/20	-1/20	0
	75	1	0	-1/32	5/32	0
	30	0	0	-7/32	3/32	1
		0	0	1	9	0

Г=6560

х=(75,8,0,0,30)

Пусть предлагается произвести продукцию вида А3. Для производства продукции вида А3 требуется 10 кг сырья, 5 чел/ч физического труда. Выяснить, стоит ли браться за изготовление этой продукции, если прибыль от реализации 1-ой ед. продукции вида А3 составит с тыс. рублей.

Х6 – кол-во ед. продукции вида А3, которую следует выпустить. Тогда каноническая форма новой задачи имеет вид:

Тогда последняя таблица имеет вид:

		80	70	0	0	0	с
	8	0	1	1/20	-1/20	0	1/4
	75	1	0	-1/32	5/32	0	-15/32
	30	0	0	-7/32	3/32	1	105/32
		0	0	1	9	0

Т.о. не имеет смысла производить 3-ю продукцию, если выполняется последнее соотношение. Если оно не выполняется, то задачу следует дорешать.

Св-во решение ЗЛП Т.1(О разрешимости ЗЛП): Для того чтобы ЗЛП была разрешима, т.е. существ x^* из Х, (с, x^*)>=(с, x) для люб х из Х <=> чтобы мно-ство Х не было пустым и целев ф-я огранич сверху на Х. Д-во: =>) Очевидно существ x^* из Х, (с, x^*)>=(с, x) для люб х из Х, Х<>0 Г(х) огран в силу неравенства (с, x^*)>=(с, x), т.е. (с, x^*)>=Г(х). <=) Х<>0, то по утверждению в мн-ве Х существ углов точка=> можно примен симплекс метод, а так как ф-я Г(х) огран сверху на мн-ве планов, то симплекс метод придет к реш задачи. Теор.2:если ЗЛП разрешима то среди её решений обязат найдётся углов точка.Д-во: так как ЗЛП разрешима то по т.1 Х<>0. Но так как у Х существ углов точка=> примен симплекс метод получим решение задачи в угловой точке мн-ва Х.

13. Постановка тз. Построение плана перевозок методом северо-западного угла.

Пусть имеется m пунктов пр-ва однородной продукции с объемами пр-ва а_i, i=1,m, и n пункт. потребления этой продукции с потребностями b_j, j=1,n и ∑_i=1^m a_i=∑_j=1ⁿ b_j .

Известны стоимости c_ij перевозки одной еденицы продукции из i-го пункта производства в j-ый пункт потребления. Требуется определить объем перевозок x_ij≥0 чтобы ∑_i=1^m ∑_j=1ⁿ с_ij x_ij→min при условии, что ∑_j=1ⁿ x_ij=a_i и ∑_i=1^m x_ij=b_j .

Положим x₁₁=min{a₁,b₁}. Если a₁>b₁ , то излишек a₁-b₁ завозим из А₁ в пункт В₂ , т. е. полагаем x₁₂=min{a₁-b₁,b₂}. Если a₁<b₁ , то остаток b₁-a₁ завозим из пункта А₂, т. е. полагаем x₂₁=min{b₁-a₁,а₂}. Продолжая действовать по той же схеме, постепенно исчерпаем запасы в пунктах А₁, … , А_n и удовлетворим запасы в пунктах В₁, … , В_m т. е. получим допустимый план перевозок. Т. к. заполнение таблицы начинается с клетки {1,1} (с северо-западного угла), то метод получил название «Северо-западного угла».