Применение экономико-математического моделирования для обоснования (стр. 3 из 4)
Симплекс – метод применяют к задачам линейного программирования, заданным в каноническом виде, где элементы вектора правых частей ограничений принимают неотрицательные значения:
(3.1)Основные положения, на которых базируется симплекс – метод
1. Каждая вершина многогранника допустимых решений обладает следующими свойствами:
- m её координат имеют значения ≥0 (их называют базисными переменными);
- остальные (n - m) координат равны нулю (их называют свободными переменными);
- вектор – столбцы матрицы коэффициентов А, соответствующие базисным переменным вершины являются линейно независимыми, т.е. с- помощью линейных преобразований их можно привести к единичной матрице.
2. Соседние вершины многогранника допустимых решений отличаются только одной базисной переменной.
3. Переход из одной вершины в другую осуществляется с помощью метода последовательного исключения неизвестных, который называется методом Жордана-Гаусса. В результате чего из базисного решения выводим одну переменную, а вводим другую. Причём, из свободных переменных, не вошедших в базис, вводим ту, которая больше всех уменьшает значение целевой функции. А из базисных переменных выводим ту, которая не нарушает условия неотрицательности базисных переменных у новой вершины. При этом вектор – столбцы матрицы ограничений А, соответствующие новой вершине, так же будет линейно независимыми, т.е. образовывать единичную матрицу.
Алгоритм симплекс – метода
1. Находим первое опорное решение (угловую точку).
2. Составляем симплексную таблицу (см. рис.3.1).
3. Выясняем, имеется ли хотя бы одно отрицательное число ∆j. Если таких чисел нет, то найденное опорное решение является оптимальным. Если же среди чисел ∆j имеются отрицательные, то либо переходят к новому опорному решению, либо устанавливают неразрешимость задачи, когда все коэффициенты столбца матрицы ограничений А, соответствующего отрицательному ∆j, тоже отрицательны.
4. Направляющий столбец (номер вводимой в базис переменной) определяем наибольшим по абсолютной величине отрицательным числом ∆j. Пусть это будет к-ый столбец.
5. Направляющая строка (номер выводимой из базиса переменной) соответствует минимальному из всех соотношений
для положительных значений аik. Пусть это l – ая строка.6. По методу Жордана – Гаусса исключаем переменную Хк из всех ограничений, кроме l –ого, где эта переменная должна быть с коэффициентом 1. Строим, новею симплекс – таблицу.
7. Переходим к этапу 3.
Для поиска первого опорного решения можно использовать следующие методы:
- метод естественного базиса,
- метод искусственного базиса.
Метод естественного базиса применяется для задач линейного программирования, записанных в виде (3.2), где все ограничения неравенства имеют тип "≤" и элементы вектора правых частей ограничений неотрицательны.
(3.2)В этом случае задачу (3.2) приводим к каноническому виду (3.3), вводя в левую часть каждого ограничения неравенства самостоятельную переменную, которые и будут образовывать естественный базис.
(3.3)Метод искусственного базиса применяется для задач, заданных в каноническом виде, или с ограничениями смешанного типа. Если в задаче ограничения смешанного типа, то её сначала преобразуем к каноническому виду (3.1), причем нужно отслеживать, чтобы элементы вектора правых частей были неотрицательными, а затем в каждое ограничение равенство водим по самостоятельной переменной yj , которые и будут образовывать искусственный базис. При этом в целевой функции переменные искусственного базиса записываются с большими отрицательными коэффициентами. В результате преобразований получим задачу вида (3.4).
(3.4) | базис | Сбазис | b | С1 | С2 | … | Сn |
| Х1 | Х2 | … | Xn | |||
| X1базис | С1базис | b1 | a11 | a12 | … | a1n |
| Х2базис | С2базис | b2 | a21 | a22 | … | a2n |
| … | … | … | … | … | … | … |
| Хмбазис | Сmбазис | bm | am1 | am2 | … | amn |
| (Cбазис,b) |  |  | … |  |
Рис. 3.1. Симплексная таблица
Правила заполнения первой симплексной таблицы
1. Вместо С1, С2, …, Сn записываем соответствующие коэффициенты целевой функции.
2. Вместо аij записываем коэффициенты при неизвестных из основных ограничений задачи.
3. Вместо Хiбазис записываем имена переменных, вошедших в базис, в той последовательности, в которой они образуют единичную матрицу.
4. Вместо Сiбазис записываем коэффициенты целевой функции при соответствующих базисных переменных.
5. Вместо bi записываем элементы вектора правых частей задачи.
6.
7.
Оптимальное значение переменных соответствует элементам из столбца «b» последней симплексной таблицы, а максимальное значение целевой функции содержимому ячейки (сбазис ,b).
2.3 Двойственные задачи
Прежде чем строить двойственную задачу, предварительно исходную задачу линейного программирования нужно привести к виду, где все ограничения неравенства имеют один тип, а целевая функция - направление, противоположное типу ограничений неравенств.
Правила построения двойственной задачи.
1. Целевая функция в двойственной задаче меняет своё направление на противоположное.
2. Количество двойственных переменных равно количеству основных ограничений исходной задачи.
3. Двойственная переменная, соответствующая ограничению равенству, является неограниченной по знаку, а соответствующая ограничению неравенству – неотрицательной.
4. Вектор правых частей ограничений исходной задачи является вектором коэффициентов целевой функции в двойственной задаче.
5. Вектор коэффициентов целевой функции исходной задачи является вектором правых частей ограничений в двойственной задаче.
6. Матрица коэффициентов ограничений двойственной задачи – это транспонированная матрица коэффициентов исходной задачи, т.е. строка коэффициентов исходной задачи, является столбцом коэффициентов двойственной задачи.
7. Неотрицательным переменным исходной задачи соответствуют ограничения неравенства в двойственной задаче, причем тип неравенства меняется на противоположный, по сравнению с исходной задачей. А неограниченной переменной исходной задачи соответствует ограничение равенство в двойственной задаче.
Соотношение двойственности является симметричным, т.е. двойственная задача по отношению к двойственной совпадает с исходной.
Если исходная задача линейного программирования записана в стандартном виде: (с, х)→ max
(4.1)то соответствующая ей двойственная задача записывается следующим образом:
(b, y)→min
(4.2)Для следующей задачи линейного программирования построим двойственную задачу.
3x1 + 3x2 – 4x3 → max
-2х1 - х2 + 3х3 ≤ -18 у1