42 Простейшие св-ва задач линейного программирования.

Рассмотрим математическую постановку задачи, в которой функции f(x) и f₁(x) являются линейными.

(1) f(X)= 𝛾_j X_j + 𝛾₀ , при условии, что

(2) a_ij X_j ≤ b_i, i ∈ I ⊂ M=(1, 2, …, m),

(3) a_ij X_j = b_i, i ∈ M \ I

(4) X_j ≥ 0, j∈J⊂N=(1, 2, …, n)

Задача (1)-(4) называется общей задачей линейного программирования; функция f(x) – целевой функцией или функцией качества; система линейных неравенств (2) и линейных уравнений (3) – системой ограничения, а неравенства (4) – условием неотрицательности переменных.

1. Оптимальное решение задачи линейного программирования не изменится, если целевую функцию помножить на любое положительное число, либо прибавить к целевой функции любое число. Док-во можно продемонстрировать. Использую графический метод решения лин програм-ия:

Проведем через это множество прямую линию L перпендикулярно вектору градиента Г=(1, -2), те вектору координаты которого равны соответствующим частным производным функции f(X1, X2). Линия L задается уравнением: X1-2X2+ƴ0, где величина ƴ0 пропорциональна расстоянию от линии L до начала координат. Перемещая линию L в направлении, противоположном вектору градиента, приводим ее в положение, когда она становится касательной(опорной) к множеству W в точке X⁰ , 1) = W ∩ L. При этом абсолютная величина указанного расстояния увеличивается, а значение функции f (X1, X2) уменьшается, принимая в точке X⁰ наименьшее значение на множестве W. Таким образом, точка X⁰ , координат которой находятся из решения системы из двух уравнений: (верхние иксы в квадратах, в формуле не прописывается) является точкой глобального минимума функции f(X1, X2) на множестве W.

2. Рассмотрим общую задачу линейного программирования:

(1) f(X)= 𝛾_j X_j + 𝛾₀ (max),

(2) a_ij X_j ≤ b_i, I ∈ I ⊂ M=(1, 2, …, m),

(3) a_ij X_j = b_i, I ∈ I \ M=(1, 2, …, m),

(4) X_j ≥ 0, j∈J⊂N=(1, 2, …, n)

Умножив целевую функцию (1) на (-1), рассмотрим новую задачу:

1. F₁(X)= 𝛾_j X_j - 𝛾₀ =- f (X) (min)

2. a_ij X_j ≤ b_i, I ∈ I ⊂ M=(1, 2, …, m),

(3) a_ij X_j = b_i, I ∈ I \ M=(1, 2, …, m),

(4) X_j ≥ 0, j∈J⊂N=(1, 2, …, n)

Вектор α⁰ является оптимальным решением задачи (1)-(4) на максимум тогда и только тогда, когда α⁰ является оптимальным решением задачи (1)-(4) на минимум.

Док-во: Необходимость.

Пусть W есть множество допустимых решений задачи (1)-(4) и задачи (1)-(4), а вектор α⁰ является оптимальным решением задачи α⁰ на максимум. Тогда, по определению глобального максимума, выполняется неравенство f(α⁰)  ≥ f( α⁰) для любого вектора α ∈ W. Умножив последнее неравенство на минус единицу, получим новое неравенство -f(α⁰)  ≤ -f( α⁰) для любого вектора α ∈ W. Откуда, по определению глобального минимума функции f1(X), вектор α⁰ является оптимальным решением задачи (1)-(4) на минимум. Т. о. , необходимость доказана. Для доказательства достаточности следует провести рассуждения в обратной последовательности.