2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".

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

Не ищите на этом форуме халяву, правила запрещают участникам публиковать готовые решения стандартных учебных задач. Автор вопроса обязан привести свои попытки решения и указать конкретные затруднения.

Обязательно просмотрите тему Правила данного раздела, иначе Ваша тема может быть удалена или перемещена в Карантин, а Вы так и не узнаете, почему.



Начать новую тему Ответить на тему На страницу 1, 2, 3  След.
 
 Задача по математическому программированию
Сообщение30.05.2015, 17:16 


24/02/15
49
Прошу подсказать, как для данной задачи построить математическую модель, каким методом её можно решить?
Цитата:
Техническим заданием определен набор функций создаваемой информационной системы (ИС) $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;
д) требуется выяснить, при какой скидке в цене невошедший ПП будет включен в систему.

Изображение

 Профиль  
                  
 
 Posted automatically
Сообщение30.05.2015, 17:44 
Супермодератор
Аватара пользователя


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

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

 Профиль  
                  
 
 Posted automatically
Сообщение30.05.2015, 19:55 
Супермодератор
Аватара пользователя


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

 Профиль  
                  
 
 Re: Задача по математическому программированию
Сообщение30.05.2015, 20:23 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Задача по математическому программированию
Сообщение31.05.2015, 18:26 


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

Целевая функция
$\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$ // как это условие записать в должном виде?

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

 Профиль  
                  
 
 Re: Задача по математическому программированию
Сообщение31.05.2015, 19:28 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Задача по математическому программированию
Сообщение31.05.2015, 19:48 


17/10/08

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

 Профиль  
                  
 
 Re: Задача по математическому программированию
Сообщение02.06.2015, 13:53 


24/02/15
49
Спасибо за ответы.
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$

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

 Профиль  
                  
 
 Re: Задача по математическому программированию
Сообщение02.06.2015, 14:03 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Задача по математическому программированию
Сообщение02.06.2015, 14:33 


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

 Профиль  
                  
 
 Re: Задача по математическому программированию
Сообщение02.06.2015, 14:52 
Заслуженный участник


16/02/13
4183
Владивосток
Этим условиям нулевое решение тоже удовлетворяет.

 Профиль  
                  
 
 Re: Задача по математическому программированию
Сообщение02.06.2015, 14:59 


24/02/15
49
Ой, строгие неравенства. Исправил.

 Профиль  
                  
 
 Re: Задача по математическому программированию
Сообщение02.06.2015, 15:20 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Задача по математическому программированию
Сообщение02.06.2015, 16:03 


24/02/15
49
iifat в сообщении #1022784 писал(а):
Ну, значит, $x_{12}=1$, прочие нули.

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

 Профиль  
                  
 
 Re: Задача по математическому программированию
Сообщение02.06.2015, 16:13 
Заслуженный участник


16/02/13
4183
Владивосток
iifat в сообщении #1022784 писал(а):
Вчитайтесь в задание. Выделите текстовое условие. Потом попробуйте записать его в виде уравнений и неравенств


-- 03.06.2015, 00:14 --

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 37 ]  На страницу 1, 2, 3  След.

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group