Экономика и менеджмент \ Исследование операций в экономике

Введение в математическое моделирование. Математические методы и моделирование горной промышленности. Количественные методы анализа хозяйственной деятельности, страница 3

Поскольку число переменных в системе уравнений (n) больше числа ограничений (m) , то система имеет множество решений.

Одно из возможных решений можно найти если (n-m) любых переменных при =К.О. Тогда полученную систему из m-уравнений легко решить. Полученное при этом решение называется базисным, а составляющие его m переменные - базисными. Остальные (n-m) переменные называются небазисными или свободными. В каждой конкретной системе уравнений обычно существует несколько базисных решений с различными базисными переменными.

III. Линейная форма задачи линейного программирования достигает своего единственного max значения в крайней точке множества решений.

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

Число перебираемых базисных решений можно сократить путем исключения недопустимых базисных решений.

Допустимое базисное решение или опорное решение представляет собой базисное решение с положительным значением базисных переменных.

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

Этапы решения задач симплексным методом.

· Поиск исходного базисного решения

· Поиск опорного решения

· Поиск оптимального решения

Для того, чтобы решить задачу симплексным методом необходимо в системе ограничений от неравенств перейти к уравнениям, путем введения искусственных неотрицательных переменных.

Если исходную задачу представить в виде:

То ее можно записать в симплексную таблицу следующим образом:

Ряд

Базис

…

A11

…

A1s

…

A1n

…

A2s

…

A2n

…

Ar1

…

Ars

…

Arn

…

Am1

…

Ams

…

Amn

…

M+1

…

Преобразование этой таблицы позволяет заменить базисную переменную Yr на Xs, т.е. перейти к новому базисному решению. Строка R называется разрешающей строкой, столбец S – разрешающий столбец, Ars – разрешающий элемент.

Пересчет коэффициентов матрицы производится следующим образом:

В новой таблице на месте элементов разрешающей строки Arj,Br, записываются α=,

На месте всех других элементов Aij,bi, cj,Q, записываются

и после нехитрых манипуляций получили

Перечертим симплексную таблицу после пересчета симплексной таблицы:

1 2 3 4 5 6 7 8 9 10 11 12 13

Скачать файл