p align="left">Ответ: и . Задача 8 (16.237) Решить полностью целочисленную задачу линейного программирования методом Гомори. Решение: Введем дополнительные переменные и запишем условие вспомогательной задачи линейного программирования для рассматриваемого случая: Считая дополнительные переменные базисными, запишем симплекс таблицу этой задачи, соответствующую угловой точке : |
| | | | | | | | 1 | 0 | 2 | 1 | 8 | | | 1 | 1 | 0 | -1 | 4 | | | -1 | 2 | 1 | 3 | 6 | | | -1 | -3 | -3 | -3 | -18 | | |
Произведем преобразования исходной симплекс-таблицы симплекс-методом следующим образом: смотрим на нижнюю строку - выбираем тот столбец, в котором нижний элемент отрицательный, если таких столбцов несколько, то выбираем любой (в нашем случае выбираем первый столбец ); далее смотрим на последний и выбранный столбцы - сравниваем отношения элементов последнего и выбранного столбцов (в выбранном столбце берем только положительные числа), и выбираем тот элемент выбранного столбца, где отношение элементов будет наименьшим (в нашем случае 9/3 и 0/1, так как второе отношение наименьшее, следовательно, опорным элементом будет 1); меняем местами переменные и , остальные переменные оставляем на своих местах; на место опорного элемента ставим отношение 1/(опорный элемент); а остальных местах разрешающей строки записываем соответствующие элементы исходной таблицы, деленные на опорный элемент; на свободные места разрешающего столбца ставим со знаком минус соответствующие элементы исходной таблицы, деленные на опорный элемент; оставшиеся свободные места в новой симплекс-таблице заполняем построчно следующим образом: из строки элементов исходной таблицы вычитаем произведение ее элемента из разрешающего столбца на уже заполненную разрешающую строку новой таблицы. Производя преобразования симплекс-метода, получим такую последовательность симплекс-таблиц: |
| | | | | | | | 4/3 | -2/3 | 5/3 | -1/3 | 6 | | | 2/3 | 5/3 | 1/3 | 1/3 | 6 | | | -1/3 | 2/3 | 1/3 | 1/3 | 2 | | | -2 | -1 | -2 | 1 | -12 | | |
|
| | | | | | | | 1 | 1 | 2 | 0 | 8 | | | 3/2 | -5/2 | -1/2 | -1/2 | 1 | | | -1/2 | 3/2 | 1/2 | 1/2 | 3 | | | -5/2 | 3/2 | -3/2 | 3/2 | -9 | | |
|
| | | | | | | | 1/2 | 1/2 | 1/2 | 0 | 4 | | | 7/4 | -9/4 | 1/4 | -1/2 | 3 | | | -3/4 | 5/4 | -1/4 | 1/2 | 1 | | | -7/4 | 9/4 | 3/4 | 3/2 | -3 | | |
|
| | | | | | | | -2/7 | 8/7 | 3/7 | 1/7 | 22/7 | | | 4/7 | -9/7 | 1/7 | -2/7 | 12/7 | | | 3/7 | 2/7 | -1/7 | 2/7 | 16/7 | | | 1 | 0 | 1 | 1 | 0 | | |
Как видим, в последней строке таблицы все элементы положительны, то есть получаем решение и . Но это решение не удовлетворяет условию целочисленности, поэтому дополняем последнюю симплекс-таблицу строкой, используя следующие правила: среди нецелых элементов выбирается произвольный элемент , по r-ой строке симплекс-таблицы составляется дополнительное ограничение вида (здесь мы полагаем, что свободные переменные имеют номера m+1,…,n). С помощью вспомогательной переменной это ограничение представляется в виде равенства и вводится в симплекс-таблицу дополнительной строкой Где , где фигурные скобки означают дробную часть. Таким образом, мы получаем следующую таблицу: |
| | | | | | | | -2/7 | 8/7 | 3/7 | 1/7 | 22/7 | | | 4/7 | -9/7 | 1/7 | -2/7 | 12/7 | | | 3/7 | 2/7 | -1/7 | 2/7 | 16/7 | | | 2/7 | -1/7 | -3/7 | -1/7 | -1/7 | | | 1 | 0 | 1 | 1 | 0 | | |
Так как , то после дополнения строкой симплекс-таблица перестает соответствовать допустимому базисному решению задачи линейного программирования, которую она описывает. Для перехода к допустимому базисному решению производятся следующие операции: а) строка с отрицательным свободным членом считается разрешающей; б) если все коэффициенты , то задача не имеет решения, в противном случае номер l разрешающего столбца находится из условия: в) совершается преобразование симплекс-таблицы с опорным элементом Если в новой таблице по-прежнему есть хотя бы один отрицательный свободный член, то описанная процедура повторяется, начиная с операции а), необходимое число раз. Применяя данные правила к нашей симплекс-таблице, мы получаем следующие преобразования: |
| | | | | | | | -2/7 | 8/7 | 3/7 | 1/7 | 22/7 | | | 4/7 | -9/7 | 1/7 | -2/7 | 12/7 | | | 3/7 | 2/7 | -1/7 | 2/7 | 16/7 | | | 2/7 | -1/7 | -3/7 | -1/7 | -1/7 | | | 1 | 0 | 1 | 1 | 0 | | |
|
| | | | | | | | 2 | 8 | -3 | -1 | 2 | | | -2 | -9 | 4 | 1 | 3 | | | 1 | 2 | -1 | 0 | 2 | | | -2 | -7 | 3 | 1 | 1 | | | 1 | 0 | 1 | 1 | 0 | | |
Полученная симплекс-таблица не только соответствует допустимому базисному решению, но и дает решение рассматриваемой задачи: и Ответ: и Задача 9 (16.258) Решить задачу дробно - линейного программирования. Знаменатель целевой функции положителен при всех x из допустимого множества U, так как . Вводим новые переменные , , и получаем следующую задачу линейного программирования: Неизвестные параметры мы можем уже из этих выражений найти: , Ответ: , Задача 10 (16.268) Решить задачу квадратичного программирования. , Решение: Матрица нашей квадратичной функции положительно определена. Наша исходная задача имеет вид: (1) , , (2) , . (3) На основании теоремы Куна-Таккера точка минимума целевой функции из (1) на допустимом множестве (2) и (3) может быть найдена как решение следующей системы уравнений с дополнительными переменными ; : , , , , , , , , удовлетворяющее условию неотрицательности: , , , , . Применяя выше описанные условия, мы преобразуем исходную задачу в следующий вид: Будем искать угловую точку множества, определяемого этой системой, методом искусственного базиса. Введем дополнительные переменные и в 3-е и 4-ое уравнения выше написанной системы, считая базисными переменными начальной угловой точки , , и . Вспомогательную целевую функцию выразим через свободные переменные , , , , и с помощью двух первых уравнений выше написанной системы. Последовательность симплекс-таблиц, приводящих к решению задачи, приведена ниже. Рамками обведены опорные элементы, а те свободные переменные, которые на данном шаге нельзя переносить в базисные из-за условий , обведены кружками. Как видим, в последней строчке нет отрицательных чисел, следовательно, мы нашли решение и оно имеет вид и . Ответ: и
Страницы: 1, 2
|