28485

Алгоритм симплексного методу

Доклад

Математика и математический анализ

Заповнення початкової симплекстаблиці перша ітерація Таблиця 1 В рядках 1 3 записані відповідні рівняння системи 12 при цьому спочатку права частина в стовпці опорний план а потім коефіцієнти при відповідних змінних. Отже з початкової таблиці безпосередньо виписується початковий опорний план: Х1 оп = 0; 0; 182; 316; 238. В нульовому рядку міститься інформація про цільову функцію: для зручності функція 11 розглядається формалізовано як рівняння z 18х1 16х2 = О...

Украинкский

2013-08-20

23.31 KB

2 чел.

13. Алгоритм симплексного методу.

Сформулюємо алгоритм симплексного методу, використовуючи основну теорему про покращення опорного плану. При цьому компактність записів досягатиметься за рахунок роботи з так званими симплекc-таблицями по аналогії із формалізованою реалізацією методу Жордана-Гауса. Економістів цікавлять практичні рекомендації внаслідок проведеного аналізу. Тому в якості модельного прикладу візьмемо конкретну задачу про оптимальне використання сировини, числові дані якої наведені в таблиці.

Складемо математичну модель задачі:

Зведемо її до канонічної форми

де змінні  х3, х4, х5  —  кількість одиниць невикористаної сировини S1, S2,, S3 -  відповідно внаслідок випуску x 1 одиниць продукції П1, і  х 2одиниць продукції П2. 

Заповнення початкової симплекс-таблиці (перша ітерація)

Таблиця 1

              

В рядках 1—3 записані відповідні рівняння системи (12), при цьому спочатку права частина (в стовпці опорний план), а потім коефіцієнти при відповідних змінних. Така перестановка зумовлена зручністю виписування опорного плану безпосередньо із таблиці. В стовпці базисні невідомі (рядки 1—3) записані відповідні базисні змінні ху х4, ху тому решта змінних (х1, х2 ) — вільні. Отже, з початкової таблиці безпосередньо виписується початковий опорний план: Х(1) оп = (0; 0; 182; 316; 238). В нульовому рядку міститься інформація про цільову функцію: для зручності функція (11) розглядається формалізовано як рівняння z - 18х1 - 16х2 = О                                                                                                                                                             

Вмістиме клітинки "опорний план" в нульовому рядку — це значення, яке   набуває цільова функція на відповідному опорному плані. В даному випадку z(X(1))on) =18 ∙ 0+16 · 0 = 0. Надалі в наступних ітераціях необхідно слідкувати за цим значенням. Початковому опорному плану відповідає вершина многогранника допустимих розв'язків, а саме в одній з них цільова функція (11) набуває оптимального значення. Очевидно, що Х(1) оп не може бути оптимальним планом (проаналізуйте!). Цей якісний висновок узгоджується з таким твердженням, що є наслідком основної теореми. Критерій оптимальності опорного плану по симплекс-таблиці: Якщо цільова функція максимізується (мінімізується) і в нульовому рядку відсутні від'ємні (додатні) числа, за винятком стовпчика "опорний план", то опорний план є оптимальним. Аналогічні міркування приводяться і у випадку мінімізації цільової функції. Перш ніж покращувати опорний план, тобто переходити до іншого, на якому цільова функція    набере більшого (меншого) значення,  необхідно виключити випадок нерозв'язаності задачі (Z(max       = оо  ,Z min     = оо).  v   max '    mm .


 

А также другие работы, которые могут Вас заинтересовать

70469. Социально-психологические механизмы и факторы формирования убеждений 32 KB
  Во-первых образуя упорядоченную систему взглядов и представлений человека совокупность убеждений выступает как его мировоззрение; во-вторых под убеждением понимают процесс усвоения человеком внешнего мира что предполагает качественное изменение исходных установок под влиянием жизненного...
70470. Межличностные отношения, их виды, динамика, мехнизмы формирования и развития 36 KB
  Межличностные отношения их виды динамика мехнизмы формирования и развития Межличностные отношения это отношения складывающиеся между отдельными людьми. Межличностные отношения делятся на следующие виды: 1 официальные и неофициальные; 2 деловые и личные; 3 рациональные и эмоциональные...
70471. Социально-психологические характеристики больших групп 42.5 KB
  Социально-психологические характеристики больших групп Большая социальная группа количественно не ограниченная социальная общность имеющая устойчивые ценности нормы поведения и социально-регулятивные механизмы партии этнические группы производственно-отраслевые и общественные организации.
70472. Психология лидерства: классификации и концептуальные подходы 38.5 KB
  Лидером согласно этой теории может быть лишь такой человек который обладает определенным набором личностных качеств или совокупностью определенных психологических черт. Различные авторы пытались выделить эти необходимые лидеру черты или характеристики.
70473. Психология поведения людей в толпе: феномены и механизмы 29.5 KB
  Важнейшим механизмом управляющим поведением и действиями людей в толпе является циркулярная реакция представляющая собой нарастающее обоюдонаправленное эмоциональное заражение людей в неорганизованных общностях и экстремальных ситуациях.
70474. Массовые психические состояния и проявления 29 KB
  Факторы способные вызвать панику многообразны. Факторы особо сильно влияющие на поведение толпы следующие. Факторы определяющие характер мнений и верований толпы бывают двоякого рода: факторы непосредственные и факторы отдаленные.