Есть, кто может помочь?

(0) Первый раз слышу, увы.

http://www.google.ru/search?hl=ru&newwindow=1&q=%D0%94%D0%B2%D1%83%D1%85%D1%8D%D1%82%D0%B0%D0%BF%D0%BD%D1%8B%D0%B9+%D1%81%D0%B8%D0%BC%D0%BF%D0%BB%D0%B5%D0%BA%D1%81+%D0%BC%D0%B5%D1%82%D0%BE%D0%B4+&btnG=%D0%9F%D0%BE%D0%B8%D1%81%D0%BA&lr=

(0) а чем от обычного симплекс-метода отличается?

+3 может "двойственная" имелась ввиду, а не двухэтапная?

2-х этапный, это метод решения задачи
сечас лекцию перепигу

Искуственное начальное решение
Когда в ограничении имется >=, = нельзя сразу определить допустипое базисное решение в этом случае использут метод искуственной переменной для нахождения начального доп. базисного решения:
- 2-х этапный
- метод штрафов

1. 2-х этапный
Во все орграничения задачи ЛП в которых нет остаточных переменных вводим искуственную переменную Р(сч)>=0. Рассматривая новую целевую функцию Ф=Сумма(Р(сч)) решаем задачу мин(Ф) с полученным ограничением, причем Р(сч) в целевой функции выражается через основные переменные задачи и соответствующие ограничения.
НА 1-м этапе решим задачу МИН(Ф) если Фопт=0, то исходная задача имеет решения, если Фопт>0 то задача решения не имеет.
На 2-м этапе возвращаемся к исходной целевой функции и решаем симплекс методом. В Ф уравнении находится исходная целевая функция, а остальная симплекс таблица соответсвует оптимальной таблице 1-го этапа. Причем если в оптимальной СТ 1-го этапа в базисе содержались переменные Ф уравнения исходной задачи то их необходимо выразить через другие переменные.

в тексте Ф = Z целевая функция

(6) помню м."северо-западного угла", ну и м. штрафов.

(7) северо западный, это метод рещения транспортной задачи

(0) может стоит попробовать олимпиадную задачу привести к транспортной

+8 только оптять же штрафы, еще и начисляемые сложным процентом

(8) Да, по всей видимости придется приводить к транспортной. Но я сейчас не этим занимаюсь.

Теорию изучаю так сказать.

Вопрос следующий: На втором этапе у меня в базисном решении осталась искусственная переменная с нулевым значением. Симплекс метод зацикливается. Что с этим делатЬ?

Из более-менее внятных рекомендаций нашел только это:

"Правило для второго этапа заключается в том, чтобы искуственные переменные оставлять в базисе всегда, когда коэффициент в ведущем столбце положителен или отрицателен." (С) Исследование операций, Хемди Таха

Что это значит при программной реализации - хоть убей не понимаю..

(2) Я уже изучил все эти ссылки..:(

(9) Все таки похоже, что "эмпирический способ" решения задачи наиболее оптимальный и быстрый.

(12) + имею ввиду последнюю задачу ветки "Симплекс метод решения задач оптимизации"

уже и не помню каким методом решал, даже библиотека классов была наработана,
а вот в случае как в (10) надлежит помнить, что симплекс-метод
неустойчив и нуждается в регуляризационных метОдах.

+14 по Тихонову

(14) так вот мне и надо узнать, что здесь за "регуляризационный метОд" нужен.

Вопрос в (10) все еще очень актуален.

Симплекс всегда сходится и устойчив, причем колво итераций не более чем 3*колво переменных способы ускорения симплекса делают его не устойчивым...

это касается только линейной постановки

up

up

(18) угу.
(19) покопаюсь, может найду, но обязательно нормировку перед этим
сделать надо

+21 а еще там нужно будет обращение матрицы делать.
В общем гемору дофигища

(22) Я уже понял..(

Симплекс 92 строки кода.
Двухэтапный симплекст - 234.

При этом все отлаживать надо очень долго.

Идем дальше...

Если есть примеры решения задач теории оптимизации - прошу поделиться. Или, еще лучше, какая-нибудь общая классификация задач теории оптимизации.

up