Сущность линейного программирования и его использования в социальной сфере

 

В индексной строке есть отрицательный элемент, поэтому  проведём следующую итерацию:

СБ	Б	0	12	14	0	0	0
		Р0	Р1	Р2	Р3	Р4	Р5
0	Р3	у–1085	0	0	1	–7/4	1/4
14	Р2	525/8	0	1	0	7/32	5/32
12	Р1	245/4	1	0	0	–1/16	3/16
		6615/4	0	0	0	37/16	1/16

 

Так как в индексной  строке все элементы неотрицательны, то данный план является оптимальным. Таким образом, при у≥3500/3 план х₁* = 245/4, x₂* = 525/8, х₃* = (у–1085), х₄* = 0, х₅* = 0, а значение функции равно Z* = 6615/4.

 

2. Теперь рассмотрим случай  у < 3500/3. Тогда в таб. 1 ведущей строкой будет первая строка:

СБ	Б	0	12	14	0	0	0
			Р0	Р1	Р2	Р3	Р4		Р5
0	Р3	у	7	10	1	0	0	у/10
0	Р4	700	5	6	0	1	0	700/6 = 117
0	Р5	560	7	2	0	0	1	560/2 = 280
		0	–12	–14	0	0	0

 

В базис входит вектор Р₂, а покидает его Р₃. Пересчитывая, получаем новую симплексную таблицу:

Таблица 2.

СБ	Б	0	12	14	0	0	0
		Р0	Р1	Р2	Р3	Р4	Р5
14	Р2	у/10	7/10	1	1/10	0	0	у/7
0	Р4	700–3у/5	4/5	0	–3/5	1	0	875–3у/4
0	Р5	560–у/5	28/5	0	–1/5	0	1	100–у/28
		7у/5	–11/5	0	7/5	0	0

Ведущим столбцом будет второй, так как ему в  индексной строке соответствует единственное отрицательное число. При определении ведущей строки среди симплексных отношений a_ip, полученных в последнем столбце, нужно выбрать наименьшее. Все они зависят от у. Определим, в каких интервалах изменения у минимально каждое из чисел a_jp. Для этого рассмотрим три неравенства:

Проанализировав результат, приходим к следующим  выводам:

а₁₁ = у/7 меньше остальных симплексных отношений при у ≤ 560;

а₂₁ = 875–3у/4 меньше остальных отношений при у > 1085;

а₃₁ = 100–у/28 меньше остальных отношений при 560 < у < 1085.

Рассмотрим все три  случая с учетом условий у < 3500/3 и у ≥ 0.

 

2.1. 0 ≤ у ≤ 560. Тогда в таб. 2 ведущей строкой будет первая строка.

СБ	Б	0	12	14	0	0	0
		Р0	Р1	Р2	Р3	Р4	Р5
14	Р2	у/10	7/10	1	1/10	0	0
0	Р4	700–3у/5	4/5	0	–3/5	1	0
0	Р5	560–у/5	28/5	0	–1/5	0	1
		7у/5	–11/5	0	7/5	0	0

В базис входит вектор Р₁, а покидает его Р₂. Пересчитывая, получаем новую симплексную таблицу:

СБ	Б	0	12	14	0	0	0
		Р0	Р1	Р2	Р3	Р4	Р5
12	Р1	у/7	1	10/7	1/7	0	0
0	Р4	700–5у/7	0	–8/7	–5/7	1	0
0	Р5	560–у	0	–8	–1	0	1
		12у/7	0	22/7	12/7	0	0

Так как в индексной  строке все элементы неотрицательны, то полученный план является оптимальным. Таким образом, при 0 ≤ у ≤ 560 оптимален план: х₁* = у/7, х₂*=0, х₃*=0, х₄*=(700–5у/7), х₅* = (560–у), а значение целевой функции равно Z* = 12у/7.

 

2.2. 1085 ≤ у < 3500/3. Тогда в таб. 2. ведущей строкой будет вторая строка:

СБ	Б	0	12	14	0	0	0
		Р0	Р1	Р2	Р3	Р4	Р5
14	Р2	у/10	7/10	1	1/10	0	0
0	Р4	700–3у/5	4/5	0	–3/5	1	0
0	Р5	560–у/5	28/5	0	–1/5	0	1
		7у/5	–11/5	0	7/5	0	0

В базис входит вектор Р₁, а покидает его Р₄,. Пересчитывая, получаем новую симплексную таблицу:

СБ	Б	0	12	14	0	0
		Р0	Р1	Р2	Р3	Р4
14	Р2	5у/8–1225/2	0	1	5/8	–7/8	у–980
12	Р1	875–3у/4	1	0	–3/4	5/4
0	Р5	4у–4340	0	0	4	7	у–1085
		1925–у/4	0	0	–1/4	11/4	0

Ведущим столбцом будет третий столбец, так как  ему в индексной строке соответствует отрицательное число.

СБ	Б	0	12	14	0	0
		Р0	Р1	Р2	Р3	Р4
14	Р2	525/8	0	1	0	–91/64
12	Р1	245/4	1	0	0	41/16
0	Р3	у–1085	0	0	1	7/4
		6615/4	0	0	0	51/16

Так как в индексной  строке все элементы неотрицательны, то полученный план является оптимальным. Таким образом, при 1085 ≤ у < 3500/3 оптимален план: х₁* = (245/4), х₂*=(525/8), х₃*= у–1085, х₄*=0, х₅* =0, а значение целевой функции равно Z* = 6615/4.

2.3. 560 < у < 1085. Тогда в таб. 2. ведущей строкой будет третья строка:

СБ	Б	0	12	14	0	0	0
		Р0	Р1	Р2	Р3	Р4	Р5
14	Р2	у/10	7/10	1	1/10	0	0
0	Р4	700–3у/5	4/5	0	–3/5	1	0
0	Р5	560–у/5	28/5	0	–1/5	0	1
		7у/5	–11/5	0	7/5	0	0

В базис входит вектор P₁, а покидает его P₅. Пересчитывая, получаем новую симплексную таблицу:

СБ	Б	0	12	14	0	0	0
		Р0	Р1	Р2	Р3	Р4	Р5
14	Р2	у/8–70	0	1	1/8	0	–1/8
0	Р4	620–4у/7	0	0	–4/7	1	–1/7
12	Р1	100–у/28	1	0	–1/28	0	5/28
		37у/28+220	0	0	37/28	0	11/28