2014 dxdy logo

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

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


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


В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".

Если Вы зададите новый вопрос в существующей теме, то в случае нарушения оформления или других правил форума Ваше сообщение и все ответы на него могут быть удалены без предупреждения.

Не ищите на этом форуме халяву, правила запрещают участникам публиковать готовые решения стандартных учебных задач. Автор вопроса обязан привести свои попытки решения и указать конкретные затруднения.

Обязательно просмотрите тему Правила данного раздела, иначе Ваша тема может быть удалена или перемещена в Карантин, а Вы так и не узнаете, почему.



Начать новую тему Ответить на тему
 
 Интересный пример по линейному прогр.
Сообщение03.08.2015, 20:12 


03/08/15
70
Здравствуйте.
Пример взят из книги Ходыкин В.Ф Преображенский А.А Сборник задач по математическому программированию, 2002 г. Страница 105, задача 5.2.61
Вот собственно пример, с которым дальше не могу разобраться.
$z=4x_1   \Rightarrow$ минимизируется
$2x_2+x_3=7$
$2x_1+2x_2        =4$
$2x_1+x_2          \geqslant4$
Каноническая форма:
$2x_2+x_3=7$
$2x_1+2x_2+x_4=4$
$2x_1+x_2-x_5+x_6=4$
Базисные переменные: $x_3, x_4, x_6$
Так как во втором ограничении знак равно, а в третьем больше или равно, то вводим искусственную функцию:
$w=x_4+x_6$
Выражаем искусственную функцию через небазисные переменные:
$w=8-4x_1-3x_2+x_5$,
или
$w-8=-4x_1-3x_2+x_5$
Далее я буду приводить скриншоты программы, которую я написал чтобы не пересчитывать симплекс-таблицу на листе бумаги.
На первом скриншоте собственно каноническая форма задачи с базисными переменными и исскуственной функцией
Изображение
Рассматриваем w-строку (искусственная функция). Выбираем ведущим столбец номер 1 (значение -4). Сразу же в программе видны симплекс-отношения: Для второй и третьей строки они совпадают и равны 2 (последний столбец таблицы). Первая строка не рассматривается т.к мы не можем делить на ноль. Применяем правило Бленда и выбираем переменную с наименьшим индексом. В данном случае $x_4$. Значит ведущая строка это строка номер 2. Переменная $x_4$ выйдет из базиса, а вместо нее базисной станет $x_1$. Пересчитываем таблицу:
Изображение
А вот здесь самое интересное. Вспомним нашу искусственную функцию : $w=x_4+x_6$
Мы видим, что $x_6$ не вышла из базиса, а когда есть искусственная функция ,то когда она обнуляется все искусственные переменные должны выйти из базиса, иначе мы не можем продолжать решение т.к система ограничений несовместна. В данном случае искусственная функция обнулилась и значение $x_6=0$, хотя она не вышла из базиса! А $x_4$ не входит в базис, поэтому ее значение тоже равно нулю и получается что $w=0$ и значит все правильно! Искусственная функция равна нулю. И вот теперь я хотел спросить как тут быть: С одной стороны мы не можем решать , т.к не все искусственные переменные вышли из базиса ($x_6$), а с другой стороны искусственная функция то обнулилась и значение $x_6=0$. Это получается то же самое что если бы она вышла из базиса. Я посмотрел ответ в книге (стр. 204 ).
Он такой :
$z=8$
$x_1=2$
$x_2=0$
$x_3=7$
Если обратить внимание на текущие значения базисных переменных и значение целевой функции (z-строка), то они совпадают с ответом. Но в строке целевой функции есть же еще отрицательный элементы.
Вот теперь как дальше решать, есть ли какие методы?
Кстати в книге есть еще один похожий пример под номер 5.2.60

 Профиль  
                  
 
 Re: Интересный пример по линейному прогр.
Сообщение03.08.2015, 23:57 
Заслуженный участник
Аватара пользователя


28/04/14
795
матмех спбгу
Решать нужно забыв про линейное программирование.

 Профиль  
                  
 
 Re: Интересный пример по линейному прогр.
Сообщение04.08.2015, 00:22 
Заслуженный участник


