КАТЕГОРИИ:
Архитектура-(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)
Метод искусственного базиса. Часто, после приведения ОЗЛП к каноническому виду расширенная матрица системы линейных уравнений (СЛУ) не является К-матрицей (нет начального опорного плана)
|
|
|
|
Часто, после приведения ОЗЛП к каноническому виду расширенная матрица системы линейных уравнений (СЛУ) не является К-матрицей (нет начального опорного плана), и, следовательно, решать такую КЗЛП симплекс-методом нельзя. Суть метода искусственного базиса состоит в следующем: строится такая вспомогательная КЗЛП (ВКЗЛП) с заранее известным опорным планом, по решению которой либо определяется начальный опорный план исходной задачи, либо устанавливается, что ее множество планов пусто.
Дано:
, i = 1,..., m, rang (A) = m < n, bi 
0, i = 1,..., m.
Найти: К-матрицу (начальный опорный план).
Построим следующую ВКЗЛП:
, 
, i = 1,..., m, xj 0, j = 1,..., n, yi 0, i = 1,..., m, yi – искусственные переменные.
Очевидно, начальный опорный план ВКЗЛП имеет вид:
,
= (n+1, n+2,..., n+m).
Применяя симплекс-метод, находят
– решение ВКЗЛП.
Замечание: ВКЗЛП всегда разрешима, так как множество ее планов не пусто, а целевая функция ограничена.
Теорема: Если 
, то 
– начальный опорный план исходной КЗЛП. Если 
, то множество планов исходной КЗЛП пусто и, следовательно, она неразрешима.
Пример: F(X) = 5×x1 + 3×x2 + 4×x3 - x4 
x1 + 3×x2 + 2×x3 + 2×x4 = 3
2×x1 + 2×x2 + x3 + x4 = 3
.
x1 + 3×x2 + 2×x3 + 2×x4 + y1 = 3
x1 + 3×x2 + 2×x3 + 2×x4 + y2 = 3
xj0, j = 1,..., 4, y1,20.
= (5,6), 
= (3,3), 
= (-1,-1).
Таблица 1
| 
| 
| 
| 
| 
| 
| 
|  =
|
| -1 -1 | ||||||||
| -3 | -5 | -3 | -3 | F(x)=-6 | |||
| -1 | 1/3 4/3 | 2/3 -1/3 | 2/3 -1/3 | |||||
|
| -4/3 | 1/3 | 1/3 | -1 | ||||
| 3/4 -1/4 | 3/4 -1/4 | 3/4 3/4 | ||||||
|
| F(x)=0 |
Замечание:
По мере выхода искусственных переменных из базиса, вычисления в соответствующих клетках симплекс-таблицы не проводятся.
Получили оптимальный опорный план ВКЗЛП.
(3/4,3/4,0,0,0,0), , 
(3/4,3/4,0,0).
Теперь решаем симплекс-методом исходную задачу:
F(X)= 5×x1 + 3×x2 + 4×x3 - x4
x2 + 3/4×x3 + 3/4×x4 = 3/4
x1 - 1/4×x3 - 1/4×x4 = 3/4
xj0, j = 1,..., 4.
Таблица 2
| 
| 
| 
| 
| 
|  =
|
| 3/4 -1/4 | 3/4 -1/4 | 3/4 3/4 | ||||
| -3 | F(x) = 6 | ||||
| 4/3 1/3 | ||||||
|
| F(x) = 9 |
(1, 0, 1, 0), 
= 9.
|
|
|
|
Дата добавления: 2013-12-14; Просмотров: 251; Нарушение авторских прав?; Мы поможем в написании вашей работы!