Студопедия

Главная страница Случайная страница

КАТЕГОРИИ:

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






nbsp;   6. Прямой алгоритм с искусственными переменными




 


1. Рассмотрим теперь прямой алгоритм симплексно­го метода для случая, когда каноническая форма полу­чается путем введения в уравнения системы искусствен­ных переменных. Предварительно исходную систему уравнений преобразуем так, чтобы все свободные члены bj были неотрицательны. Пусть дана задача линейного программирования в стандартной форме:

найти

xj³0 (j=1,2, … , n) (6.1)

при условиях

(6.2)

c1x1 + c2x2 + ··· cnxn = z à min (6.3)

Введем в уравнение системы (6.2) базисное множество искусственных переменных xn+i≥0 (i = 1, 2, … ,m). Кро­ме того, в целевой функции перенесем z в левую часть со знаком минус и, таким образом, приравняем (6.3) нулю; получим расширенную систему уравнений;

(6.4)

и

xj³0 (j=1,2, … , n, n+1, … , n+m) (6.5)

Сумму искусственных переменных (обозначим ее че­рез u)

xn+1 + xn+2 + ··· + xn+m = u (6.6)

будем называть, искусственной линейной формой (или u-уравнением).

Исключим переменные xn+1, xn+2, … , xn+m из u-уравнения, вычитая из него сумму первых m уравнений рас­ширенной системы (иначе говоря, находим значения искусственных переменных из уравнений расширенной системы и подставляем их в искусственную форму). Тогда коэффициенты при x1, x2, … ,xn будут соответст­венно равны: d1= –(a11+a12+…+am1), d2= –(a12+a22+…+am2), … , dj= –(a1j+a2j+…+amj), … , dn= –(a1n+a2n+…+amn). Перенесем u в левую часть (со знаком минус), а свободный член — в правую часть с обратным знаком; будем иметь:

d1x1+d2x2+···+dnxn+u0=u, где

u0=b1+b2+···bm,

или d1x1+d2x2+···+dnxn+(-u)=u0 (6.7)

Добавив к расширенной системе уравнений (6.4) пре­образованное u-уравнение (искусственную форму), по­лучим следующую каноническую форму:

(6.8)

Используем алгоритм, описанный в пп. 1, 2, 3 описания прямого симплекс-метода, для получения решения системы (6.4)–(6.5), которое дает минимальное значение u.

Составим начальную таблицу 2 по аналогии с ра­нее составлявшейся таблице с той лишь разницей, что дополняем, её еще одной стро­кой, в клетки которой вписываем коэффициенты dj u-уравнения (6.7). Таким образом, первоначальную табли­цу 2 заполняем соответствующими коэффициентами канонической формы (6.8), при этом в клетках, относя­щихся к базисным переменным, нули писать не будем.

2. Пусть дана стандартная форма задачи линейного программирования (в сокращенной записи):

найти

xj³0 (j=1,2, … , n) (6.9)

при условиях

(i=1,2, … , m), (6.10)

дающих

, (6.11)

при этом

bi³0 (i=1, 2, … , m). (6.12)

Введем искусственные переменные хn+j, связанные с x1, x2, … , xn; получим расширенную систему:



(i=1, 2, … , m), (6.13)

, (6.14)

xj³0 (j=1,2, … , n, n+1, … , n+m). (6.15)

Как было принято, искусственная линейная форма (сумма искусственных переменных) есть

xn+1+ xn+2++ xn+m=u (6.16)

Теперь задача состоит в том, чтобы найти минималь­ное значение u. Для этого используем алгоритм, описан­ный в описании прямого симплекс-метода, чтобы получить решение системы (6.13)—(6.15), которое дает минимальное значение искусственной линейной формы u. При условии xn+1=0, xn+2=0, … , xn+m=0 очевидно, решение системы (13) эквивалентно системе (10).

