Объединенный Открытый Проект - Сайт для Настоящих Компьютерщиков

Объединенный Открытый Проект

Сайт для Настоящих Компьютерщиков

; Логин:
  Пароль:
Обычный
Безопасный
Запомнить пользователя



Зарегистрироваться
Забыли пароль?
 
 
 
Объединенный Открытый Проект »   Прочее »   Форум поддержки прочих разработок »   Вопрос по симплексу
RSS

Вопрос по симплексу

вопрос по алгоритму методу

Текущий рейтинг темы: Нет

<<Назад  Вперед>>Печать
 
Bas
Новичок


Всего сообщений: 2
Рейтинг пользователя: 0





Дата регистрации на форуме:
19 мая 2005
1)В коде Вы производите расчет маргиналов: от дельты отымая коефициенты целевой функции
Delta[j]:=0;
for i:=0 to M-1 do Delta[j]:=Delta[j]+Cons[i].A[j]*C[Basis[i]];
Delta[j]:=Delta[j]-C[j];
а вот для решения задачи
5X + 7Y -> MAX
2X + 4Y <= 100
3X + 3Y <= 90
X,Y >= 0
результат (10,20) будет получен только если
Delta[j]:=C[j]-Delta[j];
и в теории рылся - тоже вроде так выглядит
поправте меня, возможно я ошибаюсь?
2)Можно не пользоваться целочисленным методом?
Заранее благодарен.
4X_Pro
Руководитель Проекта
Настоящий Компьютерщик
4X_Pro
Откуда: Москва
Всего сообщений: 2994
Рейтинг пользователя: 79





Дата регистрации на форуме:
29 сен. 2001
1) Возможно, это и есть та самая причина, по которой симплекс зацикливается (тут про это уже пару раз писали). Я на всякий случай проверю еще раз и если это действительно так, в ближайшее время выложу обновленную версию (также там еще есть пара незначительных исправлений для повышения точности сравнения)
2) Можно. Для этого используйте класс TSimplex, а не TIntSimplex и функцию Solve вместо IntSolve.

---
Каждый человек всегда может найти, чем он может быть полезен окружающим. Проблема только в одном: слишком многие не хотят это искать.
4X_Pro
Руководитель Проекта
Настоящий Компьютерщик
4X_Pro
Откуда: Москва
Всего сообщений: 2994
Рейтинг пользователя: 79





Дата регистрации на форуме:
29 сен. 2001
Только что проверил, у меня решение получается именно при Delta[j]:=Delta[j]-C[j], причем как в обычном, так и в целочисленном методе. Если сделать наоборот, то на первом же шаге получается ноль.

---
Каждый человек всегда может найти, чем он может быть полезен окружающим. Проблема только в одном: слишком многие не хотят это искать.
Bas
Новичок


Всего сообщений: 2
Рейтинг пользователя: 0





Дата регистрации на форуме:
19 мая 2005
Добавлю только одно,
Ваш код переписан на JAVA.
Gram
Понечетный Участник Проекта

Gram
Откуда: здешний
Всего сообщений: 566
Рейтинг пользователя: 14

Репутация пользователя: 1




Дата регистрации на форуме:
23 июля 2003
Bas, а может ты сделаешь программку для мобильных телефонов? За этот апплет я думаю очень много человек бы тебе спасибо сказали :)
4X_Pro
Руководитель Проекта
Настоящий Компьютерщик
4X_Pro
Откуда: Москва
Всего сообщений: 2994
Рейтинг пользователя: 79





Дата регистрации на форуме:
29 сен. 2001
По поводу переписанного кода: возможно, там где-то есть ошибка, которая и приводит к смене знака...
Еще один важный момент: ограничения x[i]>=0 неявно подразумеваются самим симплекс-методом, поэтому явно задавать их не надо (это как раз и приведет к зацикливанию).

---
Каждый человек всегда может найти, чем он может быть полезен окружающим. Проблема только в одном: слишком многие не хотят это искать.
Sonntex
Новичок


Всего сообщений: 2
Рейтинг пользователя: 0





Дата регистрации на форуме:
8 дек. 2006
Здравствуйте!

С помошью этого алгоритма можно получить не одно единственное решение? К примеру грань лежит под прямым углом у критерию, боюсь вообще представить как все выглядит в n-мерном пространстве. Это может быть использовано, к примеру, в методе с жестким приоритетом в многокритериальной задаче, где нужно проверять количество решений, если количесвто решений = 1, то получен оптимум, > 1 - задача решается по другому критерию.
4X_Pro
Руководитель Проекта
Настоящий Компьютерщик
4X_Pro
Откуда: Москва
Всего сообщений: 2994
Рейтинг пользователя: 79





Дата регистрации на форуме:
29 сен. 2001
Нет, алгоритм всегда дает одно решение. Если требуется больше, то нужно задавать дополнительные условия.
Например, получаем первое решение для L=c1*x1+c2*x2+c3*x3
Затем добавляем условие c1*x1+c2*x2+c3*x3 < L и решаем еще раз, получая второе решение.

---
Каждый человек всегда может найти, чем он может быть полезен окружающим. Проблема только в одном: слишком многие не хотят это искать.
Sonntex
Новичок


Всего сообщений: 2
Рейтинг пользователя: 0





Дата регистрации на форуме:
8 дек. 2006
Хм... не понятен принцип алгоритма.

К примеру такая задача

1*X1 - 3*X2 -> min

-1*X1 + 2*X2 <= 6
1*X1 + 1*X2 <= 5
1*X1 + 1*X2 >= 1

Как только появляется неравенство со знаком >= происходит непонятная мне вещь. В конструкторе CreateBasis обнуляется весь критерий. А затем вместо коэффициентов критерия мы записываем коэффициенты соответствующего знаку >= ограничения. Т.е. в данном случае после построение канонической формы третье уравнение будет с коэффициентами 1, 1, 0, 0, -1, 0. Такой же выбирается и критерий.

Я просто пытаюсь переделать метод так, чтобы он работал пошагово. Алгоритм гонял только на min и max для знаков <=. А тут заметил что при >= происходит вот такая вот штука. Это алгоритм такой или я просто печатаю в TStringGrid не те значения (Печатаю в методе SimplexStep содержимое C, L и Cons.A, Cons.B). Видимо не в том месте я значения вывожу, ибо ответ то верный получается.

Подскажите в каком методе можно взять значения коэффициентов всех ограничений и критерия для текущего шага симплекс метода.

Заранее благодарен.
<<Назад  Вперед>>Печать
Объединенный Открытый Проект »   Прочее »   Форум поддержки прочих разработок »   Вопрос по симплексу
RSS
Быстрый переход в раздел:


Время выполнения скрипта: 0.0538. Количество выполненных запросов: 18, время выполнения запросов 0.0208