- •Математические модели задач лп
- •1.1. Постановка задачи лп
- •1.2. Рекомендации к составлению математических моделей
- •1.3. Пример задачи лп --- задача о диете
- •Графическое решение задач лп
- •2.1. Каноническая форма задачи лп
- •2.2 Пример
- •2.3. Общие рекомендации к графическому решению задач лп
- •2.4. Пример
- •3. Численные методы решения задач лп
- •3.1. Симплекс – метод
- •3.2. Алгоритм симплекс-метода для задачи на минимум
- •3.3. Алгоритм симплекс-метода для задачи на максимум
- •На шаге 2::
- •На шаге 4: .
- •3.4. Пример
- •3.5. Метод искусственного базиса
- •3.6. Пример
- •3.7. Двойственный симплекс-метод
- •3.8. Пример
- •4. Двойственность в лп
- •4.1. Постановка задачи
- •4.2. Пример
- •4.3. Теоремы двойственности
- •4.4. Пример
- •4.5. Пример
- •5. Метод Гомори
- •5.1. Постановка задачи цлп
- •5.2. Алгоритм метода Гомори
- •Замечания.
- •5.3. Пример
- •6. Транспортная задача лп
- •6.1. Постановка задачи
- •6.2. Построение опорного плана транспортной задачи
- •6.3. Метод северо-западного угла
- •6.4. Пример
- •6.5. Метод минимальной стоимости
- •6.6. Пример
- •6.7. Метод потенциалов
- •6.8. Вычислительная схема метода потенциалов
- •6.9. Пример
- •7. Задания для самостоятельной работы
- •7.1. Построить математическую модель задачи
- •7.2. Привести задачу лп к канонической форме
- •Список литературы
3.5. Метод искусственного базиса
Симплекс-метод применяется для решения задач ЛП, представленных в специальной форме:
(16)
Характерная особенность задачи (16) – известное базисное допустимое решение
Чтобы применить симплекс-метод для решения задачи ЛП в произвольной форме, необходимо привести эту задачу к виду (16), т.е. выделить начальное допустимое базисное решение.
Для этого в симплекс-метод вводят подготовительный этап. Один из методов для реализации подготовительного этапа называется методом искусственного базиса и состоит в следующем [1,2,3].
Вычислительная схема метода искусственного базиса.
Шаг 1.Приводим задачу ЛП к канонической форме
(17)
с неотрицательными правыми частями .
Шаг 2.В каждуюi-ю строку ограничений (17) вводимискусственнуюнеотрицательную переменнуюxiи строимвспомогательную задачу ЛПвида:
(18)
Эта задача имеет допустимое базисное решение и легко может быть сведена к виду (16). Для этого целевую функцию необходимо выразить через свободные переменные:
Шаг 3.Для построенной вспомогательной задачи строим симплексную таблицу
|
b |
… | ||
… | ||||
… | ||||
… |
… |
………….. | ||
… |
и находим оптимальное решение вспомогательной задачи с помощью симплекс-метода.
Шаг 4.Еслии все переменныеявляются небазисными, тоmпеременных извойдут в базис и система ограничений, соответствующих симплексной таблице, будет иметь вид:
(19)
Так как переменные , то их исключили из системы (19), не нарушив при этом равенств. Выражая целевую функцию основной задачичерез небазисные переменныесистемы (19), получим исходную задачу (17) в виде (16).
Шаг 5.Если, но в базисе остались искусственные переменные, для которых(вырожденный случай), то проводим для каждой искусственной переменной из базиса следующее преобразование симплексной таблицы:
Выбираем ведущим столбцом столбец такой переменной , для которой элемент индексной строки, а элемент столбца .
В этом случае строка искусственной переменной будет ведущей и после стандартного преобразования симплексной таблицы (шаг 6 из прямого симплекс – метода) искусственная переменнаявыведется из базиса.
В результате получим симплексную таблицу, соответствующую шагу 4.
Шаг 6.Если, то допустимого решения в исходной задаче (17) не существует (не могут все искусственные переменныебыть равными нулю в задаче (18), а значит система ограничений задачи (17) несовместна) – процесс решения исходной задачи (17) завершается.
3.6. Пример
Выделить допустимое базисное решение для задачи ЛП.
Приведем задачу к канонической форме на минимум с неотрицательными правыми частями.
Заметим, что переменные иможно использовать для введения в исходный базис, поэтому в первую и третью строку ограничений можно не вводить искусственные переменные.
Во вторую строку ограничений вводим искусственную переменную z, потому что в этой строке нет переменной, которую можно взять базисной, не проводя при этом дополнительных преобразований всей системы ограничений.
Полученная вспомогательная задача имеет вид:
Приведем задачу к виду (16):
Выпишем соответствующую симплексную таблицу:
|
B | |||
10 |
5 |
4 |
-1 | |
3 |
3 |
-2 |
0 | |
10 |
5 |
4 |
-1 | |
5 |
2 |
1 |
0 |
Ведущий столбец рекомендуется выбирать не по максимальному положительному элементу строки целевой функции, а так, чтобы из базиса выводилась искусственная базисная переменная (соответствующая ведущая строка должна быть строкой искусственной переменной). Так, выбрав ведущим столбцом, столбец переменной получим ведущую строку - строку с переменнойz(выбирая ведущим столбцом, получили бы ведущую строку, и из базиса выводилась бы переменная).
Итак, искусственная переменная zвыйдет из базиса, а переменная введется в базис.
Симплексная таблица преобразуется к виду:
|
B | |||
0 |
0 |
-1 |
0 | |
8 |
11/2 |
½ |
-1/2 | |
5/2 |
5/4 |
¼ |
-1/4 | |
5/2 |
¾ |
-1/4 |
¼ |
Так как значение , то полученный базисявляется начальным допустимым базисом для исходной задачи ЛП. Чтобы выразить целевую функциючерез небазисные переменные, подставим значение базисной переменнойв целевую функцию. В результате получим:
Тогда исходная задача будет иметь вид специальной формы задачи ЛП:
что и требовалось получить в результате решения вспомогательной задачи.