Несовместность задачи

Рассматривается задача в стандартной форме

Здесь столбцы a^j матрицы A описывают технологические способы, элементы вектора b – запас ресурсов или обязательство (цели) по их производству.

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

Так как реальная система как то работает, то несовместность задачи показывает, что проект (модель) нуждается в доработке.

Направления совершенствования модели:

Изменяем правые части ограничений задачи:

Насколько нужно увеличить каждое b_i, чтобы задача стала разрешимой.

Вводим вектор переменных «надбавок» .

где r_i ≥ 0 – «стоимость» изменения правой части.

Важно: «стоимость» должна быть соизмеримой с исходной целевой функцией.

Пусть есть k_i способов увеличения b_i. При этом способ k может увеличить b_i не более чем на с удельными затратами . Также пусть более дешевые способы имеют меньшие номера:

Задача запишется следующим образом:

Утверждение: Если в оптимальном решении последней задачи z_i^k > 0, то
z_i^{k`</sup> = d<sub>i</sub><sup>k`} для всех k` < k (способ применяется только после того, как исчерпаны возможности более дешевых способов).

Доказательство: Пусть в оптимальном решении задачи для некоторых
k` < k имеем z<sub>i</sub><sup>k</sup> > 0, и z<sub>i</sub><sup>k`</sup> < d_i^{k`</sup>.
Тогда существует такое δ >0, что z<sub>i</sub><sup>k</sup> – δ > 0 и z<sub>i</sub><sup>k`} + δ < d_i^{k`</sup>.
Заменяя в условиях задачи z<sub>i</sub><sup>k</sup> на z<sub>i</sub><sup>k</sup> – δ, а z<sub>i</sub><sup>k`} на z_i^{k`</sup> + δ, видим, что все они выполняются.
Но при этом значение целевой функции выросло на величину δ(r<sub>i</sub><sup>k</sup> – r<sub>i</sub><sup>k`}). А это противоречит оптимальности решения.

В некотором роде рассмотренные способы изменения правых частей сводятся к задаче добавления нового технологического способа производства.

Возникает вопрос: каким условиям должен соответствовать технологический способ, добавляемый в модель с целью устранения несовместности?

Рассматривается задача P в канонической форме:

c · x → max при Ax = b, x ≥ 0.

Будем считать, что вектор b ≥ 0.

Решение данной задачи происходит с симплекс-метода, с поиска исходного БДР методом искусственного базиса: рассматривается вспомогательная задача P ₁, которая всегда разрешима:

– Σ _i t_i → max при Ax + t = b, x ≥ 0, t ≥ 0.

Пусть f ₁ – оптимальное решение задачи P ₁. | f ₁| указывает на минимальную достижимую величину «суммарного невыполнения» ограничений задачи P. Если задача P совместна, то f ₁ = 0, иначе f ₁ < 0.

Устранение несовместности задачи – введение такого технологического способа, который повысит значение f ₁ (в идеале до нуля).

Рассмотрим задачу P ₁^*, двойственную к вспомогательной:

h (y) = b · y → min при yA ≥ 0, y_i ≥ –1 для всех i.

Так как задача P ₁ разрешима, то и двойственная к ней будет иметь решение y ^* и h (y ^*) = f ₁.

Предположим, что в исходную задачу вводится новый технологический способ: переменная x ≥ 0 с коэффициентами a_i в ограничениях и c – в целевой функции. Аналогично строится вспомогательная задача P ₂.

Она будет отличаться от P ₁ введенной дополнительной переменной с теми же коэффициентами в ограничениях и нулевым коэффициентом в ЦФ.

Пусть x допустимое решение задачи P ₁, тогда решение (x, x) при x = 0 – допустимо в P ₂. Задача P ₂ совместна. Двойственная к ней P ₂^* – также разрешима.

Отличие задачи P ₂^* от задачи P ₁^* в ограничении:

Σ _i a_iy_i ≥ 0 (*).

Задачи P ₂ и P ₂^* разрешимы одновременно по первой теореме двойственности. Их целевые функции имеют одинаковые значения f ₂.

Пусть Y ₁ и Y ₂ – множества допустимых решений задач P ₁^* и P ₂^* соответственно. Поскольку любое дополнительное ограничение сужает область поиска решения, то Y ₁ Y ₂.Поэтому f ₁≤ f ₂ – чем шире области минимизации (Y ₁), тем меньше минимум.

Если решение задачи P ₁^* удовлетворяет условию (*), то оно также является допустимым решением задачи P ₂^*: y ^* Y ₂ и f ₂ = min _{Y 2} h (y) ≤ h (y ^*) = f ₁

Так как нам нужно, чтобы при добавлении способа значение целевой функции задачи P ₁ повышалось (f ₁ < f ₂), то, c учетом вышеупомянутого замечания, необходимо, чтобы условие (*) не выполнялось.

Утверждение: Для того, чтобы в несовместной задаче P с неотрицательным вектором b после введения нового технологического способа (a₁,…,a_m, c) задача стала совместной, коэффициенты a_i должны удовлетворять условию

Σ _i a_iy_i ^* < 0,

где y_i^* – двойственные оценки вспомогательной задачи P ₁.

Замечание: Указанное в утверждении условие необходимо, но, вообще говоря, недостаточно, чтобы при введении нового технологического способа задача стала совместной (потребуется введение нескольких дополнительных технологических способов).

Поиск по сайту: