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 .


 

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

1279. Экзаменационные вопросы и ответы по Правоведению 449.5 KB
  Государство: понятие, признаки, функции. Происхождение государства и права, сущность права. Понятие конституции РФ, содержание основного закона государства. Понятие и принципы конституционного строя. Понятие и структура государственных органов власти. Взаимодействие административного права с основными отраслями права РФ. Основные виды договоров в хозяйственной деятельности. Налоговое регулирование предпринимательской деятельности.
1280. Теория государства и права. Государственные и политические институты 443 KB
  Понятие, сущность и признаки государства. Форма государственного устройства: понятие и виды. Политический режим: понятие и виды. Понятие, сущность и признаки правового государства. Классификация нормативно-правовых актов. Действие нормативных актов: во времени, в пространстве, по кругу лиц. Конституционные обязанности граждан РФ.
1281. Информационные технологиии в экономике 399 KB
  Понятие и свойства информационной технологии. Эволюция информационных технологий, этапы их развития. Функционально-ориентированные и объектно-ориентированные информационные технологии. Операционные системы как составная часть платформы. Основные понятия открытых систем. Понятие технологизации социального пространства. Использование OLTP-технологии в системах поддержки принятия решений. Технология аналитической обработки данных (OLAP-технология) и средства OLAP-технологии.
1282. Основы менеджмента. Основные школы менеджмента ХХ века 363 KB
  Основные школы менеджмента ХХ века. Внешняя и внутренняя среда организации. Характеристика внутренней среды организации. Система управления. Функции, структура, деятельность. Процесс формулирования стратегии по этапам с разъяснением роли каждого члена организации.
1283. Бутовская линия метрополитена на участке от станции Улица Старокачаловская до станции Битцевский парк и тупики за станцией Улица Старокачаловская 355.5 KB
  Проект Бутовской линии метрополитена на участке от станции Улица Старокачаловская до станции Битцевский парк и тупиков за станцией Улица Старокачаловская разработан на основании технического задания 08.04.2008г. № 2, выданного ГУП города Москвы Московский метрополитен и согласованного Департаментом экономической политики и развития города Москвы.
1284. Проблема соблюдения адвокатской тайны в деятельности адвоката в уголовном процессе 396.5 KB
  Понятие и назначение института адвокатской тайны. Проблема соблюдения адвокатской тайны в уголовном процессе.Основные виды нарушений адвокатской тайны в уголовном процессе.
1285. Расчет кулачкового механизма 94 KB
  Кинематические диаграммы толкателя. Начальный радиус кулачка. Подбор чисел зубьев планетарной передачи. Картина линейных и угловых скоростей. Геометрический расчет зацепления. План скоростей и ускорений.
1286. Выполнение камерального дешифрирования контактных аэроснимков ближнего Подмосковья 105.5 KB
  Дешифрирование снимков для создания базовых карт земель масштаба 1:10000. Требования к рассматриваемому виду дешифрирования. Нормы генерализации. Дешифрирование увеличенных снимков при инвентаризации приусадебных земель.
1287. Завдання з фізики. Визначити кількість пазів на полюс і фазу 108 KB
  Визначити кількість пазів на полюс і фазу. Матеріали, які використовують при виготовленні електричних машин. Виробничий та технологічний процеси. Основні типи валів, які використовують в електричних машинах.