Главная|Решения онлайн |Теория | Основные формулы и обозначения |Обратная связь |


Линейное программирование

Математическое программирование занимается изучением экстремальных задач и поиском методов их решения. Задачи математического программирования формулируются следующим образом : найти экстремум некоторой функции многих переменных f ( x1, x2, ... , xn ) при ограничениях gi ( x1, x2, ... , xn ) * bi , где gi - функция, описывающая ограничения, * - один из следующих знаков ≥, =, ≤, а bi - действительное число, i = 1, ... , m. f называется функцией цели ( целевая функция ).

Линейное программирование - это раздел математического программирования, в котором рассматриваются методы решения экстремальных задач с линейным функционалом и линейными ограничениями, которым должны удовлетворять искомые переменные.
Задачу линейного программирования можно сформулировать так . Найти min


формулировка задачи линейного программирования

при условии :
a11 x1 + a12 x2 + . . . + a1nxn ≤ b1 ;
a21 x1 + a22 x2 + . . . + a2n xn ≤ b2 ;
. . . . . . . . . . . . . . . . . . . . . . . . . . . .
am1 x1 + am2 x2 + . . . + amn xn ≤ bm ;
x1 ≥ 0, x2 ≥ 0, . . . , xn ≥ 0 .

Эти ограничения называются условиями неотрицательности. Если все ограничения заданы в виде строгих неравенств, то данная форма называется канонической.

В матричной форме задачу линейного программирования записывают следующим образом. Найти max cT x
при условии
A x ≤ b ;
x ≥ 0 ,
где А - матрица ограничений размером (m×n), b(m×1) - вектор-столбец свободных членов, x(n×1) - вектор переменных, сТ = [c1, c2, ... , cn ] - вектор-строка коэффициентов целевой функции.
Решение х0 называется оптимальным, если для него выполняется условие сТ х0 ≥ сТ х , для всех х E R(x).
Поскольку min f(x) эквивалентен max [ - f(x) ] , то задачу линейного программирования всегда можно свести к эквивалентной задаче минимизации.

Для решения задач данного типа применяются методы:

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

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

F=a0,1x1+a0,2x2+...a0,nxn +b0 → max

a1,1x1+a1,2x2+...a1,nxn=b1

a2,1x1+a2,2x2+...a2,nxn=b2

.......................................

am,1x1+am,2x2+...am,nxn=bm

В случае если в исходной задаче необходимо найти минимум - знаки коэффициентов целевой функции F меняются на противоположные a0,n=-a0,n. Знаки коэффициентов ограничивающих условий со знаком "≥" так же меняются на противоположные. В случае если условие содержит знак "≤" - коэффициенты запишутся без изменений. К каждому ограничивающему условию, при переходе от неравенств к равенствам, добавляется дополнительная переменная xn+m. Дополнительная переменная не будет оказывать влияния на значение целевой функции и на оптимальное решение которое будет получено в результате.

Пример

Необходимо привести задачу к каноническому виду.

 F=4x1+3x2-x3 → min

5x1-2x2≥7

-6x1+2x3≤10

Изменим знаки коэффициентов целевой функции на противоположные, и перейдем тем самым к поиску max. Изменим знаки коэффициентов первого условия на противоположные т. к. это условие со знаком "≥", и добавим в него дополнительную переменную x4. Знаки второго условия оставим без изменения, добавив к нему дополнительную переменную x5.

F=-4x1-3x2+x3 → max

-5x1+2x2+x4=7

-6x1+2x3+x5=10

 



R336709263964 - WebMoney 41001419134483 - Яндекс Деньги
WebMoneyПонравился сайт? Окажите помощь в развитиияндекс