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

Математическое программирование занимается изучением экстремальных задач и поиском методов их решения. Задачи математического программирования формулируются следующим образом : найти экстремум некоторой функции многих переменных f ( x₁, x₂, … , x_n ) при ограничениях g_i ( x₁, x₂, … , x_n ) * b_i , где g_i – функция, описывающая ограничения, * – один из следующих знаков ≥, =, ≤, а b_i – действительное число, i = 1, … , m. f называется функцией цели ( целевая функция ).

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

при условии :
a₁₁ x₁ + a₁₂ x₂ + . . . + a_1nx_n ≤ b1 ;
a₂₁ x₁ + a₂₂ x₂ + . . . + a_2n x_n ≤ b₂ ;
. . . . . . . . . . . . . . . . . . . . . . . . . . . .
a_m1 x₁ + a_m2 x₂ + . . . + a_mn x_n ≤ b_m ;
x₁ ≥ 0, x₂ ≥ 0, . . . , x_n ≥ 0 .
Эти ограничения называются условиями неотрицательности. Если все ограничения заданы в виде строгих неравенств, то данная форма называется канонической.
В матричной форме задачу линейного программирования записывают следующим образом. Найти max c^T x
при условии
A x ≤ b ;
x ≥ 0 ,
где А – матрица ограничений размером (m×n), b^(m×1) – вектор-столбец свободных членов, x^(n×1) – вектор переменных, с^Т = [c₁, c₂, … , c_n ] – вектор-строка коэффициентов целевой функции.
Решение х₀ называется оптимальным, если для него выполняется условие с^Т х₀ ≥ с^Т х , для всех х E R(x).
Поскольку min f(x) эквивалентен max [ – f(x) ] , то задачу линейного программирования всегда можно свести к эквивалентной задаче минимизации.
Для решения задач данного типа применяются методы:

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

решить онлайн задачу линейного программирования методом искусственного базиса
Перед применением симплекс метода задачу необходимо привести к каноническому виду. Это означает, что все ограничивающие условия должны быть представлены в виде равенств, а целью решения задачи должен быть поиск максимума целевой функции.
F=a_0,1x₁+a_0,2x₂+…a_0,nx_n +b₀ → max
a_1,1x₁+a_1,2x₂+…a_1,nx_n=b₁
a_2,1x₁+a_2,2x₂+…a_2,nx_n=b₂
…………………………………
a_m,1x₁+a_m,2x₂+…a_m,nx_n=b_m
В случае если в исходной задаче необходимо найти минимум – знаки коэффициентов целевой функции F меняются на противоположные a_0,n=-a_0,n. Знаки коэффициентов ограничивающих условий со знаком “≥” так же меняются на противоположные. В случае если условие содержит знак “≤” – коэффициенты запишутся без изменений. К каждому ограничивающему условию, при переходе от неравенств к равенствам, добавляется дополнительная переменная x_n+m. Дополнительная переменная не будет оказывать влияния на значение целевой функции и на оптимальное решение которое будет получено в результате.
Пример
Необходимо привести задачу к каноническому виду.
F=4x₁+3x₂-x₃ → min
5x₁-2x₂≥7
-6x₁+2x₃≤10
Изменим знаки коэффициентов целевой функции на противоположные, и перейдем тем самым к поиску max. Изменим знаки коэффициентов первого условия на противоположные т. к. это условие со знаком “≥”, и добавим в него дополнительную переменную x₄. Знаки второго условия оставим без изменения, добавив к нему дополнительную переменную x₅.
F=-4x₁-3x₂+x₃ → max
-5x₁+2x₂+x₄=7
-6x₁+2x₃+x₅=10