Автомобильный завод производит легковые и грузовые автомобили. Завод включает три цеха, производственные мощности которых по каждому виду автомобилей в расчете на месяц даны в таблице:
Цех Производственные мощности в расчете на месяц
Легковые Грузовые
Кузовной 100 200
Моторный 120 144
Сборочный
легковые 110
грузовые
120
Прибыль от выпуска единицы легкового автомобиля составляет 16 000 д.е., а грузового – 11000 д.е. Рассчитайте объемы выпуска легковых и грузовых автомобилей, обеспечивающих максимальную прибыль.
Ответ
Максимальную прибыль 1780000 д. е. в месяц обеспечивает выпуск 70 легковых и 60 грузовых автомобилей.
Решение
Пусть х1 –планируемый объем выпуска легковых автомобилей,
х2 – планируемый объем выпуска грузовых автомобилей.
На выпуск всех машин двух типов каждому цеху дается 1 месяц, цеха работают одновременно.
На примере кузовного цеха представим расчет ежемесячного затрата времени на производство автомобиля каждого типа. В цехе ежемесячно выпускается 100 легковых автомобилей и 200 грузовых, что можно представить в виде 1100 и 1200, аналогично по остальным цехам.
Покажем формирование ограничений по ресурсу «время» на примере кузовного цеха.
Время работы цеха (в долях месяца) по изготовлению общего количества выпускаемых автомобилей типов Х1 и Х2 можно представить следующим образом
1100x1+1200x2.
Так как временной ресурс на выпуск всех автомобилей составляет 1 месяц, значит время работы цеха не должно превышать объема времени в 1 месяц, отсюда ограничение:
1100x1+1200x2≤1.
Аналогично определяем для остальных цехов.
Ограничения, которым должны удовлетворять значения переменных х1 и х2 связаны с тем, что эти переменные обозначают количество выпускаемых автомобилей. Поскольку кол-во автомобилей не может быть отрицательным, то значения х1 и х2 должны быть не отрицательными, т.е. x1 ≥ 0, x2 ≥ 0.
Обозначим получаемую прибыль через F(X), прибыль необходимо максимизировать, учитывая расчетную прибыль от автомобиля каждого типа максимальное значение целевой функции примет вид F(X) = 16000x1+11000x2
Экономико-математическая модель расчета оптимальной месячной программы выпуска автомобилей примет вид:
1100x1+1200x2≤1,
1120x1+1144x2≤1,
1110x1≤1,
1120x2≤1,
x1 ≥ 0, x2 ≥ 0.
Решим задачу симплекс-методом.
Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных.В 1-м неравенстве смысла (≤) вводим базисную переменную x3. В 2-м неравенстве смысла (≤) вводим базисную переменную x4. В 3-м неравенстве смысла (≤) вводим базисную переменную x5. В 4-м неравенстве смысла (≤) вводим базисную переменную x6.
1100x1+1200x2+x3 = 1,
1120x1+1144x2+x4 = 1,
1110x1+x5 = 1,
1120x2+x6 = 1,
x1 ≥ 0, x2 ≥ 0.
Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:
A = 1/100 1/200 1 0 0 0
1/120 1/144 0 1 0 0
1/110 0 0 0 1 0
0 1/120 0 0 0 1
Решим систему уравнений относительно базисных переменных: x3, x4, x5, x6.
Полагая, что свободные переменные равны 0, получим первый опорный план: X0 = (0,0,1,1,1,1)
Базис B x1 x2 x3 x4 x5 x6
x3 1 1/100 1/200 1 0 0 0
x4 1 1/120 1/144 0 1 0 0
x5 1 1/110 0 0 0 1 0
x6 1 0 1/120 0 0 0 1
F(X0) 0 -16000 -11000 0 0 0 0
Переходим к основному алгоритму симплекс-метода.
Итерация №0.
Проверка критерия оптимальности
. Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.
2. Определение новой базисной переменной. В качестве ведущего выберем столбец, соответствующий переменной x1, так как это наибольший коэффициент по модулю.
3. Определение новой свободной переменной. Вычислим значения Di по строкам как частное от деления: bi / ai1 и из них выберем наименьшее: min (1 : 1/100 , 1 : 1/120 , 1 : 1/110 , - ) = 100 Следовательно, 1-ая строка является ведущей.Разрешающий элемент равен (1/100) и находится на пересечении ведущего столбца и ведущей строки.
Базис B x1 x2 x3 x4 x5 x6 min
x3 1 1/100 1/200 1 0 0 0 100
x4 1 1/120 1/144 0 1 0 0 120
x5 1 1/110 0 0 0 1 0 110
x6 1 0 1/120 0 0 0 1 -
F(X1) 0 -16000 -11000 0 0 0 0
4. Пересчет симплекс-таблицы. Формируем следующую часть симплексной таблицы. Вместо переменной x3 в план 1 войдет переменная x1.Строка, соответствующая переменной x1 в плане 1, получена в результате деления всех элементов строки x3 плана 0 на разрешающий элемент РЭ=1/100. На месте разрешающего элемента получаем 1. В остальных клетках столбца x1 записываем нули.
Таким образом, в новом плане 1 заполнены строка x1 и столбец x1. Все остальные элементы нового плана 1, включая элементы индексной строки, определяются по правилу прямоугольника.
Для этого выбираем из старого плана четыре числа, которые расположены в вершинах прямоугольника и всегда включают разрешающий элемент РЭ.НЭ = СЭ - (А*В)/РЭ
СТЭ - элемент старого плана, РЭ - разрешающий элемент (1/100), А и В - элементы старого плана, образующие прямоугольник с элементами СТЭ и РЭ.
Представим расчет каждого элемента в виде таблицы:
B x1 x2 x3 x4 x5 x6
1 : 1/100 1/100 : 1/100 1/200 : 1/100 1 : 1/100 0 : 1/100 0 : 1/100 0 : 1/100
1-(1 • 1/120):1/100 1/120-(1/100 • 1/120):1/100 1/144-(1/200 • 1/120):1/100 0-(1 • 1/120):1/100 1-(0 • 1/120):1/100 0-(0 • 1/120):1/100 0-(0 • 1/120):1/100
1-(1 • 1/110):1/100 1/110-(1/100 • 1/110):1/100 0-(1/200 • 1/110):1/100 0-(1 • 1/110):1/100 0-(0 • 1/110):1/100 1-(0 • 1/110):1/100 0-(0 • 1/110):1/100
1-(1 • 0):1/100 0-(1/100 • 0):1/100 1/120-(1/200 • 0):1/100 0-(1 • 0):1/100 0-(0 • 0):1/100 0-(0 • 0):1/100 1-(0 • 0):1/100
0-(1 • -16000):1/100 -16000-(1/100 • -16000):1/100 -11000-(1/200 • -16000):1/100 0-(1 • -16000):1/100 0-(0 • -16000):1/100 0-(0 • -16000):1/100 0-(0 • -16000):1/100
Получаем новую симплекс-таблицу:
Базис B x1 x2 x3 x4 x5 x6
x1 100 1 1/2 100 0 0 0
x4 1/6 0 1/360 -5/6 1 0 0
x5 1/11 0 -1/220 -10/11 0 1 0
x6 1 0 1/120 0 0 0 1
F(X1) 1600000 0 -3000 1600000 0 0 0
Итерация №1.
1
Задать вопрос
на новый заказ в Автор24.