16/02/13
3538
Владивосток
Что-то вообще не помню слов «искусственная функция» в линейном программировании. То ли что-то новое, то ли хорошо забытое старое.
Задача несколько вырожденная, по крайней мере, при обычном требовании неотрицательности переменных: из второго и третьего ограничений немедленно следует $x_2=0$.
И на кой вам сдались ваши $x_4$, $x_6$ — что-то вообще не понимаю.

 Профиль  
                  
 
 Re: Интересный пример по линейному прогр.
Сообщение04.08.2015, 13:08 


03/08/15
70
Цитата:
Решать нужно забыв про линейное программирование.

мм...странно. Вообще это задача линейного программирования, ну по крайней мере она должна быть решена симплекс-методом.
Слово "искусственная целевая функция" встречается в книге Б.Банди Основы линейного программирования, 1989. Видимо из за того что вводятся искусственные переменные $x_4, x_6$ функция так и называется искусственной. Иначе это называется метод искусственного базиса. Согласен с Вами, скорее всего название "искусственная целевая функция" уже не применяется, ну по крайней мере в современной литературе.
Что касается вводимых переменных объясню. Ведь задача в стандартной форме должна переводиться в каноническую. А тут неизбежны добавления дополнительных переменных. Да, получается что задача становится вырожденной на определенном этапе

 Профиль  
                  
 
 Re: Интересный пример по линейному прогр.
Сообщение04.08.2015, 16:07 
Заслуженный участник


16/02/13
3538
Владивосток
А, 1989 — это для меня слишком ново.
damir_777 в сообщении #1042620 писал(а):
Что касается вводимых переменных объясню
Не понимаю. Новые переменные вводятся 1) для превращения неравенств в равенства. Например, $x_1+x_2\geq1$$x_1+x_2-x_3=1$. 2) Для переменных, на которые нет условия неотрицательности. Например, нас интересуют $x_1$ любые и мы меняем её на $x_2-x_3$. Ваши преобразования к таковым не относятся. Ах да, есть ещё искусственный начальный базис. Ладно, согласен, хоть это и не относится к переводу задачи в каноническую форму.
А таки что там с искусственной функцией? Целевая у вас $4x_1$, её надо выразить через базисные. Получаем $4x_1=2(4-x_4-2x_2)=2(4-x_4-(7-x_3))=-6-2x_4+2x_3$, не?
damir_777 в сообщении #1042620 писал(а):
получается что задача становится вырожденной на определенном этапе
Да нет же. Смотрите: $2x_1+x_2\geq4$, а $2x_1+2x_2=4$. Учитывая (если оно есть!) требование неотрицательности переменных, получаем $x_2=0$

 Профиль  
                  
 
 Re: Интересный пример по линейному прогр.
Сообщение04.08.2015, 18:12 


01/10/10
54
В задачах линейного программирования терминология весьма разнообразна. Встречал разные названия одного и того же метода, приёма и т.д.
Хотя термина "искусственная целевая функция" раньше не видел.

По сути задачи
1) необходимо явно уточнить, есть ли условия неотрицательности переменных
2) ТС решает задачу 2-х этапным (2-х фазным) симплекс-методом, немного напутав с действиями, но в целом верно.
надо так:
$z=4x_1   \Rightarrow \min
$2x_2+x_3=7$
$2x_1+2x_2        =4$
$2x_1+x_2          \geqslant 4$
$x_1 \geqslant 0, x_2 \geqslant 0, x_3 \geqslant 0$

Приводим задачу к канонической форме
$z=4x_1   \Rightarrow \min
$2x_2+x_3=7$
$2x_1+2x_2        =4$
$2x_1+x_2 - x_4 = 4$
$x_1 \geqslant 0, x_2 \geqslant 0, x_3 \geqslant 0, x_4 \geqslant 0$

Теперь решаем задачу 1-ого этапа (вспомогательную), вводим 2 искусственные переменные
$F=x_5+x_6   \Rightarrow \min
$2x_2+x_3=7$
$2x_1+2x_2+x_5        =4$
$2x_1+x_2 - x_4+x_6 = 4$
$x_1 \geqslant 0, x_2 \geqslant 0, x_3 \geqslant 0, x_4 \geqslant 0, x_5 \geqslant 0, x_6 \geqslant 0$

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

 Профиль  
                  
 
 Re: Интересный пример по линейному прогр.
