Эмиссия газов от очистных сооружений канализации: В последние годы внимание мирового сообщества сосредоточено на экологических проблемах...
Биохимия спиртового брожения: Основу технологии получения пива составляет спиртовое брожение, - при котором сахар превращается...
Топ:
Характеристика АТП и сварочно-жестяницкого участка: Транспорт в настоящее время является одной из важнейших отраслей народного хозяйства...
Организация стока поверхностных вод: Наибольшее количество влаги на земном шаре испаряется с поверхности морей и океанов...
Интересное:
Мероприятия для защиты от морозного пучения грунтов: Инженерная защита от морозного (криогенного) пучения грунтов необходима для легких малоэтажных зданий и других сооружений...
Берегоукрепление оползневых склонов: На прибрежных склонах основной причиной развития оползневых процессов является подмыв водами рек естественных склонов...
Влияние предпринимательской среды на эффективное функционирование предприятия: Предпринимательская среда – это совокупность внешних и внутренних факторов, оказывающих влияние на функционирование фирмы...
Дисциплины:
2017-12-12 | 184 |
5.00
из
|
Заказать работу |
|
|
Общая задача линейного программирования (ЛП) формулируется, как задача об оптимизации (максимизации или минимизации) линейной функции нескольких переменных при наличии ограничений на эти переменные в виде линейных равенств или неравенств или и того и другого (ограничения на знаки переменных обычно выделяются отдельно). Математически это выглядит следующим образом:
f (X) = c j x j max(min)
a11x1 + a12x2 +…+ a1nxn b1
a21x1 + a22x2 +…+ a2nxn b2
………………………… (1)
am1x1 + am2x2 +…+ amnxn = bm
x 1 0, x 2 0, …, x l 0 (l n).
Основная задача ЛП имеет вид:
f (X)= CX min
AX=B (2)
X O.
Задача (2) записана в матричной форме:
· матрица C = (c 1 ,c 2, …,c n) – матрица цен,
· матрица A – матрица из коэффициентов, стоящих перед неизвестными,
· матрица X = (x1,x2,…,xn)т – вектор неизвестных,
· матрица B = (b1,b2,…, bm)т – вектор свободных членов.
Отличительные особенности основной задачи – это всегда задача на минимизацию целевой функции, в этой задаче все ограничения имеют вид равенств и все неизвестные – неотрицательны.
Путем изменения знака целевой функции и добавления новых неизвестных общая задача (1) всегда может быть преобразована к основной задаче (2), пример преобразования будет приведен ниже.
Каноническая задача ЛП имеет вид:
f(X) = c0 - cjxj min
a11x1+a12x2+ … +a1kxk+xk+1=b1
a21x1+a22x2+ … +a2kxk+xk+2=b2
…………………………. (3)
ar1x1+ar2x2+ … +arkxk+xk+r=br
x1 0, x2 0, …, xn 0
(k+r=n, bj 0, j=1,2,…,r)
Здесь все свободные члены b1, b2, …, br неотрицательны.
Переменные x1,x2, …,xk называются свободными переменными, а переменные xk+1,xk+2, …,xn называются базисными переменными.
Отличительной особенностью канонической задачи по сравнению с основной задачей является то, что в ней целевая функция выражена только через свободные переменные, базисные переменные присутствуют в каждом уравнении только по одному, все свободные члены неотрицательны.
|
Основная задача (2) не всегда может быть приведена к каноническому виду (3). Пример приведения основной задачи к каноническому виду также приведен ниже.
Пример. Нижеследующую общую задачу ЛП привести к основной задаче, а затем, получившуюся основную задачу ЛП привести к канонической задаче:
f(X) = 2x1 + 3x2 max
x1 – x2 -3
- 4x1 + 6x2 -5 (*)
x1 0
Эта задача отличается от основной задачи тем, что, во-первых, целевая функция максимизируется, а не минимизируется, как в основной задаче, во-вторых, ограничения задачи имеют вид неравенств, а должны быть равенства и, в третьих, неотрицательна только одна переменная, x1, вторая же переменная, x2, может принимать значения любого знака. Поэтому преобразуем эту задачу следующим образом: 1) вместо целевой функции
f (X) введем функцию f*(X) = - f (X) = - 2x1 – 3x2 min; 2) для преобразования неравенств (*) в равенства введем две новых неотрицательных переменных x3 и x4 так, чтобы они удовлетворяли уравнениям
x1 – x2 + x3 = -3
4x1 – 6x2 + x4 = 5
(здесь, во втором из неравенств (*) мы предварительно поменяли знак неравенства на противоположный); 3) наконец, вместо переменной x2 введем две новых неотрицательных переменных x5 и x6: x2 = x5 – x6. В результате, задача (*) приводится к виду:
f*(X) = -2x1 – 3x5 + 3x6 min
x1 – x5 +x6 + x3 = -3
4x1 – 6x5 + 6x6 + x4 = 5 (**)
x1 0, x3 0,x4 0,x5 0, x6 0.
Задача (**) является основной задачей ЛП. Преобразуем теперь задачу (**) к каноническому виду. Для этого поменяем знак в первом из уравнений на противоположный и добавим в получившемся уравнении в левую часть новую переменную x7 0. Тогда получим задачу:
f*(X) = -2x1 – 3x5 + 3x6 min
-x1 + x5 – x6 – x3 + x7 = 3
4x1 – 6x5 + 6x6 +x4 = 5
x1 0, x3 0, x4 0, x5 0, x6 0, x7 0.
Здесь переменные x4, x7 являются базисными, а остальные переменные – свободными. Задача является канонической.
|
|
Автоматическое растормаживание колес: Тормозные устройства колес предназначены для уменьшения длины пробега и улучшения маневрирования ВС при...
Архитектура электронного правительства: Единая архитектура – это методологический подход при создании системы управления государства, который строится...
Таксономические единицы (категории) растений: Каждая система классификации состоит из определённых соподчиненных друг другу...
Типы оградительных сооружений в морском порту: По расположению оградительных сооружений в плане различают волноломы, обе оконечности...
© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!