Доски длиной L, имеющиеся в достаточном количестве, следует распилить на заготовки двух видов: длиной l1 и длиной l2, причём заготовок первого вида должно быть получено не менее n 1 штук и заготовок второго вида –не менее n2 штук. Каждая доска может быть распилена на указанные заготовки несколькими способами.
Требуется найти число досок, распиливаемых каждым способом с тем, чтобы необходимое количество заготовок было получено из наименьшего количества досок.
Все необходимые числовые данные указаны в таблице.
Необходимо: 1) составить математическую модель в виде задачи ЦП; 2) решить задачу методом отсечений Гомори.
Решение
Вначале необходимо определить способы распилки досок на заготовки, которые могут быть представлены в виде следующей таблицы:
№ способа 1- вид заготовки 2- вид заготовки План
1 3 0 х1
2 2 1 х2
3 0 2 х3
Минимальное количество заготовок 85 56
Итак, существует 3 способа распилки досок для получения необходимых заготовок. Здесь введены обозначения:
Хi - планируемое количество досок, подлежащих распилке по i-му способу, i = 1,2,3.
Тогда планируемое количество досок для распилки определяется формулой: F= х1+х2+х3 → min. Это количество должно быть минимальным.
Количество первого вида заготовок должно быть не менее 85, поэтому запишем следующее неравенство: 3х1 +2 х2 ≥ 78, а количество 2-го вида заготовок – не менее 45:х2 + 2х3 ≥ 56.
Количество досок не может быть отрицательным и дробным числом, поэтому х1 ≥ 0, х2 ≥ 0, х3 ≥ 0, х1 , х2 , х3 – целые.
Итак, определена математическая модель данной задачи.
переход к канонической форме3x1+2x2-x4 = 85 x2+2x3-x5 = 56 Расширенная матрица системы ограничений-равенств данной задачи:
3 2 0 -1 0 85
0 1 2 0 -1 56
Приведем систему к единичной матрице методом жордановских преобразований. В качестве базовой переменной можно выбрать x4. Получаем новую матрицу:
-3 -2 0 1 0 -85
0 1 2 0 -1 56
В качестве базовой переменной можно выбрать x5. Получаем новую матрицу:
-3 -2 0 1 0 -85
0 -1 -2 0 1 -56
базисных переменных принимаем X = (4,5). Выразим базисные переменные через остальные: x4 = 3x1+2x2-85 x5 = x2+2x3-56 Подставим их в целевую функцию: F(X) = x1+x2+x3
Вместо переменной x4 следует ввести переменную x2. Выполняем преобразования симплексной таблицы методом Жордано-Гаусса.
Базис B x1 x2 x3 x4 x5
x2 85/2 3/2 1 0 -1/2 0
x5 -27/2 3/2 0 -2 -1/2 1
F(X0) -85/2 -1/2 0 1 1/2 0
Среди свободных членов bi имеются отрицательные значения, следовательно, полученный базисный план не является опорным. Вместо переменной x5 следует ввести переменную x4. Выполняем преобразования симплексной таблицы методом Жордано-Гаусса.
Базис B x1 x2 x3 x4 x5
x2 56 0 1 2 0 -1
x4 27 -3 0 4 1 -2
F(X1) -56 1 0 -1 0 1
Выразим базисные переменные через остальные: x2 = -2x3+x5+56 x4 = 3x1-4x3+2x5+27 Подставим их в целевую функцию: F(X) = x1+(-2x3+x5+56)+x3 или F(X) = x1-x3+x5+56 x2+2x3-x5=56 -3x1+4x3+x4-2x5=27 При вычислениях значение Fc = 56 временно не учитываем. Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:
A = 0 1 2 0 -1
-3 0 4 1 -2
Базисные переменные : x2, x4 Полагая, что свободные переменные равны 0, получим первый опорный план: X0 = (0,56,0,27,0) Базисное решение называется допустимым, если оно неотрицательно.
Базис B x1 x2 x3 x4 x5
x2 56 0 1 2 0 -1
x4 27 -3 0 4 1 -2
F(X0) 0 -1 0 1 0 -1
Переходим к основному алгоритму симплекс-метода. Текущий опорный план неоптимален, так как в индексной строке находятся положительные коэффициенты. В качестве ведущего выберем столбец, соответствующий переменной x3, так как это наибольший коэффициент. Вычислим значения Di по строкам как частное от деления: bi / ai3 и из них выберем наименьшее: min (56 : 2 , 27 : 4 ) = 63/4 Следовательно, 2-ая строка является ведущей. Разрешающий элемент равен (4) и находится на пересечении ведущего столбца и ведущей строки.
Базис B x1 x2 x3 x4 x5 min
x2 56 0 1 2 0 -1 28
x4 27 -3 0 4 1 -2 27/4
F(X1) 0 -1 0 1 0 -1 0
Получаем новую симплекс-таблицу:
Базис B x1 x2 x3 x4 x5
x2 85/2 3/2 1 0 -1/2 0
x3 27/4 -3/4 0 1 1/4 -1/2
F(X1) -27/4 -1/4 0 0 -1/4 -1/2
Среди значений индексной строки нет положительных
. Поэтому эта таблица определяет оптимальный план задачи. Окончательный вариант симплекс-таблицы:
Базис B x1 x2 x3 x4 x5
x2 85/2 3/2 1 0 -1/2 0
x3 27/4 -3/4 0 1 1/4 -1/2
F(X2) -27/4 -1/4 0 0 -1/4 -1/2
Оптимальный план можно записать так: x1 = 0, x2 = 421/2, x3 = 63/4 F(X) = 1*0 + 1*421/2 + 1*63/4 = 491/4 Метод Гомори. В полученном оптимальном плане присутствуют дробные числа. По 2-у уравнению с переменной x3, получившей нецелочисленное значение в оптимальном плане с наибольшей дробной частью 3/4, составляем дополнительное ограничение: q2 - q21•x1 - q22•x2 - q23•x3 - q24•x4 - q25•x5≤0 q2 = b2 - [b2] = 63/4 - 6 = 3/4 q21 = a21 - [a21] = -3/4 + 1 = 1/4 q22 = a22 - [a22] = 0 - 0 = 0 q23 = a23 - [a23] = 1 - 1 = 0 q24 = a24 - [a24] = 1/4 - 0 = 1/4 q25 = a25 - [a25] = -1/2 + 1 = 1/2 Дополнительное ограничение имеет вид: 3/4-1/4x1-1/4x4-1/2x5 ≤ 0 Преобразуем полученное неравенство в уравнение: 3/4-1/4x1-1/4x4-1/2x5 + x6 = 0 коэффициенты которого введем дополнительной строкой в оптимальную симплексную таблицу.
Базис B x1 x2 x3 x4 x5 x6
x2 85/2 3/2 1 0 -1/2 0 0
x3 27/4 -3/4 0 1 1/4 -1/2 0
x6 -3/4 -1/4 0 0 -1/4 -1/2 1
F(X0) -27/4 -1/4 0 0 -1/4 -1/2 0
Среди отрицательных значений базисных переменных выбираем наибольший по модулю. Ведущей будет 3-ая строка, а переменную x6 следует вывести из базиса. Минимальное значение θ соответствует 5-му столбцу, т.е
Задать вопрос
на новый заказ в Автор24.
