АкушерствоАнатомияАнестезиологияВакцинопрофилактикаВалеологияВетеринарияГигиенаЗаболеванияИммунологияКардиологияНеврологияНефрологияОнкологияОториноларингологияОфтальмологияПаразитологияПедиатрияПервая помощьПсихиатрияПульмонологияРеанимацияРевматологияСтоматологияТерапияТоксикологияТравматологияУрологияФармакологияФармацевтикаФизиотерапияФтизиатрияХирургияЭндокринологияЭпидемиология

Сущность симплекс-метода

Прочитайте:
  1. Антротомия, сущность операции, показания (относительные, абсолютные), первичный шов. Послеоперационное лечение.
  2. В чем сущность оздоровительного эффекта плавания?
  3. Глава 1. Понятие и сущность информации и информационных ресурсов
  4. Глава 1. Понятие и сущность медицинской услуги
  5. Данные патологоанатомического исследования и сущность болезни
  6. Климат и погода. Понятие Медицинская оценка погоды. Метеотропные заболевания. Профилактика. Акклиматизация. Физиологическая сущность. Фазы.
  7. Н.И. Пирогов и сущность его открытий в анатомии человека.
  8. Н.И. Пирогов. Сущность его открытий в анатомии и методов изучения топографической анатомии.
  9. ОПРЕДЕЛЕНИЕ (ФИЗИЧЕСКАЯ СУЩНОСТЬ) ЕДИНИЦ ИЗМЕРЕНИЯ ИОНИЗИРУЮЩИХ ИЗЛУЧЕНИЙ
  10. Организм человека и внешняя среда: сущность, принципы, результаты, проявления взаимодействия: методы их обнаружения.

Лечение болезни Паркинсона: применение пирибедила

 

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

а) на все переменные наложены ограничения неотрицательности, а все остальные ограничения (пусть их m) представляют собой уравнения;

б) свободные члены ограничений неотрицательны;

в) среди векторных коэффициентов имеется полный набор линейно независимых векторов, который представляет собой m единичных столбцов.

 

Отметим, что задача, удовлетворяющая первому условию, представляет собой задачу линейного программирования в канонической форме. Любая задача линейного программирования в смешанной форме (т.е. в общем виде) может быть к ней приведена (см. раздел 1.4.1).

Что касается двух других условий, то в ряде частных случаев (но отнюдь не всегда) можно добиться их выполнения, умножив или разделив обе части ограничения на одно и то же число. Так, если свободный член в ограничении отрицателен, можно умножить обе части уравнения на -1. Если после этого одного из единичных векторов не хватает, но в соответствующем ограничении присутствует с некоторым положительным коэффициентом переменная, которая в другие ограничения не входит, то обе части этого ограничения можно разделить на данный коэффициент. Например, если одно из ограничений имеет вид -4х1 - 6х2 + 2х3 - 2х4 = -10, и, например, переменная х4 в других ограничениях не встречается, то разделив обе части на -2, можно получить 2х1 + 3х2 - х3 + х4 = 5. В полученном уравнении свободный член неотрицателен, и векторный коэффициент при х4 является единичным.

 

Задачу, удовлетворяющую перечисленным условиям, можно записать в общем виде следующим образом (для задачи на максимум):

Разумеется, единичные вектора не обязательно должны стоять при первых m переменных. Однако переменные всегда можно обозначить по-другому, перенумеровать, поэтому запись (14) все-таки можно считать общей.

 

Опорный план построим следующим образом: базисные переменные (в (14) это первые m переменных) примем равными соответствующим элементам столбца свободных членов, а небазисные - равными нулю. Таким образом, исходный опорный план Х = (b1, b2,... bm, ). Такой план, очевидно, является допустимым, что легко проверить, подставив его в систему ограничений:

b1 + 0 = b1

b2 + 0 = b2

bm + 0 = bm

b1-m ³ 0; 0 ³ 0

 

Векторные коэффициенты при его ненулевых компонентах b1-m представляют собой линейно независимые единичные столбцы; т.е. этот план действительно опорный. Далее применение симплекс-метода рассмотрим на примере.



Дата добавления: 2015-01-18 | Просмотры: 624 | Нарушение авторских прав



1 | 2 | 3 |



При использовании материала ссылка на сайт medlec.org обязательна! (0.003 сек.)