0. 1.3. Построение исходного допустимого базисного множества

В общем случае построение д.б.м. K и x(K) связано с решением вспомогательной задачи, для которой исходное д.б.м. определяется тривиально. Это уже означает, что вспомогательная задача может решаться с помощью основной части МПУ.

Во вспомогательной задаче наряду с векторами ^j=(a_1j, a_2j,… a_mj) фигурируют дополнительные векторы

ⁿ⁺ⁱ = ρ_i eⁱ, i= , (18)

где eⁱ=(0,0,…,0,1,0,…,0) – орты соответствующих координатных осей, а

(19)

Таким образом, здесь имеется n+m векторов с номерами j , где =J J₁, J₁={n+1, n+2,…, n+m}. Назовем вспомогательную задачу, задачей .

Задача . Максимизировать линейную функцию

(20)

на множестве (n+m)-мерных векторов

=(x₁, x₂,…, x_n+m), (21)

удовлетворяющих условиям

x_j , j , (22)

(23)

Вспомогательные векторы , j J₁ являются линейно независимыми, и для них имеет место равенство

(24)

Это означает, что в качестве исходного д.б.м. в задаче может быть принято K=J₁. Ему отвечает допустимый вектор (K) с компонентами

x_j=0, j , x_j=|b_j-n|, j J₁ (25)

Через конечное число итераций процесс МПУ закончиться пунктом (а) процедуры 2. Завершиться пунктом (а) процедуры 4 он не может, т.к. линейная функция (20) ограничена сверху нулем.

С помощью процесса МПУ получим базисное множество , которое является допустимым и двойственно допустимым базисным множеством. Одновременно будут найдены оптимальные векторы и , для которых ( )= ( ). При этом возможны следующие случаи:

1⁰ Множество не содержит элементов множества J₁.

2⁰ Множество содержит некоторый элемент множества J_1, которому отвечает положительная компонента .

Если имеет место случай 1⁰, то в качестве д.б.м. K может быть принят . При этом компоненты x(K) совпадают с соответствующими компонентами .

Если имеет место случай 2⁰, то в исходной задаче A_м допустимых векторов не существует.

Пример 2. Решить задачу A_м с числовыми данными, приведенными в табл. 7.

Таблица 7 Таблица 8

j i	1 2 3
1 2	-2 1 3 2 3 4	-2 -1
	-1 2 -3

j i	1	2	3	4	5
1 2	-2 2	1 3	3 4	1 0	0 1	-2 -1
	0	0	0	-1	-1

Информация для соответствующей вспомогательной задачи записана в табл. 8. При ее решении в качестве исходной информации принимается д.б.м. K={4,5}, (K)=(0,0,0,2,1).

Получаемая промежуточная информация приведена в табл. 9 и 10 (вида табл. 3 и 4). При этом найденные на второй итерации величины z_j неположительные. Это означает, что базисное множество ={4,3} одновременно допустимо и двойственно допустимо и вектор

=(0;0;0.25;1.25;0)

является оптимальным. При этом имеет место случай 2⁰, означающий, что в задаче A допустимых векторов не существует.

Таблица 9

Итерация 1				Итерация 2
4 5	2 1	3.00 4.00	1.00 1.00	4 3	1.25 0.25	- -	1.00 -0.75
5	-3	0.25			-1.25	-

Таблица 10

	1	2	3	4	5
№1 №2	0 -3.5	4 -1.25	7 0	0 0	0 -0.75	3 -