Предприятие выпускает три вида крепежных изделий: гайки, болты и шайбы. Норма расхода сырья, времени работы оборудования и затрат на электроэнергию, которые необходимы для производства одной тонны каждого изделия, приведены в таблице. Месячные запасы ресурсов, которыми располагает предприятие, ограничены. По сырью эти ограничения обусловлены емкостью складских помещений, по оборудованию - станочным парком и трудовыми ресурсами, по электроэнергии – техническими и финансовыми причинами. Спрос на шайбы не превосходит 0,2 т., а спрос на гайки не превышает 25 т. Размеры запасов и прибыль от реализации продукции в у.е. за 1 тонну приведены в таблице. Требуется сформировать месячную производственную программу (определить объемы выпуска каждого вида продукции), при которой прибыль от реализации будет максимальным. Составить математическую модель данной задачи и решить ее симплекс-методом.
Ресурсы Нормы расхода ресурсов на тонну продукции Ограничения по ресурсам
Шайбы Гайки Болты Сырье 12,5 20 27,5 350
Оборудование 10 15 25 300
Электроэнергия 12,5 17,5 22,5 325
Прибыль (у.е. / т) 90 140 200
Решение
1. Составляем математическую модель нашей задачи.
Вводим обозначения для объемов выпуска каждого вида продукции:
x1 – месячная программа выпуска шайб (т);
x2 – месячная программа выпуска гаек (т);
x3 – месячная программа выпуска болтов (т).
При этом прибыль предприятия от реализации продукции составит
f=90x1+140x2+200x3
Целью решения задачи является определение среди всех допустимых таких значений x1, x2 и x3, которые максимизируют прибыль предприятия от реализации продукции.
Рассмотрим ограничения задачи.
Значения программы выпуска шайб, гаек и болтов не могут быть отрицательными, поэтому x1≥0, x2≥0, x3≥0.
Три ограничения задачи из всех её ограничений связаны с имеющимися месячными запасами ресурсов сырья, времени работы оборудования и затрат на электроэнергию.
Математическая запись указанных ограничений такова:
12,5x1+20x2+27,5x3≤350 – имеющийся месячный запас ресурсов сырья не может быть превышен;
10x1+15x2+25x3≤300 – имеющийся месячный запас ресурсов времени работы оборудования не может быть превышен;
12,5x1+17,5x2+22,5x3≤325 – имеющийся месячный запас ресурсов затрат на электроэнергию не может быть превышен.
Ещё два ограничения задачи из всех ограничений задачи связаны со спросом на продукцию. Математическая запись этих ограничений такова:
x1≤0,2 – не следует превышать спрос на шайбы;
x2≤25 – не следует превышать спрос на гайки.
В целом соотношения математической модели задачи об оптимальных объемах выпуска каждого вида продукции выглядят следующим образом:
f=90x1+140x2+200x3max
при ограничениях
12,5x1+20x2+27,5x3≤350
10x1+15x2+25x3≤300
12,5x1+17,5x2+22,5x3≤325
x1≤0,2
x2≤25
x1≥0, x2≥0, x3≥0
2. Для решения задачи симплекс-методом применяется каноническая форма её записи
. В такой задаче осуществляется поиск неотрицательных значений переменных, для которых линейная целевая функция достигает максимума. При этом неравенства исходной задачи преобразуют в равенства с неотрицательной правой частью за счет введения дополнительных неотрицательных переменных.
Получаем:
z=90x1+140x2+200x3+0(x4+x5+x6+x7+x8)max;
12,5x1+20x2+27,5x3+x4=350;
10x1+15x2+25x3+x5=300;
12,5x1+17,5x2+22,5x3+x6=325;
x1+x7=0,2;
x2+x8=25;
xj≥0; j=1,…,8.
Здесь дополнительные переменные x4, x5, x6, x7 и x8 введены для перехода от неравенств к равенствам. Они включены в целевую функцию с нулевыми коэффициентами.
Переменные x4, x5, x6, x7 и x8 образуют естественный базис. Начальное опорное решение (0;0;0;350;300;325;0,2;15) допустимо.
Работа с симплекс-таблицей состоит в следующем:
1) среди оценочных элементов переменных находим наибольший по модулю отрицательный; этот столбец будет разрешающим; соответствующая переменная может быть переведена в разряд базисных;
2) для выбранного разрешающего столбца вычисляются значения оценочных отношений как результат деления соответствующих элементов вектора B на положительные элементы разрешающего столбца; из всех оценочных отношений выбирается минимальное, и при этом соответствующая строка будет разрешающей;
3) на пересечении разрешающих столбца и строки находится разрешающий элемент.
На основании начальной (нулевой) симплекс-таблицы приступаем к построению новой (первой) симплекс таблицы.
Получение каждой новой симплекс-таблицы на основании предыдущей выполняется по одной и той же схеме:
1) в разрешающей строке все элементы (включая и элемент вектора B) делятся на разрешающий элемент;
2) элементы разрешающего столбца (за исключением разрешающего элемента, который стал равным единице) обнуляются;
3) все остальные элементы матрицы (в том числе и элементы вектора B, а также оценочной строки) пересчитываются по правилу прямоугольника (новое значение равно старому значению за вычетом произведения соответствующих элементов из разрешающей строки и столбца, поделенного на разрешающий элемент);
Приступаем к этапу построения начальной (нулевой) симплекс-таблицы.
Построение нулевой симплекс-таблицы состоит в её заполнении данными на основании канонической записи задачи и найденного базиса:
X x1 x2 x3 x4 x5 x6 x7 x8 x* ⇒ X x1 x2 x3 x4 x5 x6 x7 x8 x* ⇒ X x1 x2 x3 x4 x5 x6 x7 x8 x* ⇒
x4 25/2 20 55/2 1 0 0 0 0 350
x4 3/2 7/2 0 1 -11/10 0 0 0 20
x4 3/7 1 0 2/7 -11/35 0 0 0 40/7
x5 10 15 25 0 1 0 0 0 300
x5 2/5 3/5 1 0 1/25 0 0 0 12
x2 1/7 0 1 -6/35 8/35 0 0 0 60/7
x6 25/2 35/2 45/2 0 0 1 0 0 325
x3 7/2 4 0 0 -9/10 1 0 0 55
x3 25/14 0 0 -8/7 5/14 1 0 0 225/7
x7 1 0 0 0 0 0 1 0 1/5
x7 1 0 0 0 0 0 1 0 1/5
x7 1 0 0 0 0 0 1 0 1/5
x8 0 1 0 0 0 0 0 1 25
x8 0 1 0 0 0 0 0 1 25
x8 -3/7 0 0 -2/7 11/35 0 0 1 135/7
z -90 -140 -200 0 0 0 0 0 0
z -10 -20 0 0 8 0 0 0 2400
z -10/7 0 0 40/7 12/7 0 0 0 17600/7
⇒ X x1 x2 x3 x4 x5 x6 x7 x8 x*
x2 0 1 0 2/7 -11/35 0 -3/7 0 197/35
x3 0 0 1 -6/35 8/35 0 -1/7 0 299/35
x6 0 0 0 -8/7 5/14 1 -25/14 0 445/14
x1 1 0 0 0 0 0 1 0 1/5
x8 0 0 0 -2/7 11/35 0 3/7 1 678/35
L 0 0 0 40/7 12/7 0 10/7 0 17602/7
x*=(1/5;197/35;299/35); z(x*)=17602/7→max
Кейс-задание №3 (k = 25).
Составить и решить задачу, двойственную к кейс-
Задать вопрос
на новый заказ в Автор24.
