АкушерствоАнатомияАнестезиологияВакцинопрофилактикаВалеологияВетеринарияГигиенаЗаболеванияИммунологияКардиологияНеврологияНефрологияОнкологияОториноларингологияОфтальмологияПаразитологияПедиатрияПервая помощьПсихиатрияПульмонологияРеанимацияРевматологияСтоматологияТерапияТоксикологияТравматологияУрологияФармакологияФармацевтикаФизиотерапияФтизиатрияХирургияЭндокринологияЭпидемиология
|
Сущность симплекс-метода
Лечение болезни Паркинсона: применение пирибедила
Симплекс-метод может быть применен для решения любой задачи линейного программирования, однако в общем случае приходится использовать различные его модификации. Рассмотрим вначале его применение для задачи линейного программирования, удовлетворяющей следующим условиям:
а) на все переменные наложены ограничения неотрицательности, а все остальные ограничения (пусть их 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 |
|