многопродуктовая некорректная задача оптимизации

[zlobozavr]

Доброго времени суток.

Есть такая задача:

Есть k продуктов. Для их производства требуется n видов сырья.
1. количество i-го $\[(i = \overline {1,n} )\]$ сырья, необходимое для производства единичного количества продукта, равно $a_i_j\in \left\{ $a_i_j_1, $a_i_j_2\}, $\[(j = \overline {1,k} )\]$, где $a_i_j\in \left\{ $a_i_j_1, $a_i_j_2\} есть отрезок, в пределах которого приемлима вариация используемого количества i-го сырья для производства единичного количества продукта $\[P_j \]$;
2. остатки i-го сырья на предприятии равны $\[b_i \] $;
3. стоимость единичного количества i-го сырья равна $\[c_i \]$;
4. количество денежных средств, которое предприятие может затратить на закупку дополнительных объемов сырья, равно M.
Нужно определить, какие виды сырья и в каком количестве следует закупить предприятию, чтобы обеспечить максимальный объем производства продуктов.

Ясно, что задача является некорректной. Интуитивно, есть мысль попробовать начать с двойственной к ней задаче, хотя и не уверен,что это даст. Может кто-нибудь сталкивался с подобным? В каком направлении вообще здесь копать? Спасибо.

[Yu_K]

А в чем некорректность по Вашему?

[zlobozavr]

Количество сырья варьируется - исходные данные заданы не точно.

[Alexey1]

Вы же понимаете, что для разных коэффициентов $a_{ij}$ могут быть различные оптимальные решения. В каком смысле надо решить задачу? Можете попробовать начать с некоторых коэффициентов $a_{ij}$, найти оптимальное решение, а потом посмотреть, при каких изменениях этих коэффициетов найденное решение остаётся оптимальным.

[Yu_K]

Я бы просто добавил эти ограничения на кол-во сырья в математическую постановку задачи и пусть они себе варьируются - кол-во уравнений возрастет и все.

[zlobozavr]

Спасибо за советы, попробую. А что по по поводу целевой функции (максимизировать объем производства продуктов), ведь её аналитическое выражение неизвестно и она входит также и в ограничения задачи..

[Yu_K]

Каким образом входит? Попробуйте математическую постановку написать.

[zlobozavr]

$$\begin{gathered} w(x) = \sum\limits_{j = 1}^k {v_j } \to \max \hfill \\ \sum\limits_{j = 1}^k {a_{ij} v_j } - x_i \leqslant b_i ,\forall i = \overline {1,n} \hfill \\ \sum\limits_{i = 1}^n {c_i x_i } = M \hfill \\ x_i \geqslant 0,i = \overline {1,n} \hfill \\ \end{gathered} $ $ где $v_j $ - объем производства j-го продукта.

[Евгений Машеров]

0. Обычно слово "некорректная задача" понимается в существенно ином смысле. В смысле сильного изменения решения при малых возмущениях данных. То есть когда говорят "некорректная", подразумевают "не являющаяся корректной по Адамару".
1. Легко видеть, что если все нормы расхода сырья для получения продукта положительны, то максимальный выход достигается при минимальной норме расхода. Возможно, речь идёт о "мероприятиях по снижению расходов", и тогда можно указать, что снизить с... до... можно, причём это обойдётся в №№№ рублей на единицу удельного расхода?
2. Объём производства продуктов. Что максимизируется? Сумма натуральных объёмов выпуска по всем продуктам, сумма стоимостей их, сумма прибыли? Или тут многокритериалка, и вообще Парето нужно?
4. Ну и, если бы я столкнулся с подобным в реале, вероятно, начал бы с решения при определённых значениях расхода материалов на единицу продукции (скажем, при средних реальных), а потом исследовал бы на зависимость от изменений норм расхода, это любой пакет ЛП умеет.

[zlobozavr]

Спасибо за ответ.

Нет, речь о "мероприятиях по снижению расходов" не идет. Максимизируется сумма натуральных объёмов выпуска по всем продуктам.

[Yu_K]

Что-то потеряли свои интервалы в постановке. Что такое $x_i$ ? Попробуйте ввести в рассмотрение неизвестные величины вида $A_{i,j}$ такие что $a_{i,j1}\leq A_{i,j}\leq a_{i,j2}$. Задача получится нелинейная - если я ее правильно понял - посмотрите сколько будет варьируемых переменных.

[zlobozavr]

Да, интервалы пока еще не учел, так как еще не определился с тем как их учитывать.

$x_i $ - то, что требуется найти: в каком количестве нужно закупить i-ое сырьё.

А что это даст, если ввести в рассмотрение неизвестные величины $a_{ij1} \leqslant A_{ij} \leqslant a_{ij2} $?

[Yu_K]

Это даст возможность учесть требование 1 Вашей задачи. $A_{i,j}$ должны как-то войти в Ваши уравнения, а некоторые величины должны оттуда уйти - особенно те, которых нет в условии задачи.

[zlobozavr]

А которые по Вашему должны оттуда уйти, которых нет в условии задачи?

[Yu_K]

Конкретных значений в условии нет для $a_{i,j}$ - есть только интервал.