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 .


 

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

80800. Правовое регулирование обращения с химическими и биологическими веществами 29.88 KB
  Закон о санитарноэпидемиологическом благополучии населения предусмотрел в качестве одной из основных мер обеспечения безопасного обращения с потенциально опасными для человека химическими биологическими веществами и отдельными видами продукции государственную регистрацию ст. Потенциально опасные для человека химические биологические вещества и отдельные виды продукции допускаются к производству транспортировке закупке хранению реализации и применению использованию после их государственной регистрации. Правовое регулирование...
80801. Экологические требования при эксплуатации опасных производственных объектов 32.08 KB
  Организация эксплуатирующая опасный производственный объект обязана: соблюдать положения настоящего Федерального закона других федеральных законов и иных нормативных правовых актов Российской Федерации а также нормативных технических документов в области промышленной безопасности; иметь лицензию на осуществление конкретного вида деятельности в области промышленной безопасности подлежащего лицензированию в соответствии с законодательством Российской Федерации; обеспечивать укомплектованность штата работников опасного производственного...
80802. Правовое регулирование генно-инженерной деятельности 32.83 KB
  Внедрение результатов генноинженерной деятельность сопряжено с потенциальными отрицательными последствиями для природы. В связи с этим возникает потребность в правовом регулировании экологических отношений возникающих при осуществлении генноинженерной деятельности. Этим целям служит Федеральный закон О государственном регулировании генноинженерной деятельности .
80803. Меры обеспечения экологической безопасности 31.19 KB
  Экологическая безопасность обеспечивается комплексом правовых организационных финансовых материальных и информационных мер предназначенных для прогнозирования предотвращения ликвидации реальных и потенциальных угроз безопасности смягчения их последствий. Угроза экологической безопасности выражает повышенную вероятность гибели отдельных природных объектов существенного загрязнения отравления или заражения окружающей среды масштабы которых определяются исходя из размеров поражения окружающей среды его устойчивости возможности...
80804. Предупреждение и ликвидация чрезвычайных ситуаций природного и техногенного характера 32.12 KB
  Предупреждение чрезвычайных ситуаций это комплекс мероприятий проводимых заблаговременно и направленных на максимально возможное уменьшение риска возникновения чрезвычайных ситуаций а также на сохранение здоровья людей снижение размеров ущерба окружающей среде и материальных потерь в случае их возникновения. Ликвидация чрезвычайных ситуаций это аварийноспасательные и другие неотложные работы проводимые при...
80805. Правовые меры обеспечения радиационной безопасности 30.43 KB
  Федеральный закон о радиационной безопасности населения закрепляет требования по обеспечению радиационной безопасности при обращении с радиоактивными веществами ядерными материалами. При обращении с источниками ионизирующего излучения организации обязаны: 1соблюдать требования законодательства РФ норм правил и нормативов в области обеспечения радиационной безопасности; 2 планировать и осуществлять мероприятия по обеспечению радиационной безопасности; 3 осуществлять систематический производственный контроль за радиационной обстановкой на...
80806. Правовой режим территорий подвергшихся радиоактивному загрязнению 29.82 KB
  зона эвакуации территория вокруг Чернобыльской АЭС с которой в 1986 г. было эвакуировано население 30километровая зона; 2. зона первоочередного отселения; 3. зона последующего отселения; 4.
80807. Порядок обращения с отходами производства и потребления 31.6 KB
  была принята серия специальных законодательных и иных нормативноправовых актов полностью или частично регламентирующих обращение с отходами в рамках логического правотворчества что послужило прорывом в данной области. определил правовые основы обращения с отходами производства и потребления в целях предотвращения их вредного воздействия на здоровье человека и окружающую среду впервые четко зафиксировал принципы государственной политики в сфере обращения с отходами: охрана здоровья человека поддержание и восстановление благоприятного...
80808. Понятие, система и источники международного экологического права 33.01 KB
  38 Устава Международного суда ООН источниками международного права охраны окружающей среды являются: международные договоры как общие так и специальные; международный обычай как доказательство всеобщей практики признанной в качестве правовой нормы; общие принципы права признанные цивилизованными государствами; вспомогательное право т. Источники международного экологического права разделяются: на общие Устав ООН конвенции общего характера регулирующие наряду с иными вопросами и охрану окружающей среды Конвенция ООН по...