АкушерствоАнатомияАнестезиологияВакцинопрофилактикаВалеологияВетеринарияГигиенаЗаболеванияИммунологияКардиологияНеврологияНефрологияОнкологияОториноларингологияОфтальмологияПаразитологияПедиатрияПервая помощьПсихиатрияПульмонологияРеанимацияРевматологияСтоматологияТерапияТоксикологияТравматологияУрологияФармакологияФармацевтикаФизиотерапияФтизиатрияХирургияЭндокринологияЭпидемиология

Сущность симплекс – метола и его геометрическая иллюстрация

Процедура поиска по симплекс методу основана на геометрическом представлении ОДР. При этом определяются соответствия между геометрическими и алгебраическими понятиями. К этим соответствия относятся:

-система уравнений в постановке задачи- пространство геометрических решений, определяемое ограничениями в виде уравнений и соответствующих им линий;

-алгебраические решения в виде координат точек – угловая точка, геометрически представляющая собой пересечение образующих линий.

Сущность симплекс-метода геометрически реализуется посредством движе­ния по границам ОДР и перебора угловых точек с оценкой значения функции цели в каждой из них. В ходе поиска по угловым точкам придерживаются двух правил:

- каждая следующая точка должна быть смежной с предыдущей и находиться на одном ребре;

- возврат предыдущей точки не допускается.

7.1Стандартная форма линейных оптимизационных моделей

Для использования симплекс-метода необходимо привести задачу к стандарт­ной форме. Стандартная форма характеризуется следующими особенностями:

1) все ограничения представляются в виде равенств с неотрицательной правой частью;

2) все переменные в постановке задачи имеют неотрицательные значения;

3) целевая функция подлежит максимизации или минимизации (для нашего случая - максимизации).

Преобразование неравенств в равенства осуществляется посредством введе­ния в ограничения избыточных или остаточных переменных. Избыточные перемен­ные увеличивают левую часть ограничения до величины, позволяющей поставить в ограничении знак «=», взамен знака «≤». Остаточные переменные уменьшают ле­вую часть ограничения до величины, позволяющей поставить знак «=», взамен зна­ка «>». В нашем случае все переменные будут избыточными с учетом стандартного представления постановки задачи. Эти же переменные вводятся в функцию цели (1) но в связи с тем, что они являются искусственными, при этих переменных вво­дятся нулевые коэффициенты. С учетом изложенного, постановка задачи в стан­дартной форме имеет вид:

у=500х_щ+900х_д+0* S₁+0* S₂+0* S₃+0* S₄→ max

1,2х_щ+ 2,0х_д+ S₁ = 85

0,38х_щ+1х_д+ S₂ = 30

-х_щ+ х_д+ S₃ = 0

х_д+ S₄ = 20

х_щ,х_д, S₁, S_2, S_3, S₄ ≥ 0, где

S₁…S₄ - избыточные переменные

Графическая иллюстрация ОДР для постановки задачи в стандартной форме представляется следующим образом. Каждую точку ОДР можно определить с по­мощью переменных х_щ,х_д, S₁, S_2, S_3, S₄. Для этого воспользуемся тем, что при S_i =0 (i=1...4), ограничения модели эквивалентны равенствам, которые представляются ребрами ОДР. Например, при S₂=0 ограничение 0,38x_щ+1x_д+S₂=30 принимает вид равенства 0,38.х_щ+1х_д=30, которое геометрически отражает ребро ВС. Уве­личение переменных S_i (S_i>0) будет соответствовать смещению допустимых точек с границ ОДР в его внутреннюю область. Таким образом, переменные х_щ,х_д, S₁, S_2, S_3, S₄, связанные с экстремальными точками А,В,С можно упорядочить с учетом того, какое значение (нулевое или ненулевое) имеет данная переменная в экстре­мальной точке (см. табл.5.1)

Упорядочивание переменных модели

На основе результатов упорядочивания просматривается вывод, что для ОДР:

1) имеются 4 уравнения в постановке задачи (функция цели не учитывается) и 6 неизвестных, поэтому в каждой экстремальной точке как минимум 2 (6-4=2) пе­ременные должны иметь нулевые значения;

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

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

7.2. Решение поставленной задачи на основе симплекс-метода

Алгоритм симплекс-метода с учетом рассмотренных выше закономерностей представляет следующую последовательность шагов:

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

2) выбор из текущих небазисных переменных включаемой в новый базис пе­ременной, увеличение которой обеспечивает улучшение значения функции цели. Если такой переменной нет - конец вычислений, иначе - переход к шагу 3);

3) выбор из переменных текущего базиса исключаемой переменной, которая должна стать небазисной при введении новой включаемой переменной;

4) определение нового базисного решения соответствующего новому составу переменных, затем переход к шагу 2).

Результаты расчетов представлены в табл. 7.2

Таблица 7.2

Дата добавления: 2015-09-18 | Просмотры: 522 | Нарушение авторских прав