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 .


 

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

47846. ЗАКОН ХАРДИ-ВАЙНБЕРГА 622 KB
  ЧАСТОТА ГЕНА А и а рассматриваемые аллели N количество диплоидных особей 2N – количество генов D – количество особей с доминантными аллелями АА Н количество гетерозиготных особей Аа R – количество рецессивных особей аа D H R = N D H R структура популяции D H R доля или частота гена доля или частота гена а СЛУЧАЙНОЕ СКРЕЩИВАНИЕ структура популяции частота скрещиваний УСТАНОВЛЕНИЕ РАВНОВЕСИЯ формула теоретической популяции ; экспериментальная популяция
47847. Аспекты информатизации в цивилизации 817.5 KB
  Дробные числа переводятся аналогично но деление на группы проводится двигаясь вправо от десятичной точки и записывая недостающие нули являющиеся значащими. На каждом шаге деления получают цифры числа в системе S начиная с младшей. Отдельно для целой и дробной части числа в произвольной системе счисления.
47848. ПРИКЛАДНІ АСПЕКТИ ЗДІЙСНЕННЯ ІНВЕСТУВАННЯ В ЛЮДСЬКИЙ ПОТЕНЦІАЛ ТОВ «КРИЖАНА ФУДС» 413.77 KB
  Метою випускної кваліфікаційної роботи є розкриття теоретичних та практичних аспектів формування та функціонування ефективного інвестиційного поля для матеріальних та психологічних вкладень в людський капітал, а також визначення напрямів покращення його функціонування у ТОВ »Крижана Фудс».
47849. Модусы иронии в творчестве Евгения Замятина и пародия как средство выражения авторской позиции 159.5 KB
  Дать определение понятий «ирония» и «пародия» с точки зрения Ю.Н. Тынянова; привести классификацию иронико-комических модусов, выделенных в творчестве Е.И. Замятина; интерпретировать авторскую позицию через анализ приёмов иронически-пародийного модуса в книге «Нечестивые рассказы»; рассмотреть особенности комически-пародийного модуса в цикле «Чудеса».
47850. Элементарная логика 244.5 KB
  Логические операции можно объединить с помощью одного понятия – умозаключения или рассуждения. Форма понятия: Т. Форма понятия: круг символизирует любую совокупность предмета а каждая точка внутри символизирует отдельно взятые предметы. 1 суждение – 2 понятия.
47851. Высшая математика 4.3 MB
  Султанаев Высшая математика Курс лекций для студентов всех специальностей очной и заочной форм обучения...
47852. Менеджмент. Общее управление и менеджмент 207 KB
  Общее управление это управленческая деятельность и процессы связанные с разработкой концепции и стратегии развития организации постановкой ее цели планированием организационной деятельностью координированием контролем а при необходимости и корректировкой ранее принятых решений. Необходимо обеспечить наиболее правильное соотношение между цетролизацией и декзентролизацией в зависимости от конкретных условий; вознаграждение персонала; порядок;и инициатива персонала; корпоративный дух преданность организации; единство...
47853. Лекции по правоведению. Власть, политика и право 214 KB
  Предписание права суть таковым: честно жить – другим не вредить каждому своё отдавать. Пентаграмма Схема истинного познания Вещь предмет Образ идея Идеат научный предмет Идеал осознанный предмет Дух энергия синергия познание ведение Цель польза utilit Средства instrumenti процесс Способ механизм процедура стандарт Метод техника opertio Принцип основные положения Слово термин характер характеристика Понятие свойства Категория признак Феноме явление ноомен бытие Концепт этимон Форма структура конструкция...
47854. Лекции по правоведению 609.5 KB
  Во-первых духовнонравственные подходы к праву рассуждения о нравственности права и государства не особенно приветствуется современной наукой права но вместе с тем круг людей способных судить о праве чрезвычайно широк: экономисты политики руководители различных ступеней и уровней все так или иначе сталкиваются с правом но что ещё более примечательно с правовой парадигмой мышления хотя подчас этого и не осознают.7 Конституции РФ: Человек его права и свободы являются высшей ценностью. Мы раскроем природу начал этих парадигм для...