Интересный пример по линейному прогр.

[damir_777]

Здравствуйте.
Пример взят из книги Ходыкин В.Ф Преображенский А.А Сборник задач по математическому программированию, 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

[demolishka]

Решать нужно забыв про линейное программирование.

[iifat]

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

[damir_777]

Цитата:

Решать нужно забыв про линейное программирование.

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

[iifat]

А, 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$

[Psw]

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

По сути задачи
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)$ и т.д.

[iifat]

Psw в сообщении #1042685 писал(а):

$F=x_5+x_6 \Rightarrow \min$

Вот это место не поясните? У меня тут упорно получается $x_3-x_5$ в ваших обозначениях.

[damir_777]

Цитата:

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$. Ваши преобразования к таковым не относятся.

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

[Psw]

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

[damir_777]

Я прорешал до конца пример и что то не понял одной вещи.
Возьмем изначальный пример:

Цитата:

$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). Пересчитываем таблицу:

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

[damir_777]

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