Сообщение04.08.2015, 23:18 
Заслуженный участник


16/02/13
3538
Владивосток
Psw в сообщении #1042685 писал(а):
$F=x_5+x_6   \Rightarrow \min$
Вот это место не поясните? У меня тут упорно получается $x_3-x_5$ в ваших обозначениях.

 Профиль  
                  
 
 Re: Интересный пример по линейному прогр.
Сообщение05.08.2015, 13:20 


03/08/15
70
Цитата:
1) необходимо явно уточнить, есть ли условия неотрицательности переменных

Да все переменные неотрицательны, я не стал просто снизу писать это условие в начале задачи (хотя надо было).
Что касается несовпадения индексов переменных, дело в том, что в своей программе (не та что на скриншоте (я ее написал для проверки), а другая, которая решает задачу уже полностью автоматически переводя в каноническую форму и в конце выдает ответ) я просматриваю последовательно строки каждого ограничения и присваиваю индексы вводимым переменным последовательно по порядку. Т.е. начиная со второго ограничения нужно ввести переменную. Вводим $x_4$. Потом просматривается 3-е ограничение. Следующие по порядку индексы $x_5, x_6$. Но смысл остается тем же.
Что касается метода, то я остановился на решении 2-х фазным симплекс-методом, да и во многих книгах по лин. прог. видел именно его. Попадалось пару раз и какой то метод с вводом штрафа за использование доп. переменных, но честно говоря я его не очень что то понял.
Цитата:
Дальше цифири я не проверял, но для последней полученной симплекс-таблицы решение можно продолжить и вывести искусственную переменную $x_6$ из базиса, для этого достаточно умножить 3-ю строку таблицы на $(-1)$ и т.д.

Т.е получается на последнем этапе мне уже нужно просматривать строку целевой функции (Z) выбрав в качестве разрешающего столбца $x_2$, ну т.е решать как обычно?

-- 05.08.2015, 15:52 --

Цитата:
Не понимаю. Новые переменные вводятся 1) для превращения неравенств в равенства. Например, $x_1+x_2\geq1$$x_1+x_2-x_3=1$. 2) Для переменных, на которые нет условия неотрицательности. Например, нас интересуют $x_1$ любые и мы меняем её на $x_2-x_3$. Ваши преобразования к таковым не относятся.

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

 Профиль  
                  
 
 Re: Интересный пример по линейному прогр.
Сообщение05.08.2015, 15:48 


01/10/10
54
iifat в сообщении #1042749 писал(а):
Psw в сообщении #1042685 писал(а):
$F=x_5+x_6   \Rightarrow \min$
Вот это место не поясните? У меня тут упорно получается $x_3-x_5$ в ваших обозначениях.
В 2-х этапном симплекс-методе на 1-ом этапе решается вспомогательная задача, целевая функция - сумма искусственных переменных, задача на мин.
В результате находим допустимое начальное решение исходной задачи и на 2-ом этапе работает уже обычный симплекс-метод.
Собственно говоря, такая схема используется во всех методах, которыми можно решить исходную задачу - М-метод (или метод больших штрафов), 2-х этапный (фазный) симплекс-метод, двойственный симплекс-метод.
Можно посмотреть обсуждение по этой ссылке http://e-science.ru/node/120246

damir_777 в сообщении #1042867 писал(а):
Что касается несовпадения индексов переменных, дело в том, что в своей программе (не та что на скриншоте (я ее написал для проверки), а другая, которая решает задачу уже полностью автоматически переводя в каноническую форму и в конце выдает ответ) я просматриваю последовательно строки каждого ограничения и присваиваю индексы вводимым переменным последовательно по порядку. Т.е. начиная со второго ограничения нужно ввести переменную. Вводим $x_4$. Потом просматривается 3-е ограничение. Следующие по порядку индексы $x_5, x_6$. Но смысл остается тем же.
На самом деле, этот момент принципиальный. Многие лекторы вообще обозначают переменные разного типа разными буковками, типа s, u, t, r. Изначальные переменные $x_1, x_2, \ldots $, далее приводим модель в каноническую форму, эти переменные обозначают уже следующей буквой, они для модели имеют прямой экономический смысл. В самой распространённой модели - это остатки товара на складе. Я предпочитаю называть их балансовыми.
А вот следующие переменные не имеют никакого эконом. смысла, потому и называются искусственными. Их обозначают уже следующей буквой. Эти переменные фиктивные и при решении М-методом или 2-х этапным они обязательно должны быть выведены из базиса, иначе система ограничений просто несовместна.

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

 Профиль  
                  
 
 Re: Интересный пример по линейному прогр.
