Студопедия

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

КАТЕГОРИИ:

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






Характеристика вершин области допустимых значений задачи 14.5






 

Вершина Номера соответствующих ограничений или осей системы координат Нулевые переменные Ненулевые переменнвге

А 5-е ограничение и ось х2 хз, х$, х\ х2, х4, х5, хб, х7

В 3-е ограничение и ось х2 хь х6 х2, х3, х4, х5, х7, х8

С 3-е и 4-е ограничения х6, х-/ Х\, х2, х3, х4, х5, х8

Б 4-е и 2-е ограничения х7, х$ х{, х2, х}, х4, х6, хя

Е 2-е и 1-е ограничения х5, х4 хь х2> хг> хб, хт, хв

Р 1-е и 5-е ограничения х4> х3, хй хи х2, х5, х6, х7

Заметим, что в пределах области допустимых значений основ­ных переменных искусственная переменная х8 всегда может быть приравнена к нулю, так как 5-е ограничение из системы (14.15) в этой области можно удовлетворить, подобрав соответствующее неотрицательное значение избыточной переменной х3. Поэтому в пределах области допустимых значений искусственные пере­менные можно исключать из рассмотрения.

Нетрудно заметить следующую особенность: в рассматривае­
мой задаче имеется пять ограничений (не считая условий нео­
трицательности) и семь основных, остаточных и избыточных пе­
ременных; количество ненулевых переменных, не считая искус­
ственную, в каждой вершине равно именно пяти, а количество
нулевых (7 — 5) = 2. В общем случае, если в задаче т ограничений
и п основных, остаточных и избыточных переменных, то каждой
вершине области допустимых значений соответствует т ненуле­
вых переменных и (п — т) нулевых. Как уже указывалось ранее,
такое решение называется допустимым базисным решением, а не- *
нулевые переменные в нем — базисными. \

Посмотрим теперь, как меняется допустимое базисное реше- < ние (далее будем говорить просто «базисное») при переходе от данной вершины области допустимых значений к соседней. Ис­кусственные переменные, как уже отмечалось, мы не будем при­нимать во внимание. Из таблицы 67 видно, что при таком пере­ходе только пара переменных меняется местами. Например, при переходе от вершины А к вершине В переменная х6 переходит в базис, а переменная х3 выводится из базиса. Это свойство сосед­них вершин и было положено в основу вычислительного алго­ритма симплекс-метода.

Другая особенность данного алгоритма — правила, благода­ря которым переход от одной вершины области допустимых значений к другой осуществляется направленно, а именно в


сторону роста целевой функции (если задача решается на мак­симум).

В каноническом представлении исходное (опорное) решение задачи определяется элементарно: все основные и избыточные переменные приравниваются к нулю, а остаточные и искусствен­ные приравниваются к правым частям соответствующих ограни­чений. Поскольку такое решение включает ненулевые значения искусственных переменных, на первых шагах алгоритма они не должны исключаться из рассмотрения. Отметим также, что по­скольку при этом Х| = х2 О, опорное решение соответствует на­чалу координат. Далее общее число ограничений обозначим сим­волом т, а общее число переменных на данном шаге алгоритма — символом п. Таким образом, для рассматриваемой демонстраци­онной задачи на первом шаге т = 5, п = 8.

Все расчеты удобно проводить в так называемых симплексных таблицах, первая из которых (табл. 68) соответствует опорному решению.

Построение первой таблицы проводится по следующим пра­вилам (с учетом того, что опорное решение задачи получено из ее канонического представления).

1. Первая строка таблицы содержит коэффициенты Су, у'= 1,..., 8 при неизвестных в каноническом представлении целе­вой функции (14.14).

2. Первый столбец — это просто сплошная (от 1 до т) нумера­ция переменных, попавших в базис. Этот столбец сохраняется неизменным во всех последующих симплекс-таблицах, хотя на­бор и порядок расположения базисных переменных меняется на каждом шаге алгоритма.

3. Второй столбец содержит список базисных переменных.

4. Величины Сь /= \,..., т из третьего столбца равны соответ­ствующим коэффициентам Су при базисных переменных в кано­ническом представлении целевой функции.

5. Значения базисных переменных Аю, /= \,..., т берутся в со­ответствии с опорным решением. Столбец Аю иногда называют столбцом свободных членов (имея в виду, что он формируется из правых частей исходной системы ограничений).

6. В качестве коэффициентов замещения Ац берутся соответ­ствующие коэффициенты при переменных из системы ограниче­ний в канонической форме (смысл термина «коэффициент заме­щения» будет подробно анализироваться в гл. 16).

7. Элементы индексной строки вычисляются по формуле

т _

(^-Су)=ЕС^-С,, у=а1,...Д (14Л7)

где Ср ]= 1,..., 8 — коэффициенты при соответствующих переменных в выражении для целевой функции в каноническом представлении; С0 = 0.


Оо -с


68. Первая симплекс-таблица задачи 14.5

 

 

 

 

 

Коэффициенты целевой функции               А.а  
  Базисные перемен­ные с, Номера ограниче­ний (для дополни­тельных перемен­ных) До (значение базисных перемен­ных) Коэффициент замещения  
№ п/п (0 (осн.) (осн.) Аэ(*э) (изб., огр. 5) Лц(х4) (ост., огр. 1) Лй(*з) (ост., огр. 2) Аъ(х6) (ост., огр. 3) (ост., огр. 4) Мх*) (иск., огр. 5) А', п + 1

 

1 хА (ост.)                        
2 х5 (ост.)         50;                
3 х6 (ост.)       -10 : ': 1: 8о'^:                
4 х-, (ост.)     ПО                 ПО  
5 л8 (иск.)         _!              
Индексная {?! - -с,) -400М -150 -800             -950
строка         -40АГ1               -441АГ

Заметим, что принятое в каноническом представлении целе­вой функции буквенное обозначение коэффициента при искус­ственных переменных сохранено в симплекс-таблице. В связи с этим, например, второй элемент индексной строки равен вели­чине (-800 - 40М).

Назначение двух последних столбцов симплекс-таблицы будет пояснено ниже. Нулевой элемент индексной строки (2" 0 — С0) равен значению целевой функции на данной итерации симплекс-метода.

Итерационная процедура симплекс-метода сводится к после­довательному преобразованию симплекс-таблиц, что (после ис­ключения искусственных переменных — см. ниже) соответствует последовательному переходу от одной вершины симплекса к дру­гой. На каждой итерации выполняется несколько шагов; рас­смотрим их подробнее.


Поделиться с друзьями:

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