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

Математическое программирование занимается изучением экстремальных задач и поиском методов их решения. Задачи математического программирования формулируются следующим образом : найти экстремум некоторой функции многих переменных 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 ] — вектор-строка коэффициентов целевой функции.
Решение х называется оптимальным, если для него выполняется условие сТ х ≥ сТ х , для всех х E R(x).
Поскольку min f(x) эквивалентен max [ — f(x) ] , то задачу линейного программирования всегда можно свести к эквивалентной задаче минимизации.

Читайте также  Пример Алгоритм Флойда

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

    • графический;
    • табличный ( прямой, простой ) симплекс — метод;
    • метод искусственного базиса;
    • модифицированный симплекс — метод;
    • двойственный симплекс — метод.

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

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

Читайте также  Абсолютная медиана графа

F=a0,1x1+a0,2x2+…a0,nxn +b → 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. Дополнительная переменная не будет оказывать влияния на значение целевой функции и на оптимальное решение которое будет получено в результате.

Читайте также  Алгоритм Литтла - Пример 1

Пример

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

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

1 Звезда2 Звезды3 Звезды4 Звезды5 Звезд (Пока оценок нет)
Загрузка...