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 .


 

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

11273. ОПРЕДЕЛЕНИЕ ЗАВИСИМОСТИ МОМЕНТА ИНЕРЦИИ СИСТЕМЫ ОТ РАСПРЕДЕЛЕНИЯ МАССЫ ОТНОСИТЕЛЬНО ОСИ ВРАЩЕНИЯ 235 KB
  ОПРЕДЕЛЕНИЕ ЗАВИСИМОСТИ МОМЕНТА ИНЕРЦИИ СИСТЕМЫ ОТ РАСПРЕДЕЛЕНИЯ МАССЫ ОТНОСИТЕЛЬНО ОСИ ВРАЩЕНИЯ Методические указания к лабораторной работе № 10Б по физике Раздел Механика Указания содержат краткое описание рабочей установки и методики ...
11274. Определение момента сил трения и момента инерции махового колеса 266 KB
  Определение момента сил трения и момента инерции махового колеса. Указания содержат краткое описание рабочей установки и методики определения момента инерции махового колеса. Методические указания предназначены для студентов инженерных специальностей...
11275. Определение момента инерции твердых тел методом трифилярного подвеса 235 KB
  Определение момента инерции твердых тел методом трифилярного подвеса Указания содержат описание рабочей установки и методики определения момента инерции твердых тел методом трифилярного подвеса. Методические указания предназначены для студентов инжене
11276. Изучение динамики вращательного движения с помощью маятника максвелла 231 KB
  Изучение динамики вращательного движения с помощью маятника максвелла Указания содержат краткое описание рабочей установки и методики определения момента инерции с помощью маятника Максвелла. Методические указания предназначены для студентов инженерных спе...
11277. Определение коэффициентов трения качения и трения скольжения с помощью наклонного маятника 7.79 MB
  Лабораторная работа Определение коэффициентов трения качения и трения скольжения с помощью наклонного маятника Цель работы: определение коэффициентов трения качения и трения скольжения. Оборудование: измерительная установка секу
11278. Определение ускорения свободного падения на машине Атвуда 258 KB
  Определение ускорения свободного падения на машине Атвуда. Указания содержат краткое описание рабочей установки и методику определения ускорения свободного падения с помощью машины Атвуда. Методические указания предназначены для студентов инженерных специально
11279. ОПРЕДЛЕНИЕ КИНЕМАТИЧЕСКИХ ХАРАКТЕРИСТИК РАВНОПЕРЕМЕННОГО ДВИЖЕНИЯ 178 KB
  ОПРЕДЛЕНИЕ КИНЕМАТИЧЕСКИХ ХАРАКТЕРИСТИК РАВНОПЕРЕМЕННОГО ДВИЖЕНИЯ Цель работы: 1 измерить основные кинематические характеристики равнопеременного поступательного и вращательного движений; 2 познакомиться с методами обработки прямых и косвенных измерений. Обо...
11280. Изучение внешнего фотоэффекта, Световой поток 380.5 KB
  Световой поток – это физическая величина, определяемая оптической мощностью излучения по вызываемому им световому ощущению (по его действию на селективный приемник света с заданной спектральной чувствительностью); измеряется в люменах (лм)...
11281. Определение концентрации раствора сахара при помощи сахариметра 340 KB
  Определение концентрации раствора сахара при помощи сахариметра. Методические указания содержат краткое описание процесса распространения линейно поляризованного света в оптически активных веществах. Методические указания предназначены для студентов инжене...