На пилораме имеется 250 досок длиной 3 м. Из них необходимо изготовить заготовки трех типов: длиной 1,8 м, 1,1 м и 0,7 м. Заготовок длиной 1,8 м должно быть получено не менее 100 шт., заготовок длиной 1,1 м – не менее 100 шт., заготовок длиной 0,7 м – не менее 200 шт. Прибыль, получаемая от одной заготовки первого типа, равна 16 денежных единиц (д.е.), от заготовки второго типа - 10 д.е., от заготовки третьего типа - 6 д.е. Сформулируйте задачу линейного программирования и, решив ее, определите, как распилить доски, чтобы получить максимальную прибыль. Добавьте к задаче требование достижения минимума общего количества операций распиливания. Решите полученную задачу, используя метод главного критерия. Сделайте вывод о зависимости между величиной получаемой прибыли и общим количеством операций распиливания.
Решение
Введем следующие обозначения:
L — длина исходного материала;
/, — длина заготовки i-ro вида, i = 1, ш
bj — количество заготовок i-го вида; у — номер варианта раскроя,у = 1,
п aXj — количество заготовок г-го вида при раскрое единицы исходного материала ноу-му варианту;
Cj — длина отхода поу-му варианту раскроя (разреза);
Xs — количество единиц исходного материала, распиливаемого поу-му варианту.
Тогда целевая функция по критерию минимума отходов принимает вид
а по критерию минимума раскраиваемых единиц исходного материала
при следующих условиях:
Необходимо определить оптимальное количество единиц исходного материала х} (бруса), раскраиваемых по каждому у-му варианту распила, которые должны удовлетворять условиям целочисленности переменных.
При этом следует обратить внимание на составление вариантов раскроя:
При этом длина отхода для любого варианта раскроя должна быть строго меньше длины самой короткой заготовки.
LINK Excel.SheetBinaryMacroEnabled.12 "C:\\Windows\\system32\\config\\systemprofile\\AppData\\Roaming\\Microsoft\\Excel\\Book1 (version 1).xlsb" "Sheet2!R5C5:R12C10" \a \f 5 \h \* MERGEFORMAT
Количество бруса по каждому варианту распила х) Количество,м
заготовк икаждого размера аи,м Остаток Cj, м
1,8 1,1 0,7
x1 1 1 0 0,1
x2 1 0 2 0,8
x3 0 2 1 0,1
x4 0 0 4 0,2
b1=100 b2=100 b3=200
х1 +х2=100
х1+2*х3=100
2*х2+х3+4*х4=200
F(х)=0,1*х1+0,8*х2+0,1*х3+0,2*х4---->min
Определим минимальное значение целевой функции F(X) = 0.1x1+0.8x2+0.1x3+0.2x4 при следующих условиях-ограничений.x1+x2=100x1+2x3=1002x2+x3+4x4=200Введем искусственные переменные x: в 1-м равенстве вводим переменную x5; в 2-м равенстве вводим переменную x6; в 3-м равенстве вводим переменную x7;x1+x2+x5 = 100x1+2x3+x6 = 1002x2+x3+4x4+x7 = 200Для постановки задачи на минимум целевую функцию запишем так:F(X) = Mx5+Mx6+Mx7 → minПолученный базис называется искусственным, а метод решения называется методом искусственного базиса.Причем искусственные переменные не имеют отношения к содержанию поставленной задачи, однако они позволяют построить стартовую точку, а процесс оптимизации вынуждает эти переменные принимать нулевые значения и обеспечить допустимость оптимального решения.Из уравнений выражаем искусственные переменные:x5 = 100-x1-x2x6 = 100-x1-2x3x7 = 200-2x2-x3-4x4которые подставим в целевую функцию:F(X) = M(100-x1-x2) + M(100-x1-2x3) + M(200-2x2-x3-4x4) → minилиF(X) = (-2M)x1+(-3M)x2+(-3M)x3+(-4M)x4+(400M) → minВведем новую переменную x0 = -2x1-3x2-3x3-4x4.Выразим базисные переменные <5, 6, 7> через небазисные (свободные).Базисное решение называется допустимым, если оно неотрицательно.x0 = 400-2x1-3x2-3x3-4x4x5 = 100-x1-x2x6 = 100-x1-2x3x7 = 200-2x2-x3-4x4Переходим к основному алгоритму симплекс-метода.Поскольку задача решается на минимум, то переменную для включения в текущий план выбирают по минимальному отрицательному числу в уравнении для x0.1
. Проверка критерия оптимальности.В выражении для x0 присутствуют отрицательные элементы. Следовательно, текущий план неоптимален.2. Определение новой базисной переменной.Поскольку коэффициент при переменной x4 больше, чем при остальных переменных, то при увеличении x4 целевая функция будет уменьшаться быстрее.max(-2,-3,-3,-4,0,0,0) = -4x0 = 400-2x1-3x2-3x3-4x4x5 = 100-x1-x2x6 = 100-x1-2x3x7 = 200-2x2-x3-4x4В качестве новой переменной выбираем x4.3. Определение новой свободной переменной.Вычислим значения Di по всем уравнениям для этой переменной: bi / ai4 и из них выберем наименьшее:min (- , - , 200 : 4 ) = 50Вместо переменной x7 в план войдет переменная x4.4. Пересчет всех уравнений.Выразим переменную x4 через x7x4 = 50-1/2x2-1/4x3-1/4x7и подставим во все выражения.x0 = 400-2x1-3x2-3x3-4(50-1/2x2-1/4x3-1/4x7)x5 = 100-x1-x2x6 = 100-x1-2x3После приведения всех подобных, получаем новую систему, эквивалентную прежней:x0 = 200-2x1-x2-2x3+x7x5 = 100-x1-x2x6 = 100-x1-2x3x4 = 50-1/2x2-1/4x3-1/4x7Полагая небазисные переменные x = (5, 6, 4) равными нулю, получим новый допустимый вектор и значение целевой функции:x = (2, 1, 2, 0, 0, 0, -1), x0 = 2001. Проверка критерия оптимальности.В выражении для x0 присутствуют отрицательные элементы. Следовательно, текущий план неоптимален.2. Определение новой базисной переменной.Поскольку коэффициент при переменной x3 больше, чем при остальных переменных, то при увеличении x3 целевая функция будет уменьшаться быстрее.max(-2,-1,-2,0,0,0,1) = -2x0 = 200-2x1-x2-2x3+x7x5 = 100-x1-x2x6 = 100-x1-2x3x4 = 50-1/2x2-1/4x3-1/4x7В качестве новой переменной выбираем x3.3. Определение новой свободной переменной.Вычислим значения Di по всем уравнениям для этой переменной: bi / ai3 и из них выберем наименьшее:min (- , 100 : 2 , 50 : 1/4 ) = 50Вместо переменной x6 в план войдет переменная x3.4. Пересчет всех уравнений.Выразим переменную x3 через x6x3 = 50-1/2x1-1/2x6и подставим во все выражения.x0 = 200-2x1-x2-2(50-1/2x1-1/2x6)+x7x5 = 100-x1-x2x4 = 50-1/2x2-1/4(50-1/2x1-1/2x6)-1/4x7После приведения всех подобных, получаем новую систему, эквивалентную прежней:x0 = 100-x1-x2+x6+x7x5 = 100-x1-x2x3 = 50-1/2x1-1/2x6x4 = 75/2+1/8x1-1/2x2+1/8x6-1/4x7Полагая небазисные переменные x = (5, 3, 4) равными нулю, получим новый допустимый вектор и значение целевой функции:x = (1, 1, 0, 0, 0, -1, -1), x0 = 1001. Проверка критерия оптимальности.В выражении для x0 присутствуют отрицательные элементы. Следовательно, текущий план неоптимален.2. Определение новой базисной переменной.Поскольку коэффициент при переменной x2 больше, чем при остальных переменных, то при увеличении x2 целевая функция будет уменьшаться быстрее.max(-1,-1,0,0,0,1,1) = -1x0 = 100-x1-x2+x6+x7x5 = 100-x1-x2x3 = 50-1/2x1-1/2x6x4 = 75/2+1/8x1-1/2x2+1/8x6-1/4x7В качестве новой переменной выбираем x2.3
Задать вопрос
на новый заказ в Автор24.
