- •Линейное программирование
- •1. Общая задача линейного программирования
- •1.1. Задачи математического и линейного программирования
- •1.2. Математические модели простейших экономических задач
- •2. Каноническая форма
- •2.1. Определение и формы записи
- •2.2. Приведение общей задачи линейного
- •3. Графический метод решения задач
- •3.1. Общие понятия, примеры
- •4. Свойства решений задач линейного
- •4.1. Отрезок в . Понятие выпуклого множества. Гиперплоскость и полупространство, их выпуклость
- •4.3. Теорема о достижении линейной функцией
- •4.4. Опорное решение задачи линейного программирования,
- •5. Симплексный метод решения задач
- •5.1. Нахождение начального опорного плана и переход к новому опорному решению
- •5.2. Метод искусственного базиса
- •6. Теория двойственности
- •6.1. Построение двойственной задачи
- •6.2. Одновременное решение прямой и двойственной задач
- •7. Транспортная задача
- •7.1. Постановка задачи и её математическая модель
- •7.2. Построение первоначального опорного плана
- •7.3. Метод потенциалов
- •Образец типового расчета
- •Реализация задач лп на пк в Exсel
5.2. Метод искусственного базиса
Метод искусственного базиса применяется для решения задач ЛП в случае, когда задача не имеет начального опорного решения с базисом из единичных векторов.
Пример 5.2. Минимизировать функцию при ограничениях
Если ввести дополнительные неотрицательные переменные , , , , то система ограничений примет вид:
( 5.2.1 )
Из ( 5.2.1 ) следует, что очевидного базисного допустимого решения нет. Один из путей преодоления этих трудностей состоит в использовании того же симплекс-метода для порождения базисного допустимого решения. Изменим первые два ограничения (два других не создают проблем) введением в левую часть искусственных переменных и ( , ):
( 5.2.2 )
Тогда базисное решение (допустимый план) будет иметь вид:
, а , , , .
Затем симплекс-метод используется для минимизации функции . Функция называется искусственной целевой функцией.
Этап I задачи состоит в минимизации функции . Конечно, сначала надо выразить через небазисные переменные, а именно :
. На этом этапе с функцией проводятся те же действия, что и с ограничениями. В результате получим, что при . При этом ограничения ( 5.2.2 ) равносильны исходным ограничениям ( 5.2.1 ). Решение, минимизирующее функцию , может быть использовано как начальное базисное решение для функции на II этапе. После того, как функция , игнорируем её и искусственные переменные. Преобразования по методу Жордана-Гаусса на этапе I приведены ниже (здесь мы приводим полные симплекс-таблицы) (табл. 5.1)
Таблица 5.1
Базисные переменные |
Значения |
|
|
|
|
|
|
|
|
|
10 |
1 |
0 |
–1 |
0 |
0 |
0 |
1 |
0 |
|
5 |
0 |
1 |
0 |
–1 |
0 |
0 |
0 |
1 |
|
20 |
1 |
1 |
0 |
0 |
1 |
0 |
0 |
0 |
|
20 |
–1 |
4 |
0 |
0 |
0 |
1 |
0 |
0 |
|
0 |
3 |
4 |
0 |
0 |
0 |
0 |
0 |
0 |
|
15 |
1 |
1 |
–1 |
–1 |
0 |
0 |
0 |
0 |
|
|
|
|
|
|
|
|
|
|
|
10 |
1 |
0 |
–1 |
0 |
0 |
0 |
1 |
0 |
|
5 |
0 |
1 |
0 |
–1 |
0 |
0 |
0 |
1 |
|
10 |
0 |
1 |
1 |
0 |
1 |
0 |
–1 |
0 |
|
30 |
0 |
4 |
–1 |
0 |
0 |
1 |
1 |
0 |
|
–30 |
0 |
4 |
3 |
0 |
0 |
0 |
–3 |
0 |
|
5 |
0 |
1 |
0 |
–1 |
0 |
0 |
–1 |
0 |
|
|
|
|
|
|
|
|
|
|
|
10 |
1 |
0 |
–1 |
0 |
0 |
0 |
1 |
0 |
|
5 |
0 |
1 |
0 |
–1 |
0 |
0 |
0 |
1 |
|
5 |
0 |
0 |
1 |
1 |
1 |
0 |
–1 |
–1 |
|
10 |
0 |
0 |
–1 |
0 |
0 |
1 |
1 |
–4 |
|
–50 |
0 |
0 |
3 |
4 |
0 |
0 |
–3 |
–4 |
|
0 |
0 |
0 |
0 |
0 |
0 |
0 |
–1 |
–1 |
Теперь можно минимизировать функцию . Начальное опорное решение имеет вид .Решая эту задачу, получаем , , , , .
Так как и , то ограничения, в которые эти переменные входят, превращаются в строгие неравенства.