11. Нахождение базиса угловой точки. Пример

Рассм след вспомог задачу: Введем в рассм искусств перемен , ()=y≥0.(1) Т.к. мн-во :(2). И рассм задачу: .

Если Г₁(z^*)<0?,то исх задача имеет несовместную с-му ограничений. Далее будем считать Г₁(z^*)=0

1 случай: В симплекс-табл в мн-ве базисных пер-нных отсутсв.искуственные, то полученную таблицу можно исп. в кач-ве исходной для применения симплек-метода в реш первонач зад. .2 случай: В с-т в соответ точке z*присутствуют искуственные переменные в списке базисных, но при этом все коэф, стоящие в строке, соответ этой искуств перем-ой и столбцам, соотв основным, перем =0, то соответс-ющие огра-ия явл линейной комбинацией ур-ний из с-мы Ах=в и это огр-ия следует удалить. Если в с-т реш зад (2,3)искуственные переменные присутствуют в мн-ве базисных и при этом в строке соответ. Этой искуственной переменной найдется положительный элемент, стоящий в столбцах соотв основ небаз пер-ным, то выбрав этот элемент в кач-ве разреш, следует перещитать с-т с целью перехода к другому базису, рассматрив угл точки.

В оставшихся сл в мн-ве осн. Перем, по опред правилам выделяем переменные, значение которых для выполнения задачи могут быть только =0

Пример 1.

Угловая точка мн-ва планов вспомогательной задачи легко определяется. Это точка x=(0; 0; 0; 80; 0; 4), она имеет единичный базис.

			0	0	0	0	0	-1
Сб	Xб	СЧ
0		80	14	15	18	1	0	0	14/3
-1		4	5	7	2	0	-1	1	4/7->
			-5	-7	-2	0	1	0

			0	0	0	0	0	-1
Сб	Xб	СЧ
0		500/7	23/7	0	96/7	1	15/7	-15/7
0		4/7	5/7	1	2/7	0	-1/7	1/7
			0	0	0	0	0	1

;

Базис точки не содержит искусственной переменной поэтому совпадает с базисом угловой точки мн-ваX.

Для завершения решения задачи, во второй таблице удаляем ∆-оценки, заменяем коэффициент целевой функции на коэффициент целевой функции исходной задачи. Если не предполагается дополн. анализ задачи, то столбцы искуссст. перем. можно удалить.

			-3	-2	-6	0	0
Сб	Xб	СЧ
0		500/7	23/7	0	96/7	1	15/7
0		4/7	5/7	1	2/7	0	-1/7
	J=-8/7		11/7	0	38/7	0	2/7

; ; Минимум целевой ф-ции достигается в точке x=(0; 4/7; 0) мин знач равно 8/7.

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

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

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

ТЗ решается с использованием таблицы спец вида, кот. наз трансп таблицей. Строки соотв пунктам производ, столбцы- пунктам потребления.В правом нижнем углу каждой клетки записыв стоим перев ед прод из i-ого в 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} (с северо-западного угла), то метод получил название «Северо-западного угла».

Метод минимального эл-та отличается только способом выбора клетки для заполнения очередной перевозки: на каждом шаге выбирается клетка с минимальной стоимостью перевозки.