Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

Метод искусственного базиса




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

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

, , и , .

Алгоритм метода искусственного базиса:

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

.

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

2. В целевую функцию эти искусственные переменные в задаче на максимум вводятся с коэффициентом , а в задаче на минимум с коэффициентом , где - число намного большее единицы.

3. Записывается новая целевая функция:

,

.

После подстановки выражений искусственных переменных из системы ограничений в выражения для и приведения подобных выражения новой целевой функции могут быть записаны в виде:

,

.

4. В симплексную таблицу целевая функция записывается в виде двух строк и . Для задачи на максимум в строку для записываются коэффициенты , в строку для коэффициенты .

5. При переходе искусственных переменных из числа базисных в число свободных столбцы, соответствующие этим искусственным переменным в каждой последующей симплексной таблице вычеркиваются.

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

7. Разрешающая строка определяется как в обычном симплексном методе.

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

9. Дальше задача решается обычным симплексным методом.

Пример 9. Решить задачу линейного программирования методом искусственного базиса:

,

, , .

Решение.

1. Задача приведена к каноническому виду. Для системы ограничений соответствует матрица: . Как видно из матрицы система ограничений не приведена к допустимому виду.

2. Введем искусственные переменные в систему ограничений:

.

3. Запишем новую целевую функцию:

.

Приведем подобные и запишем:

.

4. Составим симплексную таблицу. Так как в последней строке все положительные элементы одинаковые, выберем любой, например, первый. Тогда столбец разрешающий. Оценки для первой и третьей строки одинаковые, поэтому в качестве разрешающей возьмем любую, например, первую. Тогда - разрешающий элемент.

 

  -1   -1          
-1                  
    -1            
    -2              
                   

Выполним действия: , , , . При этом искусственная переменная становится свободной, а - базисной. Столбец искусственной переменной в новой таблице можно исключить.

  -1   -1          
      -1        
    -3          
    -5         -6  
                 

Выполним действия: , , . При этом искусственная переменная становится свободной, а - базисной. Столбец искусственной переменной в новой таблице можно исключить.

  -1   -1      
  -2   -4      
    -3         -
    -2       -6  
  -2   -4        

Разделим вторую строку на , чтобы разрешающий элемент был равен единице. После деления на выполним действия: , , , . При этом искусственная переменная становится свободной, а - базисной. Столбец искусственной переменной в новой таблице можно исключить.

  -2/3   -1/3      
  -1/3   -2/3      
             
  7/3   5/3   -4  
             

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

4. Дальше применяем обычный симплексный метод. Выполним действия: , , . Переменная становится свободной, а - базисной.

      1/3 2/3    
      -1/3 1/3    
             
      -2/3 -7/3 -11  

В последней строке коэффициенты при свободных переменных и отрицательные, следовательно, оптимальное решение найдено: и .

Пример 10. Решить задачу линейного программирования методом искусственного базиса:

, , , .

Решение.

1. Приведем задачу к каноническому виду. Введем балансовые переменные: .

2. Балансовые переменные и могут быть выбраны в качестве базисных. Переменная не совпадает по знаку со свободным членом.

3. Введем в первое уравнение искусственную переменную:

.

4. Запишем новую целевую функцию:

или

.

5. Составим симплексную таблицу. В последней строке наибольший положительный элемент находится в первом столбце. Столбец разрешающий. В разрешающем столбце положительный элемент есть только в первой строке, поэтому оценки находить не надо. Первая строка – разрешающая.

      -1          
-1                
-3                
  -1 -2            
      -1          

Разделим первую строку на , чтобы разрешающий элемент был равен единице. После деления на выполним действия: , , , , . При этом искусственная переменная становится свободной, а - базисной. Столбец искусственной переменной в новой таблице можно исключить.

    1/2 -1/2        
    3/2 -1/2        
    5/2 -3/2        
  -1 -5/2 1/2     -1  
               

Последнюю строку можно вычеркнуть. Таким образом, получено начальное допустимое решение: , .

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

Задания для решения в аудитории

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

1. , , , .

 

 

2. , , , .

 

 

Задания для самостоятельной подготовки

1. Решить задачи линейного программирования методом искусственного базиса , :

1.1. , , , .

1.2. , , , .

1.3. , , , .

1.4. , , , .

Ответы: 1.1. . 1.2. Система ограничений несовместна. 1.3. , , . 1.4. Оптимального решения нет, .

 




Поделиться с друзьями:


Дата добавления: 2015-06-27; Просмотров: 3005; Нарушение авторских прав?; Мы поможем в написании вашей работы!


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



studopedia.su - Студопедия (2013 - 2024) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление




Генерация страницы за: 0.011 сек.