Сформулировать линейную производственную задачу и составить ее математическую модель

Содержание

• 1. Сформулировать линейную производственную задачу и составить ее математическую модель, взяв исходные данные из
• приложения
• Технологическая матрица A затрат ресурсов на единицу продукции каждого вида, вектор B объемов ресурсов и вектор C удельной прибыли

Предположим, что предприятие или цех выпускает n видов изделий, имея m групп оборудования. Известны нормы времени на обработку каждого изделия на каждой группе оборудования, например, в минутах или часах и фонд времени работы каждой группы оборудования. Пусть, кроме того, известно, что из всех n видов изделий наибольшим спросом пользуются k видов. Требуется составить план производства, при котором выпуск дефицитных изделий будет наибольшим возможным.

Компоненты производственной программы должны удовлетворять условию, что суммарное время обработки всех изделий на данной группе оборудования не должно превышать фонда времени работы этой группы оборудования. На обработку x1 единиц первого изделия на i-й группе оборудования будет затрачено ai1x1 единиц времени, на обработку x2 единиц второго изделия на той же группе оборудования будет затрачено ai2x2 единиц времени и т. д. Необходимое время на обработку всех x1, x2, x3, x4 изделий на i-й группе оборудования будет равно сумме

Эта сумма не может превышать фонд времени работы i-й группы оборудования, т. е. должна быть  bi. Выписывая такие условия для всех 3-x групп оборудования, получаем:

(1)

Так как компоненты плана суть количество изделий и, следовательно, не могут быть выражены отрицательными числами, то естественным образом добавляются условия:

x1  0, x2  0×3  0, x4  0. (2)

Обозначим через сj прибыль на единицу j-го изделия. При плане производства (х1, х2, х3, x4) прибыль предприятия будет равна:

z = c1x1 + c2x2 + c3x3 + c4x4 = 27×1 + 39×2 + 18×3 + 20×4. (3)

Мы хотим составить производственную программу (х1, х2,, хn) так, чтобы функция (3) приняла наибольшее значение при выполнении всех других условий.

Система линейных неравенств (1), (2) и линейная форма (3) образуют математическую модель задачи о рациональном использовании производственных мощностей. Среди всех решений системы линейных неравенств (1), удовлетворяющих условию неотрицательности (2), необходимо найти такое решение, при котором линейная форма (3) принимает наибольшее возможное значение. Это задача линейного программирования.

Последовательное улучшение производственной программы

Получили задачу на условный экстремум. Для ее решения систему неравенств (2) при помощи дополнительных неотрицательных неизвестных х5, х6, х7 заменим системой линейных алгебраических уравнений

(4)

где дополнительные переменные имеют смысл остатков соответствующих ресурсов. Среди всех решений системы уравнений (4), удовлетворяющих условию неотрицательности х10, х20,, х50,, х70. (5)

надо найти то решение, при котором функция (3) примет наибольшее значение.

Воспользуемся тем, что правые части всех уравнений системы (4) неотрицательны, а сама система имеет предпочитаемый вид дополнительные переменные являются базисными. Приравняв к нулю свободные переменные х1, х2, х3, х4, получаем базисное неотрицательное решение

x1=0, x2=0, x3=0, x4=0, x5 =140, x6=90, x7=198 (6)

первые четыре компоненты которого определяют производственную программу

x1=0, x2=0, x3=0, x4=0 (7)

по которой мы пока ничего не производим.

Составим начальную симплекс-таблицу:

Таблица 1.

Базис 27 39 18 20 0 0 0 Пояснения

Н x1 x2 x3 x4 x5 x6 x7

0 х5 140 2 1

6 5 1 0 0

0 х6 90

0 3 0 4 0 1 0

0 х7 198 3 2 4 0 0 0 1

0 z -27 -39 -18 -20 0 0 0

Перейдем к новому базису. Определим переменную, которая войдет в базис. Выбираем ту переменную, которая дает наиболее быструю прибыль. Из выражения (3) видим, что это x2. Она становится базисной.

