Доказательство.

По условию вектор β=(а₁, а₂, … , а_n, a_n₊₁, a_n₊₂, … , a_n₊_m) является оптимальным решением искусственной задачи. Тогда вектор β является опорным решением этой задачи, а, следовательно, и допустимым решением и, по определению, является решением системы линейных уравнений, то есть выполняется соотношение:

А₁а₁ + А₂а₂ + … + А_na_n + E₁a_n₊₁ + E₂a_n₊₂ + … + E_ma_n+m = B,

Так как a_n+1= a_n+2 = … = a_n+m=0, то последнее равенство можно записать в виде: А₁а₁ + А₂а₂ + … + А_na_n = B. Откуда, по определению, следует, что вектор а=(а₁, а₂, … , а_n) является допустимым решением исходной задачи (1) – (3).

Так как вектор β=(а₁, а₂, … , а_n, 0, 0, … , 0) является опорным решением искусственной задачи, то ненулевым координатам этого вектора соответствуют линейно независимые векторы условий этой задачи. Тогда некоторые из указанных линейно независимых векторов соответствуют ненулевым координатам вектора а=(а₁, а₂, … , а_n). Следовательно, вектор а является опорным решением исходной задачи (1) – (3).

От противного. Предположим, что существует число a_n₊_i>0, i=1, 2, … , m, но при этом исходная задача (1) – (3) имеет допустимое решение а=(k₁, k₂, … , k_n), которое удовлетворяет системе (2) и k_j≥0, j=1, 2, … , n. Тогда по определению допустимого решения выполняется соотношение: А₁k₁ + А₂ k₂ + … + А_n k_n = B, которое можно переписать в виде:

А₁ k₁ + А₂ k₂ + … + А_n k_n + A_n+10 + A_n+2 0 + … + A_n₊_m0 = B.

Откуда следует, что вектор β’=(k₁, k₂, … , k_n, 0, 0, … , 0) является допустимым решением искусственной задачи (4) – (6).

Так как по условию вектор β=(а₁, а₂, … , а_n, a_n₊₁, a_n₊₂, … , a_n₊_m) является оптимальным решением искусственной задачи, то φ(β)≤ φ(β’), что равносильно неравенству: a_n₊₁, a_n₊₂, … , a_n₊_m ≤0 + 0 + … + 0. Однако, по предположению, существует a_n₊_i>0, i=1, 2, … , m, следовательно, a_n₊₁, a_n₊₂, … , a_n₊_m >0. Получено противоречие. Таким образом, предположение о существовании допустимого решения исходной задачи является верным. Следовательно, система ограничений исходной задачи является несовместной.

29. 1. Целевая функция исходной задачи (32) – (34) задается на максимум, а целевая функция двойственной (35) – (37) – на минимум. 2. Матрица, составленная из коэффициентов при неизвестных в системе ограничений (33) исходной задачи (32) – (34), и аналогичная матрица в двойственной задаче (35) – (37) получаются друг из друга транспонированием (т. е. заменой строк столбцами, а столбцов – строками). 3. Число переменных в двойственной задаче (35) – (37) равно числу ограничений в системе (33) исходной задачи (32) – (34), а число ограничений в системе (36) двойственной задачи – числу переменных в исходной задаче. 4. Коэффициентами при неизвестных в целевой функции (35) двойственной задачи (35) – (37) являются свободные члены в системе (33) исходной задачи (32) – (34), а правыми частями в соотношениях системы (36) двойственной задачи – коэффициенты при неизвестных в целевой функции (32) исходной задачи. 5. Если переменная xj исходной задачи (32) – (34) может принимать только лишь положительные значения, то j–е условие в системе (36) двойственной задачи (35) – (37) является неравенством вида. Если же переменная xj может принимать как положительные, так и отрицательные значения, то 1 – соотношение в системе (54) представляет собой уравнение. Аналогичные связи имеют место между ограничениями (33) исходной задачи (32) – (34) и переменными двойственной задачи (35) – (37). Если i – соотношение в системе (33) исходной задачи является неравенством, то i–я переменная двойственной задачи . В противном случае переменная уj может принимать как положительные, так и отрицательные значения.

(32):