В системе (6.13) искусственные переменные xn+i (i=l, 2, …, m) образуют базис. Путем преобразований указанной системы искусственные базисные переменные xn+i будут переходить в число небазисных переменных, а последние вводятся в базис вместо искусственных переменных. Переход от одного базиса к другому на не­которой итерации приведет к тому, что базис не будет содержать ни одной искусственной переменной. Этот переход осуществляется путем применения указанного алгоритма; при этом решается задача о минимизации u.

Действительно, указанный алгоритм можно приме­нить, поскольку расширенная система представляет ка­ноническую форму с базисом (xn+1, xn+2, … , xn+m). Чёрез некоторое число итераций соответствующее базисное решение даст min u. При этом минимальное значение целевой функции может быть или положительным, или равным нулю, так как u есть сумма неотрицательных переменных. В самом деле, так как u≥0, то и min u≥0.

В случае если окажется min u>0, то задача не име­ет допустимого решения. В самом деле, поскольку система (6.13)—(6.14) не имеет неотрицательных решений, для которых xn+1=0, xn+2=0, … , xn+m=0 (тогда min u=0), то и исходная система также не имеет неотрицательных решений, и процесс решения на этом заканчивается.



Если min u=0, то для минимального значения u ре­шение будет ( , , …, , , …, ), так как из условия + +…+ =min u=0 следует =0, =0, … , =0. Следовательно, ( , , …, ) есть неотрицательное решение исходной формы системы, при этом среди компонент , , …, не более m отличных от нуля. Решение начинаем следую­щим образом:

исключаем из дальнейшего рассмотрения все не базисные переменные, соответствующие u-строке табли­цы 2 положительным (не нулевым) коэффициентам dj;

заменяем искусственную форму и линейной формой z, которая получается после исключения из u-строки всех базисных переменных.

Отметим, что искусственную переменную, исключен­ную из базиса в результате некоторой итерации, не сле­дует в дальнейшем вводить ни в один из последующих базисов; поэтому нет необходимости делать преобразо­вания последних m столбцов.

Таким образом, вычисления начинаем с расширенной задачи. После того как выяснится, что в u-строке таб­лицы достигнут min=0, приходим к решению исходной задачи.

Решение задачи линейного программирования пря­мым алгоритмом симплексного метода с введением в ее стандартную форму искусственных переменных нагляд­но показано в блок-схеме 2.


Блок-схема 2

Алгоритм прямого (с искусственными переменными) симплекс-метода.


 

Таблица 2

 

Симплекс-таблица (исходная).

 

 

Базисн. перем. x1 x2 xj xk xn xn+1 xn+i xn+m (-z) (-u) Свободн. члены
xn+1 a11 a12 a1j a1k a1n 1 b1
xn+2 a21 a22 a2j a2k a2n b2
xn+i a n+i,1 an+i,2 an+i,j an+i,k an+i,n 1 bi
xn+r a n+r,1 an+r,2 an+r,j an+r,k an+r,n br
xn+m an+m,1 an+m,2 an+m,j an+m,k an+m,n 1 bm
(-z) c1 c2 cj ck cn 1 0
(-u) d1 d2 dj dk dn 1 (-u0)

РЕКОМЕНДУЕМАЯ ЛИТЕРАТУРА.

 

1. Горстко А. Б. Познакомьтесь с математическим моделированием.

- М.: Знание , 1991. – 160 с.: ил.

2. Вершинин О. Е. Компьютер для менеджера: Уч. пособие.

- М.: Высш. школа , 1990. – 240 с.: ил.

3. Ромакин М. И. Математический аппарат оптимизационных задач.

- М.: Статистика, 1975.

4. Щедрин Н. И., Кархов А. Н. Математические методы программирования в экономике. – М.: Статистика, 1974.

5. Конторович Л. В., Горстко А. В. Оптимальные решения в экономике. - М.: Наука , 1972.

 

 


mylektsii.ru - Мои Лекции - 2015-2018 год. (0.011 сек.)Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав Пожаловаться на материал