« Quantity variance -сумма mix variance и yield variance | Main | Сдала CMA 3 "Strategic Management" »
December 26, 2005
Симплекс метод, пример №2
В прошлом примере мы разобрали пошаговое решение простой задачи линейного программирования в каноническом виде с неотрицательной правой частью в неравенствах ограничений. Рассмотрим более общий случай:
4х1 + 15х2 + 12х3 + 2х4 -> min
2x2 + 3x3 + x4 >= 1
x1 + 3x2 + x3 - x4 >= 0
x1, x2, x3, x4 >=0
Приведем задачу в следующий вид:
-4х1 - 15х2 - 12х3 - 2х4 -> max
-2x2 - 3x3 - x4 <= -1
-x1 - 3x2 - x3 + x4 <= 0
x1, x2, x3, x4 >=0
Введем переменные S1, S2 >= 0, тогда задача примет стандартный (канонический) вид:
-4х1 - 15х2 - 12х3 - 2х4 -> max
0x1 - 2x2 - 3x3 - x4 + 1s1 + 0s2 = -1
-x1 - 3x2 - x3 + x4 + 0s1 + 1s2 = 0
x1, x2, x3, x4, s1, s2 >=0
Составим симплекс таблицу (кликните для увеличения):
1 шаг: В строке Cj выписываем коэффициенты целевой функции при переменных x1, x2, x3, x4, s1, s2. В строках 1,2 - коэффициенты при соответсвующих переменных из уравнений ограничений. В столбце RHS (right hand side), в строках 1, 2 пишем числа -1 и 0 из правой части уравнений ограничений. Переменные, образующие единичную матрицу (выделена бежевым) будем называть базисными, в данном случае s1 и s2.
2 шаг: Заполняем столбец CB строки 1, 2 коэффициентами целевой функции при базисных переменных, то есть 0 при s1 в строке 1 (пересечение строки 1 и столбца s1) и 0 при s2 в строке 2.
3 шаг: заполняем строку 3 (Zj) путем перемножения каждого элемента столбца CB на соответствующие элементы строк 1, 2 и сложением. То есть первый элемент строки Zj получается как: 0*0 + 0*(-1) = 0. Второй как 0*(-2)+0*(-3). В данном случае все элементы строки получаются равными 0. Аналогично получается 0 в столбце RHS.
4 шаг: строка 4 (Cj - Zj) получается почленным вычитанием элементов строки 3 (Zj) из элементов строки Cj (всегда из верхней строки на всех шагах).
5 шаг: Смотрим на элементы RHS выше строки Zj (у нас на строки 1 и 2). Если все элементы RHS неотрицательные, то идем на шаг 5". Если есть хоть один отрицательный элемент, идем на шаг 5'.
5' шаг: В каждой строке 1 и 2 вычисляем соотношения RHS/x, где x пробегает значения той же строки, что и RHS, столбцы x1, x2, x3, x4, s1, s2. Мы ищем МИНИМАЛЬНЫЙ СТРОГОПОЛОЖИТЕЛЬНЫЙ ЭЛЕМЕНТ среди получившихся чисел (то есть мы можем вычислять RHS/x только для х того же знака, что и RHS). В нашем случае:
Строка 1:
столбец х2: (-1)/(-2)=0,5; столбец х3: (-1)/(-3)=0,3333(3); столбец х4: (-1)/(-1)=1;
Строка 2: все соотношения равны нулю.
Минимальный строгоположительный элемент получился в столбце x3. Этот элемент назовем ведущим, у нас -3. В таблице он выделен зеленым цветом. Строка и столбец, содержащие этот элемент называются ведущими.
Идем на шаг 7.
7 шаг: Формируем строки 5, 6 путем деления ведущей строки на ведущий элемент и формирования единичного столбца на месте ведущего). Не забываем RHS.
Сделаем совместно еще одну итерацию. На предыдущем шаге мы заполнили строки 5, 6. Далее выполняем последовательно шаг 2, шаг 3 и шаг 4, получаем новую строку (Cj - Zj), у нас строка 8. Идем на шаг 5 - на второй итерации у нас RHS в строках 5, 6 >0 , значит идем на шаг 5".
5" шаг: Ищем в строке 8 (Cj - Zj) МАКСИМАЛЬНЫЙ СТРОГОПОЛОЖИТЕЛЬНЫЙ элемент. Если такой есть, то ему соответствует ведущий стролбец (у нас x4). Идем на шаг 6. Если в (Cj - Zj) нет строгоположительных элементов, то идем в конец.
6 шаг: Ищем в ведущем столбце МИНИМАЛЬНО ПОЛОЖИТЕЛЬНОЕ число из формулы (RHS/ведущий столбец). То есть, в данном случае, выбираем между 0,33/0,33=1 и 0,33/1,33=0,25. Найдя такое число, определяем ведущую строку, у нас строка 6. Пересечение ведущих столбца и строки дает нам ведущий элемент, в нашем случае 1,33 (выделен зеленым). Идем на шаг 7.
Конец: итерации продолжаются до тех пор (в случае, что оптимальное решение задачи существует), пока на шаге 5' или на шагах 5" и 6 мы не сможем отыскать положительного ведущего элемента.
В нашем примере:
Мы сформировали строки 9, 10, 11. RHS (строки 9, 10) неотрицательна, следовательно идем на шаг 5". Число 3,50 - максимальный строгоположительный элемент (стролбец s1), но положительного ведущего элемента в этой строке нет.
Тогда в строке Zj (у нас строка 11) в RHS - столбце получим значение целевой функции в оптимальной точке (x3, x4) = (0,25; 0,25) равное -3,5. Значения 0,25 и 0,25 получаем из RHS в строках 9, 10.
Posted by mazoo at December 26, 2005 2:36 PM
Статьи по теме:
Comments
Не пойму ситуации с окончательным значением целевой функции, почему написано что в строке 11 в RHS -4, однако, там -3.5
фиг со значением целевой функцией, но какие же значения брать для оптимальной точки???
Posted by: Vaulter at January 23, 2006 7:01 PM
Vaulter, вы совершенно правы, у меня опечатка, с вашего позволения я ее исправлю.
Как и написано, значение целевой функции получаем в столбце RHS в той строке, где не можем найти нужного ведущего элемента, в нашем случае в строке 11 и значение целевой функции, конечно
-3,5 = -12*0,25 - 2*0,25;
значения для оптимальной точки ровно над ним в строках 9 и 10 , то есть (0,25; 0,25) - это x3 и x4.
Спасибо!
Posted by: Mazoo at January 23, 2006 8:23 PM
Добрый день!
Нам не понятны преобразования Симплекс-таблицы на 7 шаге.
Как из строки 2 получается 6 строка
и как из строки 5 получается 9 строка?
Posted by: Shumi and Custodian at February 8, 2006 4:11 PM
Привет!
Ну, на седьмом шаге мы совершаем обычные линейные преобразования над строками матрицы такие, чтоб получить единичный столбец на месте ведущего. В данном случае строка 6 получена как строка 1 деленная на (-3) плюс строка 2, то есть:
при х1: 0/(-3)+(-1) = (-1)
при х2: (-2)/(-3)+(-3) = (-2,33) - написано округленно, но считается нормально, так как из Excel-я
при х3: (-3)/(-3)+(-1) = 0
ну и так далее.
Строка 9 аналогично: строка 6 деленная на (-4) плюс строка 5. То есть в каждом случае нам надо чтоб в ведущем столбце была одна единица, а все остальные - нули.
Posted by: Mazoo at February 8, 2006 7:07 PM
Если в строке c-z все элементы отрицательные, кроме s2 и в этом столбце есть положительные величины, стоит продолжать решать, если (согласно проверке) решение уже найдено?
Posted by: Аня at February 10, 2006 9:18 PM
Аня, я немного не поняла в вашем вопросе какую проверку вы имеете ввиду? Проверку как у меня в алгоритме (отсутствие положительного ведущего элемента), или какую-то другую?
Posted by: Mazoo at February 11, 2006 12:27 PM
нужен пример задачи о смесях...
Posted by: Zhenya at April 17, 2006 8:29 PM
Помогите решить задачу
F(x1,х2,х3)=2х1+3х2+х3--->max
x1+3x2+5x3меньше либо равно 15
x1+x2+x3меньше либо равно 7
2x1+x2+4x3меньше либо равно 12
x1>либо равно0,x2>либо равно0,x3>либо равно0
Решить задачу линейного программирования симплекс методом
Возаграждение гарантированно (нужно к завтрошнему дню)
Пожалуйста помогите [:(][:(]
Posted by: caries at May 23, 2006 6:43 PM
интересно, задачи линейного программирования можно решать в Excel - очень просто, есть еще QSB, но он совсем уж... поотжил наверное свое. Хотя алгоритм решения знать все же необходимо.
Posted by: Ёжик at October 9, 2006 11:47 PM
Люди, мне очень нужно решить 1 задачу простую...
<<<<<<<<<<<<<
В сплаве должно содержаться не менее 8 единиц хим. Элемента А, 21 единиц --- элемента Б и 16 единиц --- элемента В. Предприятие закупает металлический лом 2-х видов: 1 и 2. В таблице указано содержание хим. Элементов в ломе каждого вида и цена единицы веса лома. Минимизировать расходы при закупке необходимого предприятию металлического лома.
Хим. Эл-ты Содержание эл-в в единице веса лома
1 2
А 1 5
Б 12 3
В 4 4
Цена ед-цы
лома, Д\е 5 2
Posted by: Леля at October 27, 2006 1:14 AM
Ежик, да, автоматических считалок полно, просто иногда надо проемонстрировать именно знание алгоритма :-)
Вот, кстати, одна из онлайн-считалок:
http://www-fp.mcs.anl.gov/otc/Guide/CaseStudies/simplex/applet/SimplexTool.html
Posted by: Mazoo at November 9, 2006 6:13 PM
Обращение к народу:
Народ! Решать задачки лично я совершенно не буду! Я могу помочь, если вы объясните мне на каком шаге у вас возникла проблема или ответить на вопрос по существу. Но решать ваши задачки с самого начала - увольте! Поэтому, прежде чем ожидать того, что кто-то бросит все свои дела и начнет на досуге щелкать ваши задачки на симплекс-метод, может сначала приложите сами немного своего времени и усилий, чтобы решить задачу? Тогда и ненужных обид не будет.
Posted by: Mazoo at November 9, 2006 6:16 PM
Хм. Случайно наткнулся на зацикливание.
Плохо, что не указан пример когда уравнений 3 а не 2. Тогда видны некоторые неточности на этапе 7. Там надо обязательно умножать не только ту строку где не хватает 0 до единичного столбца но и другую строку если даже в ней уже есть не обходимый 0(что бы избавится от другого минуса в RHS при условии что он там есть). Иначе у нас получается бесконечный цикл при условии, что ведущей переменной является 1.
Фактически на каждой итерации будет меняться тока СВ, Zj и Cj-Zj .
Posted by: stalkerg at November 14, 2006 6:48 PM
Решим задачи линейного программирования.
Posted by: Simplex at November 29, 2006 1:07 PM
Вопрос!
как будет выглядеть симплекс таблица, если в условии дано не два, а три неравенства ограничений?
заранее благодарен:)
Posted by: Crazy at December 13, 2006 12:10 AM
Проблема такая:
x1-x3 -> min
x1-2x2+x3 = 1
x1+3x2+x4 = 2
x1, x2, x3, x4 >=0
на второй итерации при нахождении ведущего элемента получается зацикливание, минимальный положительный элемент получается в базисе
Posted by: ALEX at January 22, 2007 1:20 PM
Проблема такая:
-х1 + х3 -> max
-x1 + 2x2 – x3 = -1
-x1 - 3x2 - x4 = -2
x1, x2, x3, x4 >=0
на второй итерации при нахождении ведущего элемента получается, что минимальный положительный элемент соотношения RHS/x находится в базисе, получается зацикливание.
помогите разобраться!
Posted by: ALEX at January 22, 2007 1:52 PM
Ладно мы нашли эти х3 и х4 и значение, а х1 и х2 где?? или я не что то пропустил?
Posted by: MAG at February 12, 2007 9:21 PM
похоже, что я запуталась.
3х_1+2x_2>=10
4x_1+6x_2>=20
x_1+3x_2>=7
x_1,x_2>=0
f=3x_1+4x_2 ---> min
Ну, перевела в задачу нахождения максимума, ввела базисные переменные. Получила
-3x_1-2x_2+x_3=-10
-4x_1-6x_2+x_4=-20
-x_1-3x_2+x_5=-7
x_1,...x_5>=0
f=-3x1-4x2 ---> max
Решаю и получаю дробные числа. Ответ в задаче точно x_1=2, x_2=2 и f=14.
Неужели совсем считать разучилась? Обидно. Третий день над задачкой бьюсь и каждый раз ответы разные получаю. Не те. :(
Помогите, пожалуйста.
Posted by: paralogism at April 13, 2007 12:29 AM
Действительно, непонятно как быть в случае более двух ограничений. У меня тоже получилось зацикливание потому как в колонке RHS единица. И еще не совсем понятно каким образом в колонке СВ на 5-ой сроке получилось -12. Заранее благодарен
Posted by: partem at May 13, 2007 3:57 PM
помогите пожалуйста составить правильно ограничения к задаче: есть 2 набора удобрений для газона: обычный и улучшенный. В обычный набор входит 3 фунта азотных, 4-фосфорных и 1калийных, а в улучш. -2 азотных, 6 фосфорных и 3 калийных. Известно что для некоторого газона требуется по кр. мере 10 фунтов азотных, 20 фосфорных и 7 калийных удобр. Обычный набор стоит 3 долл., улучш.-4 долл. Какие и сколько наборов удобр. надо купить, чтобы обеспечить эффективное питание почвы и минимизировать стоимость?
Я составила такие ограничения, но честно кое-что меня смущает, конкретно то что нет ответа на вопрос какие и сколько наборов. Да и при решении в таком виде у меня происходит зацикливание. Вот думаю может не то составила.
3х1+4х2+1х3=3
2х1+6х2+3х3=4
х1,х2,х3 >=0
10х1+20х2+7х3---->min
Posted by: Иринка at May 18, 2007 9:36 AM
Помогите срочно!!! Завтра нужно сдать, а у меня ничего не получается =((( Плз, хеллллллллп!!!
Решите задачу линейного программирования
Решить надо симплекс-етододом
F=C1*X1+C2*X2+C3*X3
A11*X1+A12*X2+A13*X3 <= B1
A21*X1+A22*X2+A23*X3=B2
A31*X1+A23*X2+A33*X3=B3
3я строчка А23 наверное опечатка, скорей всего А32
<= - меньше или равно
1 1 1
A= 4 3 2
-1 -3 -6
C=(2,3,-2)
B=(5,1,-2)
Posted by: mimius at May 27, 2007 7:49 PM
