Консультация онлайн # 202434

Раздел: Исследование операций
Автор вопроса: kabanov.anton2010 (Посетитель)
Дата: 24.03.2022, 13:49 Консультация неактивна
Поступило ответов: 1
Уважаемые эксперты! Пожалуйста, ответьте на вопрос:
Здравствуйте, уважаемые эксперты! Прошу вас ответить на следующий вопрос:
Для изготовления двух видов продукции P1 и P2 используют три вида сырья (S1, S2, S3).
На изготовление единицы продукции P1 используют сырье S1 - a1 (ед.), S2 - a2 (ед.), S3 - a3 (ед.). На изготовление единицы продукции P2 используют сырье S1 - b1 (ед.), S2 - b2 (ед.), S3 - b3 (ед.). Запасы сырья S1 составляют не более чем k1 , сырья S2 – не более чем k2 , сырья S3 – не более чем k3.
Прибыль от единицы продукции P1 составляет ? руб., от P2 составляет ? руб.
Необходимо составить такой план выпуска продукции, чтобы при ее реализации получить максимальную прибыль.
A1=2;a2=4;a3=9;b1=4;b2=6;b3=2;k1=720;k2=300;k3=422;( a=3;b=2)
Пусть произведено x1 единиц продукции P1 и x2 единиц продукции P2 (эти величины должны быть целыми и неотрицательными). Тогда будет израсходовано 2x1+4x2 единиц сырья S1 (но не более 720), 4x1+6x2 единиц сырья S2 (но не более 300) и 9x1+2x2 единиц сырья S4 (но не более 422). Если прибыль от продажи единицы продукции P1 и P2 составляет 3 и 2 рубля соответственно, то полная прибыль будет равна 3x1+2x2 руб. Требуется установить, при каких x1 и x2 она будет наибольшей.

Таким образом, имеем задачу линейного программирования: необходимо найти максимальное значение целевой функции F = 3x1+2x2 → max при системе ограничений:

x1≥0, x2≥0.

Перейдём к канонической форме, то есть приведём систему неравенств к системе уравнений путём введения дополнительных базисных переменных x3, x4, x5:

(дополнительные переменные обозначают неиспользованные остатки сырья). Полагая свободные переменные x1, x2 равными 0, получим начальный опорный план X = (0, 0, 720, 300, 422).

Составим симплекс-таблицу:
Базисx1x2x3x4x5
x324100720
x446010300
x592001422
F(X)-3-20000
Этот опорный план допустим, так как все свободные члены (720, 300, 422) положительны, но неоптимален, так как в индексной строке F(X) есть отрицательные коэффициенты.
Наибольший по модулю отрицательный коэффициент в индексной строке равен -3. Соответствующая ему переменная x1 будет новой базисной переменной, а соответствующий столбец - ведущим. Найдём частные от деления свободных членов на коэффициенты ведущего столбца: (720/2, 300/4, 422/9) = (360, 75, 422/9). Наименьшее среди них неотрицательное значение равно 422/9. Соответствующая ему переменная x5 будет новой свободной переменной, а соответствующая строка - ведущей:
Базисx1x2x3x4x5
x324100720
x446010300
x592001422
F(X)-3-20000
Разрешающий элемент, находящийся на пересечении ведущего столбца и ведущей строки, равен 9. Заменяем строку x5 на строку x1, для чего делим все её элементы на разрешающий элемент:
Базисx1x2x3x4x5
x324100720
x446010300
x112/9001/9422/9
F(X)-3-20000
Исключаем новую базисную переменную x1 из остальных строк, для чего вычитаем из них строку x1, умноженную на соответствующий элемент столбца x1 (2 для x3, 4 для x4 и -3 для F(X)):
Базисx1x2x3x4x5
x3032/910-2/95636/9
x4046/901-4/91012/9
x112/9001/9422/9
F(X)0-4/3001/3422/3
Получаем новый опорный план X = (422/9, 0, 5636/9, 1012/9, 0). Он допустим, так как все свободные члены (422/9, 5636/9, 1012/9) положительны, но неоптимален, так как в индексной строке F(X) есть отрицательный коэффициент -4/3 в столбце x2. Других отрицательных коэффициентов нет, поэтому переменная x2 будет новой базисной переменной, а соответствующий столбец - ведущим. Найдём частные от деления свободных членов на коэффициенты ведущего столбца: (1409/8, 22, 211). Наименьшее среди них неотрицательное значение равно 22. Соответствующая ему переменная x4 будет новой свободной переменной, а соответствующая строка - ведущей:
Базисx1x2x3x4x5
x3032/910-2/95636/9
x4046/901-4/91012/9
x112/9001/9422/9
F(X)0-4/3001/3422/3
Разрешающий элемент равен 46/9. Заменяем строку x4 на строку x2, разделив все её элементы на разрешающий элемент:
Базисx1x2x3x4x5
x3032/910-2/95636/9
x20109/46-2/2322
x112/9001/9422/9
F(X)0-4/3001/3422/3
Исключаем новую базисную переменную x2 из остальных строк, для чего вычитаем из них строку x2, умноженную на соответствующий элемент столбца x2 (2/9 для x1, 32/9 для x5 и -4/3 для F(X)):
Базисx1x2x3x4x5
x3001-16/232/23548
x20109/46-2/2322
x1100-1/233/2342
F(X)0006/235/23170
Получаем новый опорный план X = (42, 22, 548, 0, 0). Он допустим, так как все свободные члены (42, 22, 548) положительны, и оптимален, так как в индексной строке F(X) нет отрицательных коэффициентов. Оптимальный план можно записать как x1 = 42, x2 = 22, то есть при изготовлении 42 единиц продукции P1 и 22 единиц продукции P2 прибыль от их продажи будет максимальна и равна 170 руб. При этом x4 = x5 = 0, но x3 = 548, то есть сырьё S2 и S3 будет израсходовано полностью, остаток же сырья S1 составит 548 единиц.

Последнее редактирование 29.03.2022, 07:15 Коцюрбенко Алексей Владимирович (Старший модератор)


Коцюрбенко Алексей Владимирович

Старший модератор
29.03.2022, 07:12
5

Мини-форум консультации # 202434


Нет сообщений в мини-форуме
Возможность оставлять сообщения в мини-форумах консультаций доступна только после входа в систему.
Воспользуйтесь кнопкой входа вверху страницы, если Вы зарегистрированы или пройдите простую процедуру регистрации на Портале.