Добро пожаловать, гость
:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте :: :: форум ::

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 23.03.2009, 20:56
Новичок

Отправить личное сообщение для Lda78 Посмотреть профиль Найти все сообщения от Lda78
 
Регистрация: 23.03.2009
Сообщений: 1

Симплекс метод
Помогите пожалуйста определиться с возможностью использования симплекс метода.

есть задача.
2X1+1X2+2X3+3X4+2X5+2X6+15X7+8X8+4X9+1X10+7X10+
1X11+2X12+1X13+1X14+2X15 -> max

условия
X1 <= 54
X2 <= 232
....
X15 <= 404

x1+x2+x3+x4+..+x15 <=1500 /сумма Х/

при решении задачи симплекс методом был получен результат
Х1 = 54
X2 = 0
X3 = 61
...
X15 = 0

Х = 0 - 6 шт.
Х не равных 0 - 10 шт.

Вопрос.
1. Можно ли сформулировать ограничения так что бы количество Х не равных 0, не превышало заданного /например кол-во Х не равных 0 = 6/
2. возможно ли вообще решение такой задачи с помощью симплекс метода и как, если возможно
3. если нет - то с помощью какого алгоритма /желательно ПК реализуемого/ возможно решение
  #2  
Старый 30.03.2009, 12:18
Пользователь

Отправить личное сообщение для mserg Посмотреть профиль Найти все сообщения от mserg
 
Регистрация: 29.10.2006
Сообщений: 57

Прежде всего нужно понять, что линейное программирование и симплекс-метод - это не одно и то же.

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

Если задача небольшая, то можно использовать Excel - он имеет численные методы, в том числе умеет решать небольшие частично-целочисленные линейные задачи.

Заниматься программированием не рекомендую. Более-менее работающие пакеты линейного программирования имеют исходники как минимум 1 мегабайт.
  #3  
Старый 31.03.2009, 18:24
гость

 
Сообщений: n/a

>
Сообщение от mserg Посмотреть сообщение
Прежде всего нужно понять, что линейное программирование и симплекс-метод - это не одно и то же.

"...Спустя десять лет американский математик Дж. Данциг разработал эффективный метод решения данного класса задач — симплекс-метод. Общая идея симплексного метода (метода последовательного улучшения плана) для решения ЗЛП состоит в следующем:.."

>Заниматься программированием не рекомендую. Более-менее работающие пакеты линейного программирования имеют исходники как минимум 1 мегабайт.
данная задача решена на Дельфи с использованием исходников данного сайта. В принципе вопрос и состояит в том: пытаться ли приспособить то что сделано или данная задача не разрешима таким способом.....

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

вопрос в этом и состоит....как ввести данные переменные в код программы и возможно ли это вообще ?!
  #4  
Старый 31.03.2009, 21:58
Пользователь

Отправить личное сообщение для mserg Посмотреть профиль Найти все сообщения от mserg
 
Регистрация: 29.10.2006
Сообщений: 57

Да, можно "линеаризовать" указанные выше условия. Но для этого требуется немного пошевелить мозгами (Вам, а не мне, разумеется) .
После решения симплекс-методом задачи может оказаться, что некоторые из целочисленных переменных вовсе даже не целые. Для борьбы с этим зловредным явлением используется метод ветвей и границ.

Самописная хрень, конечно, может работать на тривиальных задачах. Но стоит количеству переменных достичь ~300, или стать задаче вырожденной - все, пиши-пропало.
  #5  
Старый 15.11.2010, 19:54
гость

 
Сообщений: n/a

Сообщение от mserg Посмотреть сообщение
Да, можно "линеаризовать" указанные выше условия. Но для этого требуется немного пошевелить мозгами (Вам, а не мне, разумеется) .
После решения симплекс-методом задачи может оказаться, что некоторые из целочисленных переменных вовсе даже не целые. Для борьбы с этим зловредным явлением используется метод ветвей и границ.

Самописная хрень, конечно, может работать на тривиальных задачах. Но стоит количеству переменных достичь ~300, или стать задаче вырожденной - все, пиши-пропало.
Здесь посмотрите как решать: http://net-algoritm.blogspot.com/201...g-post_08.html
  #6  
Старый 17.11.2010, 00:20
гость

 
Сообщений: n/a

пособие для умственно отсталых?
 


Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
симплекс метод незарегистрированный Математические алгоритмы 7 03.03.2010 19:54
целочисленный симплекс-метод blizzard Реализация, исходники, языки 5 12.05.2009 13:11
симплекс таблицы гость Реализация, исходники, языки 2 12.09.2008 02:13
Симплекс-таблицы Marina Математические алгоритмы 0 19.04.2008 18:25