Задача по математическому программированию

[Taurus]

Прошу подсказать, как для данной задачи построить математическую модель, каким методом её можно решить?

Цитата:

Техническим заданием определен набор функций создаваемой информационной системы (ИС) $R=(r_1, r_2,…,r_m)$.
Имеются программные продукты (ПП), характеризуемые стоимостью $C_j$ и предоставляемыми функциями $B_j=(b_{1j}, b_{2j},…,b_{kj})$.
Необходимо определить, какие ПП включить в систему для обеспечения всех ее функций.
Показать, как изменится решение, если
а) несовместимы ПП1 и ПП4, ПП5 и ПП10;
б) при установке ПП3 необходимы ПП7 и ПП13;
в) хотя бы один из трех пакетов (ПП5, ПП8, ПП12) должен быть установлен;
г) необходимы или ПП1 и ПП2 или ПП9;
д) требуется выяснить, при какой скидке в цене невошедший ПП будет включен в систему.

[Deggial]

Тема перемещена из форума «Помогите решить / разобраться (М)» в форум «Карантин»
Причина переноса: формулы не оформлены $\TeX$ом

Taurus
Наберите все формулы и термы $\TeX$ом.
Инструкции по оформлению формул здесь или здесь (или в этом видеоролике).
См. также тему Что такое карантин, и что нужно делать, чтобы там оказаться.
После исправлений сообщите в теме Сообщение в карантине исправлено, и тогда тема будет возвращена.

[Deggial]

Тема перемещена из форума «Карантин» в форум «Помогите решить / разобраться (М)»
Возвращено

[iifat]

На каждый пакет вводим переменную, которая принимает значения 0 (пакет не включён) либо 1 (пакет включён). Не помню, кажется, такие задачи рассматриваются отдельно, либо можно решать методами целочисленного программирования, добавив условия $x_i\leq1$

[Taurus]

В верном направлении иду? Не со всеми условиями разобрался, правда. Нужна помощь.

Целевая функция
$\min L=\sum\limits_{j=1}^{n}c_jx_j$, где $c_j$ -- стоимость продукта, $x_j$ -- (не)включаемый продукт, $n=13$

Условия
$x_j\in\{0;1\}$

Для а:
$x_1+x_4\leqslant 1$
$x_5+x_{10}\leqslant 1$

Для б:
если $x_3=1$, то $x_7+x_{13}=2$ // как это условие записать в должном виде?

Для в:
$x_5+x_8+x_{12}\geqslant 1$

Для г:
$x_1+x_2=2$ или $x_9=1$ // как это условие записать в должном виде?

Для д:
Как вообще записать это?

[iifat]

Начну с того, что, в общем-то, верной дорогой идёте. Возможно
Теперь конкретнее.
Вы так и не написали модель исходной задачи. Начните с постановки: целевая функция-то есть, но вы решаете задачу на минимум или на максимум? И где ограничения? В вашей постановке решение либо ничего не покупать, либо покупать всё, в зависимости от того, хотите вы минимума либо максимума целевой функции.
Для б и г — вот так, навскидку, я б разбил задачу на две, а потом сравнил бы полученные решения и выбрал из двух лучшее.
Для д, опять же навскидку, можно при решении симплекс-методом отслеживать моменты, кода исключаем соответствующий $x$ из решения и пересчитывать коэффициент. Крутится в голове что-то типа решить задачу, зафиксировать x в 1, добавить условие «целевая функция меньше (больше) найденного значения», в качестве целевой взять цену и максимизировать. Не уверен, что получится задача линейного программирования. Подумаю ещё.

[mserg]

б) $x_7+x_{13}\geqslant2x_3$
г) на вскидку, можно ввести доп. переменную, как в б) и затем сложить ее с $x_9$ - должно быть больше или равно 1
д) находите оптимальное решение. теперь, если нужно найти скидку на пакет, чтобы он гарантированно вошел, нужно
* потребовать, чтобы общая цена стала меньше (критерий превратится в неравенство)
* переменная включения рассматриваемого пакета зафиксируется в 1
* появится дополнительная переменная скидки
* критерий - минимизация скидки
в итого - линейная модель, решение которой даст скидку и цену

[Taurus]

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

iifat в сообщении #1021947 писал(а):

Вы так и не написали модель исходной задачи. Начните с постановки: целевая функция-то есть, но вы решаете задачу на минимум или на максимум? И где ограничения?

Полагаю надо искать сборку системы со всеми функциями (A, C, E, F, G, H, I, K) по минимальной стоимости.
$L=37x_1+18x_2+55x_3+64x_4+22x_5+30x_6+70x_7+57x_8+29x_9+48x_{10}+60x_{11}+19x_{12}+42x_{13}\to \min$

А ограничения разве не условиями реализуются?

[iifat]

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

[Taurus]

Убрать условия а-д из постановки? Понятно, что при нулевых переменных и функция будет равна нулю, и такой вариант не подходит.
Записать, что $\sum\limits_{j=1}^{n}x_j > 0$ и $< 13$?

[iifat]

Этим условиям нулевое решение тоже удовлетворяет.

[Taurus]

Ой, строгие неравенства. Исправил.

[iifat]

Ну, значит, $x_{12}=1$, прочие нули. Не гадайте. Вчитайтесь в задание. Выделите текстовое условие. Потом попробуйте записать его в виде уравнений и неравенств.

[Taurus]

iifat в сообщении #1022784 писал(а):

Ну, значит, $x_{12}=1$, прочие нули.

Ну да, это тоже не решение, но как задать условие на наличие нужных функций?

[iifat]

iifat в сообщении #1022784 писал(а):

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

-- 03.06.2015, 00:14 --

Ну хорошо, почему это не решение?