Типы задач ЛП. 01

[Список тем] [Вступление к этой теме] страницы темы: [1] [2]

Общая задача линейного программирования

Рассмотренные выше примеры задач линейного программирования позволяют сформулировать общую задачу линейного программирования.
Дана система m линейных уравнений и неравенств с n переменными
а₁₁ х₁ + а₁₂ х₂+...+ а_1n х_n <= b₁а₂₁ х₁ + а₂₂ х₂+...+ а_2n х_n <= b₂
...
а_k1 х₁ + а_k2 х₂+...+ а_kn х_n <= b_k
а_k+1,1 х₁ + а_k+1,2 х₂+...+ а_k+1,n х_n = b_k+1 а_k+2,1 х₁ + а_k+2,2 х₂+...+ а_k+2,n х_n = b_k+2
...
а_m1 х₁ + а_m2 х₂+...+ а_mn х_n = b_m                (1.20)
и линейная функция
F = c₁x₁+ c₂x₂ +...+ c_nx_n        (1.21)
Необходимо найти такое решение системы Х= (x₁, x₂, ..., x_j,... x_n), где
x_j>=0 (j=1,2,..., l; l <=n).        (1.22)
при котором линейная функция F   (1.21) принимает оптимальное (т.е. максимальное или минимальное) значение.
Система (1.20) называется системой ограничений, а функция F - линейной функцией, линейной формой, целевой функцией или функцией цели.
Оптимальным решением (или оптимальным планом) задачи линейного программирования называется решение Х= (x₁, x₂, ..., x_j, ... x_n)системы ограничений (1.20), удовлетворяющее условию (1.22), при котором линейная функция (1.21) принимает оптимальное (максимальное или минимальное) значение.
Термины "решение" и "план" - синонимы, однако первый используется чаше, когда речь идет о формальной стороне задачи (ее математическом решении), а второй - о содержательной стороне (экономической интерпретации).

Определение

Решение задачи может быть допустимым, только если все переменные - неотрицательны (x_j >= 0, j=1,2,...,n),.
При условии, что система ограничений (1.20) состоит лишь из одних неравенств, - такая задача линейного программирования называется стандартной;
если система ограничений состоит из одних уравнений, то задача называется канонической;
если система ограничений включает и уравнения и неравенства, то задача называется общей.

Определение
Решение задачи может быть допустимым, только если все переменные - неотрицательны (x_j >= 0, j=1,2,...,n),. При условии, что система ограничений (1.20) состоит лишь из одних неравенств, - такая задача линейного программирования называется *стандартной;* если система ограничений состоит из одних уравнений, то задача называется *канонической;* если система ограничений включает и уравнения и неравенства, то задача называется *общей.*

Так, в приведенных выше примерах задач линейного программирования задачи 1 и 2 - стандартные, задача 4 - каноническая, а задача 3 - общая.
Любая задача линейного программирования может быть сведена к канонической, стандартной или общей задаче.

Теорема 1.1

Всякому решению (а₁, а₂,..., а_n ) неравенства
a_i1 х₁+а_i2 х₂+...+а_in х_n<= b_i                (1.23)
соответствует определенное решение (а₁, а₂,..., а_n , а_n+i) уравнения
a_i1 х₁+а_i2 х₂+...+а_in х_n+ х_n+i = b_i                   (1.24)
в котором х_n+i>= 0                   (1.25)
и, наоборот, каждому решению (а₁, а₂,..., а_n , а_n+i) уравнения (1.24) и неравенства (1.25) соответствует определенное решение (а₁, а₂,..., а_n ) неравенства (1.23).

Используя эту теорему (которую принимаем без доказательства), представим в качестве примера стандартную задачу (1.4)- (1.6) в каноническом виде. С этой целью в каждое из т неравенств системы ограничений (1.4) введем выравнивающие неотрицательные переменные х_n+1, х_n+2, ..., х_n+m и система ограничений (1.4) примет вид:
а₁₁ х₁+а₁₂ х₂+...+а_1n х_n + х_n+1                  = b₁а₂₁ х₁+а₂₂ х₂+...+а_2n х_n          + х_n+2           = b₂
...
а_m1 х₁+а_m2 х₂+...+а_mn х_n                  + х_n+m = b_m                (1.26)
Таким образом, стандартная задача (1.4)-(1.6) в канонической форме: найти такое решение Х= (x₁, x₂, ..., x_n,x_n+1,... x_n+m),удовлетворяющее системе (1.26) и условию (1.5), при котором функция (1.6) принимает максимальное значение.

Теорема 1.1
Всякому решению (а₁, а₂,..., а_n ) неравенства a_i1 х₁+а_i2 х₂+...+а_in х_n<= b_i (1.23) соответствует определенное решение (а₁, а₂,..., а_n , а_n+i) уравнения a_i1 х₁+а_i2 х₂+...+а_in х_n+ х_n+i = b_i (1.24) в котором х_n+i>= 0 (1.25) и, наоборот, каждому решению (а₁, а₂,..., а_n , а_n+i) уравнения (1.24) и неравенства (1.25) соответствует определенное решение (а₁, а₂,..., а_n ) неравенства (1.23).

Замечание

В рассматриваемой задаче все неравенства вида "<=", поэтому выравнивающие неотрицательные переменные вводились со знаком "+".
В случае неравенства вида ">=", как, например, в задаче (1.10) - (1.12), соответствующие дополнительные переменные следовало бы ввести со знаком "-".

Замечание
В рассматриваемой задаче все неравенства вида "<=", поэтому выравнивающие неотрицательные переменные вводились со знаком "+". В случае неравенства вида ">=", как, например, в задаче (1.10) - (1.12), соответствующие дополнительные переменные следовало бы ввести со знаком "-".

[Список тем] [Вступление к этой теме] страницы темы: [1] [2]

[В начало страницы]