2014 dxdy logo

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

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



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


Посмотреть правила форума



Начать новую тему Ответить на тему
 
 Обобщенный/Двойственный симплекс метод c искусствен. огранич
Сообщение11.04.2017, 12:48 


03/08/15
48
Здравствуйте
Мне попалась такая задача:
$z=2x_1-x_2+x_3$ Функция ищется на максимум

$2x_1+3x_2-5x_3\geq4$

$-x_1+9x_2-x_3\geq3$

$4x_1+6x_2+3x_3\leq8$

(Все неизвестные больше или равны нулю )
Здесь нельзя применить двойственный симплекс-метод (модифицированный), т.к переменные $x_1, x_3$ не удовлетворяют условию оптимальности для задачи максимизации. Я понял так, что они должны быть со знаком минус, а здесь в целевую ф-цию они входят со знаком плюс.
Предлагается ввести дополнительное ограничение, чтобы можно было решить эту задачу:
$x_1+x_3\leq M$, где M- достаточно большое положительное число, такое, что данное неравенство не сужает область допустимых решений
исходной задачи.
1. Как нужно подбирать это число для различных задач такого типа, где целевая функция не удовлетворяет условиям оптимальности для задач максимизации или минимизации?
2. А если бы к примеру функция анализировалась на минимум, тогда получается $x_2$ не удовлетворяла условию оптимальности для задачи минимизации, то какое бы новое искусственное ограничение нужно было вводить? Т.е какой общий алгоритм ввода искусственных ограничений если те или иные переменные не удовлетворяют условию оптимальности?
Также этот пример можно решить обобщенным симплекс-методом:сначала решить двойственным, а потом когда значения базисных переменных примут неотрицательные значения, продолжить решать прямым симплекс-методом. Я вот бы хотел придерживаться больше именно этого плана, потому что, например, при анализе чувствительности какрас часто и бывает , что нужно комбинировать два метода, когда сначала значения отрицательные.
Но вопрос вот в чем. Я применяю модифицированный двойственный симплекс-метод, при этом пересчитывается не вся таблица, каноническая форма задачи вообще не изменяется при пересчетах. Когда после двойственного симплекс-метода нужно перейти к прямому, то исходная таблица должна уже содержать новые уравнения для прямого симплекс-метода, а тут только часть таблицы пересчиталась, а исходная таблица не изменяется вообще. Откуда ему брать новые данные? Я что то не нашел модифицированный обобщенный-симплекс метод в интернете...

 Профиль  
                  
 
 Re: Обобщенный/Двойственный симплекс метод c искусствен. огранич
Сообщение19.04.2017, 13:43 


03/08/15
48
Вот еще один пример
Изображение
Решение в последней таблице допустимо, но не оптимально: (правда там опечатка и базис $x_2$)
Изображение
Поэтому дальше можно продолжить решать прямым симплекс-методом. В этом и есть смысл обобщенного симплекс-метода, но проблема у меня возникла вот в чем: в данном примере вторая таблица получилась при применении не модифицированного симплекс-метода и видны значения векторов-столбцов небазисных переменных. При применении же модифицированного двойственного симплекс-метода верхняя таблица (каноническая форма) вообще не изменяется, а пересчитывается только часть таблицы. Вот как потом получить значения векторов-столбцов небазисных переменных? Ведь далее при применении прямого модифицированного симплекс-метода я уже должен отталкиваться от нижней таблицы, она у меня будет храниться постоянно, а только часть ее пересчитываться

-- 19.04.2017, 15:53 --

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

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

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



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

Сейчас этот форум просматривают: Someone


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

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