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 .


 

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

28878. Внешняя политика Петра I. Провозглашение России империей 31.5 KB
  Провозглашение России империей. Разрешение этих задач было необходимо для обеспечения внешней безопасности России на юге и на западе. Ее преобладание тяжело сказывалось на государствах близких к Балтийскому морю: на Дании Польше России. У России Ингрию и Карелию.
28879. Эпоха дворцовых переворотов и укрепление позиций дворянства 31.5 KB
  В отечественной истории являлось эпохой дворцовых переворотов напрямую связанных с реформами Петра I. Меньшиков Толстой и другие под прикрытием гвардии добилась провозглашения вдовы Петра Екатерины I 1725 1727 гг. В период царствования малолетнего Петра II 17271730 гг. На трон была провозглашена племянница Петра I вдовствующая герцогиня Курляндская Анна Ивановна 17301740 гг.
28880. Внутренняя политика эпохи «просвещенного абсолютизма» Екатерины II 29 KB
  Созыв Комиссии был обусловлен необходимостью кодификации законов т. В дебатах депутатов Уложенной комиссии находит выражение острая борьба трех основных направлений по проблемам модернизации общественного устройства России: консерваторов умеренных и реформаторов. Третья наиболее последовательная и радикальная группа не имея возможности выступать открыто сформировалась за пределами Уложенной комиссии. под предлогом начавшейся русскотурецкой войны Екатерина прервала заседания Комиссии чтобы больше их не возобновлять.
28881. Внешняя политика России во второй половине XVIII века 27.5 KB
  Внешняя политика России во второй половине XVIII века. была приведена чрезвычайно энергично со стороны России. В ответ на попытки Турции вернуть отошедшие к России территории русские войска в 178З г. к России отошло побережье Черного моря от Южного Буга до Днестра.
28882. Основные тенденции мирового развития в первой половине XIX века 23.5 KB
  Основные тенденции мирового развития в первой половине XIX века: 1 Мир развивался под влиянием промышленной революции; Промышленная революция переход от ручного труда к машинному. Причины пром. Новшества пром. промть автоматич.
28883. Попытки модернизации государственного строя в России в первой половине XIX в. 34.5 KB
  Попытки модернизации государственного строя в России в первой половине XIX в. который одним из первых в России осознал необходимость реформ. Сперанского автора всеобъемлющей системы обновления государственного управления в России. Сперанский завершил разработку Введения к уложению государственных законов предполагавшего превращение России из самодержавного государства в конституционное имеющее законодательные преграды на пути возрождения деспотизма.
28884. Внешняя политика России в первой половине XIX в. 30.5 KB
  Внешняя политика России в первой половине XIX в. Успешной для России была война со Швецией 1808 1809 гг. по итогам которой России отходила вся территория Финляндии и Аландские острова. В соответствии с заключительным актом конгресса к России отошла большая часть герцогства Варшавского Познань была отдана Пруссии Галиция Австрии.
28885. Реформы 60–70 годов XIX в.и их историческое значение 36.5 KB
  Явственно проявилось отставание России от передовых капиталистических государств в экономической и социально-политической сферах. было приведение экономической и социально-политической системы России в соответствие с потребностями времени. Значение реформ: способствовали более быстрому развитию капиталистических отношений в России. Были сделаны первые шаги по расширению роли общественности в жизни страны и превращении России в буржуазную монархию.
28886. Социально-экономическое и политическое развитие страны в пореформенный период (60–80 гг. XIX в.) 33 KB
  В пореформенный период в России был начат масштабный переход к индустриальному обществу в целом того же типа который сложился в странах Западной Европы. Основная черта пореформенной эволюции сельского хозяйства в России проявлялась в том что оно принимало все более торговый предпринимательский характер. Огромное значение в индустриализации России имело развитие транспорт главным образом железнодорожного. Быстрое развитие капитализма приводило к тому что для возникновения привилегированных прослоек типа рабочей аристократии Запада в...