Студопедия

КАТЕГОРИИ:

АстрономияБиологияГеографияДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРиторикаСоциологияСпортСтроительствоТехнологияФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника


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




При решении задач симплексным методом необходимо, чтобы модель задачи была канонической и система ограничений была приведена к единичному неотрицательному базису. Встречаются случаи, когда эти преобразования оказываются громоздкими[19].

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

,

.

Из этой задачи составим вспомогательную задачу следующим образом:

1) систему ограничений вспомогательной задачи получаем из системы ограничений исходной, добавляя в каждое ограничение, не содержащее базисную переменную, искусственную базисную переменную;

2) целевая функция равна алгебраической сумме искусственных переменных, взятых с коэффициентом (-1);

3) условие неотрицательности распространяется на все переменные, в том числе и искусственные.

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

,

.

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

= (0, 0, ¼, 0, b1, b2, ¼, bn),

при этом £ 0.

Между оптимальным решением вспомогательной задачи и опорным решением исходной задачи существует зависимость:

1) если = 0 достигается при = (l1, l2, ¼, ln, 0, 0, ¼, 0), то = (l1, l2, ¼, ln) является исходным опорным решением;

2) если max £ 0, то ограничения исходной задачи несовместны.

 


Поделиться:

Дата добавления: 2014-12-03; просмотров: 207; Мы поможем в написании вашей работы!; Нарушение авторских прав





lektsii.com - Лекции.Ком - 2014-2024 год. (0.006 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав
Главная страница Случайная страница Контакты