Определим переменную, покидающую базис. Вычислим симплексные отношения, расположенные в последнем столбце симплекс-таблицы. Здесь числителем является свободный член ограничения (столбца Н), знаменателем положительные коэффициенты ведущего столбца, т. е. столбца x2. Строка, в которой находится минимальное симплексное отношение (90/3 = 30), является ведущей строкой, в этой же строке находится переменная x6, покидающая базис. На пересечении ведущего столбца и ведущей строки находится ведущий элемент (a22 = 3). Пересчитаем таблицу:

Таблица 2.

0 х5 110

2 0 6 11/3 1 -1/3 0

39×2 30 0 1 0 4/3 0 1/3 0

0 х7 138 3 0 4 -8/3 0 -2/3 1

1170-z -27 0 -18 32 0 13 0

Приравняв к нулю свободные переменные х1, х3, х4, х6, получаем базисное неотрицательное решение, причем первые четыре компоненты его определяют новую производственную программу х1=0, х2=30, х3=0, х4=0. (8)

Исследуем, является ли эта программа наилучшей, т. е. обеспечивает ли она наибольшую прибыль. Для этого выразим функцию прибыли (3) через новые свободные переменные х1, х3, х4, х6.

(9)

Видим, что программа (9) не является наилучшей, так как прибыль будет расти, если мы начнем производить или первую, или третью продукцию, но наиболее быстро функция z растет при возрастании х1. Поэтому принимаем х1 за разрешающую неизвестную, находим разрешающее уравнение по

= 46.

Пересчитываем таблицу.

Таблица 3.

0 х5 18 0 0 10/3 49/9 1 1/9 -2/3 все j 0

39×2 30 0 1 0 4/3 0 1/3 0

27×1 46 1 0 4/3 -8/9 0 -2/9 1/3

2412-z 0 0 18 8 0 7 9

Определяем базисное неотрицательное решение рассматриваемой задачи:

x1=46, x2=30, x3=0, x4=0, x5=18, x6=0, x7=0 (10)

производственную программу:

x1=46, x2=30, x3=0, x4=0 (11)

и остатки ресурсов: первого вида х5=18

второго вида х6=0 (12)

третьего вида х7=0

Выразим функцию цели z через свободные переменные

z = 2412 — 18×3 — 8×4 — 7×6 (13)

тогда в силу того, что все xj  0, прибыль будет наибольшей тогда, когда

x3=0, x4=0, x6=0 (14)

Это означает, что производственная программа (11) является наилучшей и обеспечивает предприятию наибольшую прибыль

zmax = 2412. (15)

Итак, организовав направленный перебор базисных неотрицательных решений системы условий задачи, мы пришли к оптимальной производственной программе и указали остатки ресурсов, а также максимальную прибыль.

Рассмотрим узкие места производства.

Остатки ресурсов второго и третьего видов равны нулю, это означает, что второй и третий виды сырья используются полностью при выполнении оптимальной производственной задачи. Это и есть узкие места производства.

Из последней симплексной таблицы запишем обращенный базис Q-1, соответствующий оптимальному набору базисных неизвестных (x5, x6, x7):

(16)

Проверим выполнение оотношения:

H = Q1B.

Имеем

Умножим Q1 на B:

Т.к. по оптимальной производственной программе два вида продукции (x3 и x4) не должны выпускаться, то составим математическую модель задачи оптимизации производственной программы с двумя оставшимися переменными (x1 и x2), сохранив прежнюю нумерацию переменных и решим ее графически. Получим исходные данные:

Математическая модель:

(17)

x1  0, x2  0. (18)

z = 27×1 + 39×2. (19)

Полученную задачу линейного программирования с двумя переменными можно решить графически. Система линейных неравенств (17), (18) определяет выпуклый многоугольник OPQR допустимых решений. Линии уровня функции Z перпендикулярны вектору-градиенту grad Z = (27, 39) и образуют семейство параллельных прямых (градиент указывает направление возрастания функции).