(Отложенная) Генерация столбца

[damir_777]

Здравствуйте.
Я сейчас пытаюсь приспособить алгоритм генерации столбца для решения задачи линейного раскроя.
К примеру есть заготовка $ L=16$ метров.
есть следующие детали/их количества на которые нужно порезать исходную заготовку:

1. 3 метра. Необходимо 25 штук
2. 6 метров. Необходимо 20 штук
3. 7 метров. Необходимо 18 штук

Задача-использовать как можно меньше заготовок для выполнения данного заказа.
Обычно рекомендуют начать с самого простейшего плана раскроя, где количество раскроя равно количеству заготовок:
1. $16/3=5$ Количество деталей первого типа, которые максимально можно разместить на заготовке (взята целая часть числа)
2. $16/6=2$ Количество деталей второго типа (взята целая часть числа)
3. $16/7=2$ Количество деталей третьего типа (взята целая часть числа)
Таким образом получается исходная матрица, и она будет использована на первой итерации симплекс-метода:
$ \begin{bmatrix} 5&0&0 \\ 0&2&0\\ 0&0&2 \end{bmatrix}$
Решив задачу линейного программирования, и получив двойственные оценки, решаем задачу о рюкзаке, передав ей двойственные
оценки, длину исходного материала, и длину каждой детали. Получили решение. Решение будет новым столбцом.
Если целевая функция задачи о рюкзаке меньше нуля (кстати где то пишут что должна быть больше единицы, не пойму разницу), то столбец добавляется.
Добавили столбец.
Допустим, получилась следующая матрица, где последний столбец это решение задачи о рюкзаке:
$ \begin{bmatrix} 5&0&0&1 \\ 0&2&0&2\\ 0&0&2&0 \end{bmatrix}$
Решается задача линейного программирования уже с этой матрицей. Находим двойственные оценки из решения.
Снова решается задача о рюкзаке. Вот тут вопрос: Полученные столбцы после задачи о рюкзаке нужно постоянно добавлять, или же их
надо ставить вместо других столбцов, вместо тех, которые не будут входить в базис, т.е. задача будет в первом случае расти постоянно
по количеству переменных или же размер задачи уже не будет изменяться? (т.е. он будет равен размеру последней матрицы, будут только меняться значения в столбцах)

[Pphantom]

Тема перемещена из форума «Помогите решить / разобраться (М)» в форум «Карантин»
по следующим причинам:

- неправильно набраны формулы (краткие инструкции: «Краткий FAQ по тегу [math]» и видеоролик Как записывать формулы).

Исправьте все Ваши ошибки и сообщите об этом в теме Сообщение в карантине исправлено.
Настоятельно рекомендуется ознакомиться с темами Что такое карантин и что нужно делать, чтобы там оказаться и Правила научного форума.

[Pphantom]

Тема перемещена из форума «Карантин» в форум «Помогите решить / разобраться (М)»

[damir_777]

Я немного разобрался, как добавляются столбцы, причем все из английской литературы, там достаточно много примеров. К сожалению, на русском языке встречается только сухая теория с формулами и без примеров. В общем, столбцы только меняются, не добавляются новые. у меня другая проблема возникла. Вот маленький пример:
Длина исходной заготовки $L=24$.
Необходимо выполнить следующий заказ на раскрой (длина/количество):

1. 4/100
2. 5/800
3. 8/100

Простейший план раскроя, для начального решения задачи симплекс-методом:

1. $24/4=6$ . Максимальное кол-во заготовок первого типа, которые можно разместить в заданной длине
2. $24/5=4$ Максимальное кол-во заготовок второго типа, которые можно разместить в заданной длине. (Целая часть числа)
3. $24/6=3$ Максимальное кол-во заготовок третьего типа, которые можно разместить в заданной длине

Таким образом, получаются исходные коэффициенты при переменных в ограничениях в задаче линейного программирования:
$ \begin{bmatrix} 6&0&0 \\ 0&4&0\\ 0&0&3 \end{bmatrix}$
Решается задача лин. программирования, получаются следующие двойственные оценки из решения :
$0,167; 0,25; 0,333$.
Двойственные оценки, длину каждой детали и размер исходной заготовки передаем в задачу о рюкзаке.
Решение задачи о рюкзаке:
Значения переменных:
$1; 4; 0$
Значение "рюкзачной" функции, ну или максимальная стоимость всего рюкзака:
$z=1,167$.
Теперь, заменяем сгенерированным столбцом (это значения переменных в задаче о рюкзаке) первый столбец исходных ограничений.
Получаются следующие коэффициенты при переменных в ограничениях задачи линейного программирования:
$ \begin{bmatrix} 1&0&0 \\ 4&4&0\\ 0&0&3 \end{bmatrix}$
А чтобы вычислить , какой столбец заменить, выполняются все те же операции при замене столбца как в обычном модифицированном симплекс-методе. Двойственные оценки решенной задачи : $0,25; 0,333; 0$.
Решение задачи о рюкзаке дает следующее решение:
Значения переменных:
$1; 4; 0$
Значение "рюкзачной" функции, ну или максимальная стоимость всего рюкзака:
$z=1,583$.
Но такое значение уже было получено на предыдущем шаге, а функция еще не равна 1! Если на этом остановить решение, то решение всей задачи о раскрое не
будет оптимальным, а именно нужно использовать 234 заготовки. Сравнивая решение с перебором всех вариантов раскроя и решение
целочисленной задачи лин. программирования дает 225 заготовок.
Незнаю что делать.

[damir_777]

Разобрался, почему зацикливалось. Двойственные оценки были распределены неправильно, т.е. не в том порядке шли. Решил двойственным симплекс-методом, и оценки вышли в правильном порядке. У меня другой вопрос возник.Я объясню на этом же примере, хотя я его решил. Проблема возникла, когда я стал использовать уже 10 заготовок. (взял пример из Википедии, набрав в гугле "Задача раскроя". (https://ru.wikipedia.org/wiki/%D0%97%D0 ... 0%BE%D1%8F) Там, правда в примере 13 заготовок, но я смог решить задачу с 9 первыми заготовками, а на 10 уже возникла проблема)ю
Рассмотрим предыдущий пример. Допустим, в базис на текущем этапе входят следующие переменные: $x_3, x_1, x_2$ Я не буду приводить их значения, т.к. сейчас это не важно. Как в обычном модифиц. симплекс-методе, определяется переменная, которая должна покинуть базис. Пусть это будет $x_3$. Смотрим на индекс переменной, он равен трем, значит будет заменен третий столбец. У меня раньше возникала ошибка зацикливания, потому что я смотрел на позицию исключаемой переменной и заменял не тот столбец. В данном случае она на первом месте, и я заменял первый столбец, а когда начал смотреть на индекс переменной, и заменять столбец по номеру индекса исключаемой переменной, зацикливание исчезло. А что если бы у меня в базис входили след. переменные$x_5,x_1,x_2$ и из базиса должна уйти $x_5$? Ведь размер матрицы не меняется при каждом пересчете, у меня три заготовки и размер матрицы три на три, у меня же нет пятого столбца в ней.
Только на примере из Википедии получилось так, что я ввел 10 заготовок (пока на 10 пробую), матрица десять на десять, а из базиса должна
выйти на текущем этапе $x_1_3$