Сообщение07.08.2015, 14:34 


03/08/15
70
Я прорешал до конца пример и что то не понял одной вещи.
Возьмем изначальный пример:
Цитата:
$F=x_5+x_6 \Rightarrow \min
$2x_2+x_3=7$
$2x_1+2x_2+x_5 =4$
$2x_1+x_2 - x_4+x_6 = 4$
$x_1 \geqslant 0, x_2 \geqslant 0, x_3 \geqslant 0, x_4 \geqslant 0, x_5 \geqslant 0, x_6 \geqslant 0$

Здесь индексы расставлены правильно.
Изображение
Рассматриваем w-строку и выбираем в качестве ведущего первый столбец. Видим что симплекс-отношения равны друг другу (оба равны 2). Поэтому применяем правило Бленда и исключаем переменную, имеющую наименьший индекс из двух $x_5, x_6$. Здесь это $x_5$.
Пересчитываем таблицу:
Изображение
Первый этап задачи решен. W-строку не рассматриваем т.к ее значение равно нулю и первый этап задачи решен. Теперь уже минимизируем целевую функцию. Рассматриваем Z-строку. Ведущий столбец $x_2$, ведущая строка $x_1$. Пересчитываем таблицу:
Изображение
В Z-строке нет отрицательных переменных, задача решена. Но $x_2$ не удовлетворяет третьему ограничению исходной задачи!
$2x_1+x_2 \geqslant 4$, да и $x_6$ до сих пор не вышел из базиса.
Теперь вернемся к самой начальной симплекс-таблице, только не будем применять правило Бленда:
Изображение
Выбираем для исключения не $x_5$, а $x_6$. Пересчитываем таблицу:
Изображение
В w-строке остались еще отрицательные элементы, поэтому выбираем в качестве ведущего столбца $x_2$, а переменная для исключения $x_5$ (0/1). Пересчитываем таблицу:
Изображение
И вот этот ответ!
Что то я вот не понял, почему не сработало когда я применил правило Бленда?) Ведь по идее же когда симплекс-отношения одинаковы применяется правило Бленда либо лексикографический способ. Но здесь что то не сработало
Кстати я скачал пару программ , которые решают задачи лин. программирования, чтобы проверить этот пример. Так они выдают ответ что система ограничений несовместна. Ну это понятно, ведь там наверное логика такая, что функция на первом этапе с искусственными переменными обнулилась, а искусственная переменная не вышла из базиса. Вообщем че то я запутался

 Профиль  
                  
 
 Re: Интересный пример по линейному прогр.
Сообщение11.08.2015, 17:55 


03/08/15
70
Вроде разобрался с ответами подобных задач.
В книге есть 4 таких примера (5.2.47, 5.2.60, 5.2.61, 5.83).
Во всех этих примерах после завершения 1-фазы, когда вспомогательная задача решена, то всегда остается искусственная переменная. Т.е она не вышла после завершения 1-фазы из базиса, но ее значение равно нулю. Я заметитл, когда так происходит, то нужно прекращать решение (несмотря на то, что в целевой функции могут остаться отрицательные элементы (Z-строка)), а полученные значения и есть оптимальное решение задачи (сверил все ответв ). Если решать дальше, то всегда получается что какая нибудь переменная не удовлетворяет тому или иному ограничению. Странно что в учебниках не объясняют такие примеры. Сколько просмотрел , ничего не нашел похожего.
Ну я думаю что это действительно оптимальное решение в таких случах, потому что алгоритмов как продолжать решение дальше в подобных случаях не встречал)

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

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



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

Сейчас этот форум просматривают: нет зарегистрированных пользователей


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

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