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

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

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 19.12.2006, 20:30
незарегистрированный

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

симплекс метод
Подскажите пожалуйста, когда симплекс метод не имеет допустимых решений. Очень надо!

Ответ, пожалуйста, пришлите на мыло: alarm88@rambler.ru
Спасибо.
  #2  
Старый 23.12.2006, 02:06
незарегистр(KENZO)

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

сам задал вопрос, сам и ответил.... :))
Вот полный и качественный алгоритм: (сам реализовал на Delphi7 и преаоду сдал ))) )^

2.2. Собственно алгоритм

1. Если предложена задача на максимум, то сформулировать эквивалентную задачу на минимум (умножить коэффициенты целевой функции на –1).
2. Обеспечить условие bi >= 0, при необходимости умножив для этого соответствующие уравнения системы на –1.
3. Если имеется готовое начальное базисное решение задачи, то перейти к п. 7, иначе перейти к п. 4.
4. Сформулировать вспомогательную ЗЛП (для нахождения начального базисного решения исходной задачи) следующим образом:
целевая функция: xn+1 + … + xn+m
i-тое уравнение системы: ai1x1 + … + ainxn + xn+i = bi
5. Решить вспомогательную ЗЛП, используя данный алгоритм, при этом положив начальным базисом (xn+1,…,xn+m).
6. Если после окончания решения вспомогательной ЗЛП в ее базисе останутся вектора An+i, где i > 0, то:
6.1. Если среди xn+i есть ненулевые, то исходная ЗЛП не имеет решения.
6.2. Если в симплекс-таблице, тем не менее, для всех таких i xij = 0, где j=1..n, то все вспомогательные вектора, вошедшие в базис, из него исключаются. Перейти к п. 7.
6.3. Если существуют ненулевые xij, то принудительно ввести в базис вектор Aj и вывести из базиса вектор Ai. Повторять п. 6.3 до тех пор, пока перестанут выполняться условия п. 6 или будут выполняться условия п. 6.2. После достижения необходимого результата перейти соответственно к п. 7 или к п. 6.2.
7. Сформировать симплекс-таблицу (если был задан начальный базис) заново или путем корректирования симплекс-таблицы вспомогательной ЗЛП (отсечь ненужные ее части).
8. Сделать преобразования симплекс-таблицы таким образом, чтобы матрица, составленная последовательно из векторов текущего базиса, была единичной.
9. Найти оценки j = (CБ, Aj) – Cj. Если среди них нет положительных, то перейти к п. 12, иначе выбрать среди них максимальную положительную k = max j и вывести из базиса соответствующий ей вектор Ak.
10. Положить I-1 = B (множество индексов векторов, входящих в текущий базис). Cтроить In+1 = { i In| для xik> 0 min xi,n/xik – одинаково для всех i }, пока очередное In+1 не будет состоять из одного элемента. Вектор с данным индексом необходимо вывести из базиса. Другой вариант: I0 пусто. В этом случае решение ЗЛП: целевая функция не ограничена (бесконечно убывает).
11. Изменить базис (вывести и ввести вектора, которые были определены для этого ранее). Перейти к п. 8.
12. Окончательное оптимальное решение формируется следующим образом: неизвестные, соответствующие не вошедшим в окончательный базис векторам, полагаются равными 0, а неизвестные, соответствующие векторам, вошедшим в базис, берутся из столбца A0 симплекс-таблицы (в этом столбце они распогалаются в том же порядке, в котором в таблице следуют базисные вектора).

Будут вопросы - пишите alarm88@mail.ru
  #3  
Старый 27.02.2008, 15:48
гость

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

Решение есть здесь
Тут экзешник http://letitbit.net/download/176a9c1...earLP.rar.html
А тут есть и исходники этой программы http://letitbit.net/download/985a8f5...ramma.rar.html
  #4  
Старый 08.05.2008, 00:39
гостьВадим Шловиков

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

"Simplex-method"
Симплекс-метод ошибочен.Подскажите,как сообщить об этом математикам Швеции?
  #5  
Старый 23.06.2008, 12:08
гость3

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

Алгоритм и описание
Я когда курсяк делал тут http://razy-coding.blogspot.com/2008/06/blog-post.html брал описание и реализацию алгоритма. Там статья наплохая и исходники есть.
  #6  
Старый 02.03.2010, 03:07
гость

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

Исправление ошибочного мнения.
Сообщение от гостьВадим Шловиков Посмотреть сообщение
Симплекс-метод ошибочен.Подскажите,как сообщить об этом математикам Швеции?
Приношу извинения, симплекс-метод неошибочен. Но необходимо установить правильную последовательность выбора переменных при решении симплекс-методом, вместо произвольного выбора переменных. Об этом есть статья "О выборе переменных при решении симплекс-методом", автором которой я являюсь. Правда, в ней указана не совсем правильная последовательность выбора переменных. Поэтому надо общими усилиями установить окончательную последовательность выбора переменных при решении симплекс-методом.
  #7  
Старый 03.03.2010, 14:39
гость

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

Скажите пожалуйста а на каком курсе начинают проходить симплекс-метод решения задач ЛП?
  #8  
Старый 03.03.2010, 19:54
гость

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

Сообщение от гость Посмотреть сообщение
Скажите пожалуйста а на каком курсе начинают проходить симплекс-метод решения задач ЛП?
да хоть на первом проходи, сразу после линейной алгебры
 


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

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


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
целочисленный симплекс-метод blizzard Реализация, исходники, языки 5 12.05.2009 13:11