Помощничек
Главная | Обратная связь


Археология
Архитектура
Астрономия
Аудит
Биология
Ботаника
Бухгалтерский учёт
Войное дело
Генетика
География
Геология
Дизайн
Искусство
История
Кино
Кулинария
Культура
Литература
Математика
Медицина
Металлургия
Мифология
Музыка
Психология
Религия
Спорт
Строительство
Техника
Транспорт
Туризм
Усадьба
Физика
Фотография
Химия
Экология
Электричество
Электроника
Энергетика

Записать искусственную задачу для данной канонической задачи линейного программирования и теорему о существовании опорного решения КЗЛП.



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

Рассмотрим каноническую задачу линейного программирования

(1) f(X) = γj xj + γ0 (min),

(2) Аj xj =B,

(3) xj ≥ 0, j = 1, 2, …, n.

Построим для задачи (1) – (3) искусственную каноническую задачу линейного программирования вида:

(4) φ(X) = xn+1 + xn+2 + … +xn+m (min),

(5) Аj xj +E1 xn+1 + E2 xn+2 + … + Em xn+m =B,

(6) xj ≥ 0, j=1,2,…,n, n+1, n+2, … , n+m,

где Ej – единичный вектор (j = 1, 2, …, m) , а xn+1 , xn+2 , … , xn+m – искусственные переменные.

Теорема(о существовании опорного решения). Если каноническая задача линейного программирования имеет хотя бы одно допустимое решение, то эта задача имеет и опорное решение.

▲ Рассмотрим КЗЛП

(1) f(X) = γj xj + γ0,

(2) Аj xj =B,

(3) xj ≥ 0, j = 1,2,…,n,

которая имеет хотя бы одно допустимое решение. Из всех допустимых решений данной задачи выберем допустимое решение с наименьшим числом ненулевых координат. Пусть таким решением будет вектор α = ( α1, …, α , 0, …, 0), где координаты α1> 0, …, α > 0 (координаты всегда можно перенумеровать так, что первыми из них станут ненулевые) и докажем, что выбранный вектор является опорным решением задачи (1) – (3).

Предположим противное, а именно, что вектор α не является опорным решением. Тогда по определению опорного решения, векторы A1, A2, … A , соответствующие ненулевым координатам выбранного вектора α, образуют линейно зависимую систему. Из определения линейно зависимой системы векторов следует, что найдется ненулевой набор чисел k1, k2, …k такой, что будет выполняться соотношение

(4) A1 k1 + A2 k2 + … + A k = Ө.

Так как вектор α является допустимым решением рассматриваемой задачи, то по определению, этот вектор является решением системы линейных уравнений (2). Тогда по определению решения системы уравнений должно выполняться соотношение

(5) A1 α 1 + A2 α 2 + … + A α = В.

Прибавив к соотношению (5) соотношение (4), умноженное на δ, получим

А1( α1 δ k1) + А2 ( α2 δ k2 ) + … + А ( α δ k ) = B.

Из последнего соотношения по определению решения системы уравнений следует, что векторы α = ( α1 + δ k1, α2 + δ k2, … α + δ k , 0, …, 0) и α = (α1 – δ k1, α2 – δ k2, … α – δ k , 0. …. 0 ) являются решениями системы линейных уравнений (2). Если же число δ выбрать так, что оно удовлетворяет арифметической лемме, то координаты векторов α и α будут удовлетворять условию (3), а сами векторы будут являться допустимыми решениями задачи (1)–(3) и при этом, хотя бы у одного из этих векторов число ненулевых координат будет меньше, чем . Это противоречит выбору допустимого вектора α. Следовательно, вектор α является опорным решением задачи (1)–(3).

 

 




Поиск по сайту:

©2015-2020 studopedya.ru Все права принадлежат авторам размещенных материалов.