Студопедия

КАТЕГОРИИ:

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



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




Читайте также:
  1. Amp; Методичні вказівки
  2. Amp; Методичні вказівки
  3. Amp; Методичні вказівки
  4. Amp; Методичні вказівки
  5. Amp; Методичні вказівки
  6. Amp; Методичні вказівки
  7. Amp; Методичні вказівки
  8. B. Искусственная вентиляция легких. Методики проведения искусственной вентиляции легких
  9. Cтруктуры внешней памяти, методы организации индексов
  10. FDDI. Архитектура сети, метод доступа, стек протоколов.

При решении задач симплексным методом необходимо, чтобы модель задачи была канонической и система ограничений была приведена к единичному неотрицательному базису. Встречаются случаи, когда эти преобразования оказываются громоздкими[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; просмотров: 14; Нарушение авторских прав







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