АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция

РЕШЕНИЕ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ СИМПЛЕКС-МЕТОДОМ

Читайте также:
  1. I. ГИМНАСТИКА, ЕЕ ЗАДАЧИ И МЕТОДИЧЕСКИЕ ОСОБЕННОСТИ
  2. I. ЗАДАЧИ ПЕДАГОГИЧЕСКОЙ ПРАКТИКИ
  3. I. Решение логических задач средствами алгебры логики
  4. I. Розв’язати задачі
  5. I. Ситуационные задачи и тестовые задания.
  6. II. Основные задачи и функции
  7. II. Решение логических задач табличным способом
  8. II. ЦЕЛИ, ЗАДАЧИ И ПРИНЦИПЫ ДЕЯТЕЛЬНОСТИ ВОИ
  9. II. Цель и задачи государственной политики в области развития инновационной системы
  10. III. Разрешение споров в международных организациях.
  11. III. Решение логических задач с помощью рассуждений
  12. III. Цели и задачи социально-экономического развития Республики Карелия на среднесрочную перспективу (2012-2017 годы)

Процедуру решения задач линейного программирования симплекс-методом удобно оформлять в виде симплекс-таблиц. Для этого задачу линейного программирования приводят к стандартной форме, когда система ограничений состоит из одних уравнений и все переменные неотрицательны, а целевая функция стремится к максимуму. Неравенства любого типа (≤ или ≥) можно преобразовать в равенства путем добавления в левую часть неравенств дополнительных переменных (со знаком «плюс» или «минус»). Переход от минимума к максимуму в целевой функции осуществляется умножением на (-1), т.е. min Z= – max (-Z).

Рассмотрим задачу линейного программирования в виде:

В столбец XБ записываются базисные переменные соответствующие каждому из уравнений. В столбец сБ записываются коэффициенты при базисных переменных в целевой функции (присутствует только в начальной таблице, в последующих не пишется). Столбец В заполняется свободными членами из уравнений системы ограничений.

где cj – коэффициент при переменной xj в целевой функции.

В дальнейшем каждая симплекс таблица будет отражать одну итерацию симплекс-метода.

 

Алгоритм симплекс-метода

Если же в исходной задаче стандартного вида нет базисных переменных с единичной матрицей коэффициентов, то применяют метод искусственного базиса. Пусть, для определенности, в первых s уравнениях системы ограничений отсутствует единичная матрица коэффициентов (это всегда можно сделать простой перестановкой уравнений). Построим новую вспомогательную задачу.

Так как во втором и третьем уравнениях нет единичной матрицы переменных, воспользуемся методом искусственного базиса и введем переменные y1 и y2, целевая функция при этом тоже изменится.


1 | 2 | 3 | 4 | 5 | 6 | 7 |

Поиск по сайту:

Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.004 сек.)