Словесная формулировка задачи

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

Математическая формулировка

Пусть XI]— недельный фонд времени (в часах), выделяемый на заводе i для производства узла j. Тогда объемы производства каждого из трех комплектующих узлов будут равны:

узел 1: 8 х₁₁ + 6 х₂₁,

узел 2: 5 х₁₂+ 12 х₂₂,

узел 3: 10 х₁₃ + 4 х₂₃.

Так как в конечной сборке каждый из комплектующих узлов пред­ставлен в одном экземпляре, количество конечных изделий должно быть равно количеству комплектующих узлов, объем производства которых минимален. Если, например, объем производства двух заводов составляет 100, 112 и 108 соответствующих узлов, то коли­чество конечных изделий будет равно min [100, 112, 1081=100, Поэтому количество конечных изделий можно выразить через число комплектующих узлов следующим образом:

min [8 х₁₁ + 6 х₂₁, 5 х₁₂+ 12 х₂₂, 10 х₁₃ + 4 х₂₃. ]

узел 1 узел2 узел3

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

максимизировать z= min [8 х₁₁ + 6 х₂₁, 5 х₁₂+ 12 х₂₂, 10 х₁₃ + 4 х₂₃. ]

при ограничениях

х₁₁ + х₁₂ + х₁₃ ≤ 100 (завод 1)

х₂₁ + х₂₂ + х₂₃ ≤ 80 (завод 2)

х_ij≥ 0, i=1, 2; j=1, 2, 3.

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

y – количество изделий = min [8 х₁₁ + 6 х₂₁, 5 х₁₂+ 12 х₂₂, 10 х₁₃ + 4 х₂₃. ]

Этому выражению с математической точки зрения эквивалентна следующая формулировка:

максимизировать y

при ограничениях

8 х₁₁ + 6 х₂₁ ≥ y

5 х₁₂+ 12 х₂₂, ≥ y

10 х₁₃ + 4 х₂₃. ≥ y

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

Таким образом, окончательно математическую модель можно записать в виде

максимизировать z= y

при ограничениях

8 х₁₁ + 6 х₂₁ – y ≥ 0,

5 х₁₂+ 12 х₂₂ – y ≥ 0,

10 х₁₃ + 4 х₂₃ – y≥ 0,

х₁₁+ х₁₂ + х₁₃ ≤ 100,

х₂₁ + х₂₂ + х₂₃≤ 80,

х_ij≥ 0, для всех i и j, y ≥ 0

Пример 2.2.6. (Целевое программирование.) Во всех предыдущих примерах ограничения представляют собой соотношения, правые и левые части которых связаны знаками: ≤, ≥ или =, Однако при построении моделей, адекватных реальным ситуациям, иногда целесообразно отразить тот факт, что при соответствующей ком­пенсации (штрафе) можно допустить нарушение того или иного ограничения. Это можно пояснить на следующем примере. Фирма, предпринимающая меры по организации нового производства, обычно имеет ограниченный инвестиционный фонд, но может увеличить объем капиталовложений за счет займа необходимых средств. Штраф в этом случае есть процент, под который был получен заем. Естественно, что привлечение заемных средств окажется экономически оправданным только в том случае, если новое производство, будет прибыльным с учетом выплачиваемых процентов. Такой вид математического моделирования часто называют целевым программированием, так как уже сама формулировка модели ориентирована на нахождение уровня использования тех или иных ресурсов, который соответствовал бы цели, поставленной лицом, принимающим решение.

Модель целевого программирования рассмотрим на следующее простом примере. При изготовлении изделий двух видов осуществляется последовательная обработка соответствующих заготовок на двух различных станках. Каждый станок может использоваться для производства изделий по 8 ч в сутки, однако этот фонд времени можно увеличить на 4 ч за счет сверхурочных работ. Каждый час сверхурочного времени требует дополнительных расходов в размере 5 долл. Производительность станков и прибыль в расчете на одно изделие приведены в таблице. Требуется определить объемы про­изводства изделий каждого вида, обеспечивающие получение мак­симальной чистой прибыли.