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 .


 

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

53395. ІНДУКЦІЯ – МЕТОД ПІЗНАННЯ ІСТИНИ 59 KB
  Як виховати цілісне мислення як сформувати ставлення до математики як до цілісної системи яка забезпечує світопізнання розвиток інтелекту показати практичне застосування логічних методів для встановлення істини у житті людини Покажемо це на прикладі вивчення теми âІндукціяâ. У перекладі з латинської термін âіндукціяâ означає âнаведенняâ. Розрізняють кілька видів індуктивних міркувань: міркування за схемою âповна індукціяâ та міркування за схемою âнеповна індукціяâ. Це індукція шляхом переліку популярна індукція та...
53396. На шляху до сучасності: утвердження індустріального суспільства у провідних державах світу 91.5 KB
  Мета уроку: Систематизувати узагальнити та конкретизувати знання та уявлення учнів про розвиток провідних держав світу в 2 половині ХІХ ст. Тип уроку: урок узагальнення та систематизації знань умінь і навичок. Після цього уроку учні зможуть: Характеризувати процес завершення формування індустріального суспільства у провідних державах Європи та...
53397. Використання інформаційних технологій на уроках математики 1.49 MB
  Застосування компютерної техніки на уроках дозволяє зробити урок нетрадиційним яскравим насиченим наповнюючи його зміст знаннями з інших наочних областей що перетворюють математику з об'єкту вивчення в засіб отримання нових знань. Ефективність застосування нових інформаційних технологій на уроках математики обумовлена наступними факторами: 1 різноманітність форм представлення інформації; 2 висока степінь наочності; 3 можливість моделювання за допомогою компютера різноманітних обєктів і процесів; 4 звільнення від рутинної роботи...
53398. Засоби пошуку інформації в Інтернеті. Принципи функціонування веб-каталогів та пошукових систем. Стратегії пошуку інформації 1.56 MB
  Сьогодні на уроці продовжим вивчати сільське господарство, характеристику тваринництва, узагальнемо спеціалізацію сільського господарства, ознайомимось і оцінемо проблеми і перспективи розвитку сільського господарства, завершимо виконання практичної роботи №9, використовуючи знання з інформатики.
53399. Алгоритм 434 KB
  В цей час решта членів команд задіяні в перехресному опитуванні: задають один одному по 3 теоретичних питання за темою, які готували дома заздалегідь, причому, задають питання та дають відповіді різні члени команди. Оцінює команди журі, до складу якого входять 2 найбільш підготовлених студента (1 бал за кожну правильну відповідь). Вони ж здійснюють контроль часу.
53400. Засоби масової інформації 66 KB
  Good afternoon boys and girls. I’m very glad to see you. We are also pleased to see our guests today and we’ll try to make our lesson useful and interesting. Today we are having our last lesson on Mass Media and our aim is to generalize our knowledge on this question and to get to know something new concerning mass media.
53401. Основні команди роботи з робочою книгою та її аркушами 607.5 KB
  Актуальність теми : при роботі з великими обємами даних важливе значення відіграє їх наглядність та наочність. І навіть наша приймальна комісія використовує електронні таблиці для сортування абітурієнтів та створення бази даних та ведення документації по прийому технікуму.Навчальні цілі заняття : знати правила створення формул в Excel математичні функції СЧЕТЕСЛИ ЧСТРОК ЕСЛИ ІІ рівень абстракції; Оволодіти навичками заповнення електронних таблиць ручним та автоматичним типом вводу даних навчитися проводити розрахунки за...
53402. Інтелектуальне інформ –кафе 525 KB
  Мета: в ігровій формі дати можливість старшокласникам проявити свої розумові та творчі здібності; повторити й закріпити основний матеріал у нестандартній формі; розширити знання про звязки інформатики з іншими предметами; сприяти інтелектуальному та духовному розвитку особистості; розвивати стійкий інтерес до інформатики; формувати творчу особистість; формувати...
53403. Уведення та редагування тексту. Перевірка правопису 69 KB
  Мета уроку Навчальна: Вдосконалити основні знання про текстовий редактор Microsoft Word та його можливості навчити вводити та редагувати текст засобами текстового процесора створювати документи за певною структурою засвоїти правила введення тесту навчитись проводити перевірку правопису. Тип уроку Урок засвоєння нових знань формування умінь та навичок Обладнання Компютери підключені до локальної мережі текстовий процесор Microsoft Word текстовий документ до уроку UROK. Повідомлення теми та плану роботи на уроці мети та завдань...