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

Как уже можно было заметить, словесные формулировки, от­носящиеся к определению переменных модели, не обладают требу­емой однозначностью. Известна продолжительность смены — 8 ч, однако не известно, когда должна начинаться та или иная смена. 1слн ориентироваться на общепринятый трехсменный график работы (8: 01 — 16: 00; 16: 01—24: 00; 24: 01—8: 00) и обозна­чить количество автобусов, выходящих на линию в первую, вторую и третью смены через х₁, х₂ и х₃соответственно, то из рис. 2.7 можно видеть, что х₁≥ 10, х₂≥ 2 и х₃ ≥ 8. Поэтому общее минимальное количество используемых автобусов будет равно х₁+ х₂ +х₃=10+ 12 + 8=30.

Это решение приемлемо лишь в том случае, если расписание смен будет соответствовать обычному трехсменному графику работы. Однако может оказаться, что выгоднее график работы, составленный на основе оптимального выбора начала каждой из смен. Можно, например, принять такой график работы, когда ло одной смены смещено относительно начала следующей смены на 4 ч. Такой график работы с перекрывающимися сменами показан на рис, 2.8 для случая, когда смены начинаются в 0: 01, 4: 01, 8: 01, 12: 01, 16: 01, 20: 01, причем продолжительность смены составляет 8 ч. Теперь действительно есть возможность идентифицировать церемонные, для чего целесообразна использовать следующие обозначения:

х₁ — число автобусов, выходящих на линию в 0: 01,

х₂ — число автобусов, выходящих на линию в 4: 01,

х₃ - число автобусов, выходящих на линию в 8: 01,

х₄— число автобусов, выходящих на линию ц 12: 01

х₅— число автобусов, выходящих на линию в 16: 01,

х₆ — число автобусов, выходящих на линию в 20: 01.

Рне. 2.8. (Знак * означает минимальную потребность н автобусах для четырехчасовых интервалов.)

Соответствующая рис. 2.8 математическая модель записывается следующим образом:

минимизировать z=х₁+ х₂ +х₃ + х₄+ х₅ +х₆

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

х₁ х₆ ≥ 4 (с 0: 01 до 4: 00),

х₁+ х₂ ≥ 8 (с 4: 00 дj 8: 00),

х₂ +х₃ ≥ 10 (с 8: 01 до 12: 00),

х₃ +х₄ ≥ 7 (с 12: 01 до16: 00),

х₄ +х₅ ≥ 12 (с 20: 01 до 20: 00),

х₅ +х₆ ≥ 4 (о 20: 01 до0: 00),

х_j = 1, 2,.... 6.

Построенная модель приводит к следующему оптимальному решению: требуется только 26 автобусов, 10 из которых должны начинать работу в 4: 01 (х₂), 12 - в 12: 01 (х₄), 4 - в 20: 01 (х₆), причем смены, начинающиеся в 0: 01; 8: 01 и 16: 01, исключаются (т с. х₁ =х₃= х₅ =О). Таким образом, решение, полученное в ус­ловиях возможности выбора начала смен, в отличие от решения, предполагающего использование традиционного трехсменного гра­фика, позволяет уменьшить суточную потребность в автобусах с 30 до 26.

Пример 2.2.4. (Задача о раскрое или минимизации обрезков.)

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

Специализированные закалы выполняються на разрезном уст­ройстве, режущая кромка которого устанавливается в требуемом положении, причем рулон может быть разрезан несколькими спо­собами. На рис. 2.9 показаны три возможных положения режущей кромки. Хотя существуют и другие допустимые положения, мы ограничимся рассмотрением трех вариантов, которые представлены на рис. 2.9 и обозначены через А, В н С. Чтобы выполнить поступив­шие заказы на рулоны нестандартной ширины (5, 7 и 9 футов), можно использовать различные сочетании вариантов А, В и С, например следующие способы:

1) разрезать 300 (стандартных) рулонов по варианту А и 75 Рулонов по варианту В;

2) разрезать 200 рулонов по варианту А н 100 рулонов по варианту С.

Какой из способов лучше? Чтобы ответить на этот вопрос, следует определить величину «отходов», которые будут получаться в каждом из рассматриваемых случаев.

На рис. 2.9 затемненные части стандартных рулонов для вариантов А, В и С представляют собой неиспользуемые остатки, так как ширина их меньше минимальной из заказанных размерен.

Такие рулоны-остатки назовем обрезками. Теперь можно оценить, «качество» каждого из вариантов А, В и С, сравнивай присущие им потери бумаги в виде обрезков. Так как ширина рулона-обрезка в каждом из вариантов различна, оценку экономичности вариантов следует производить не по количеству обрезков, а по общей пло­щади бумаги в отходах. Поэтому при длине стандартного рулона L футов потери бумаги (в фут) составят

при способе 1: 300(4хL)+75(ЗхL)=1425L, фут²,

при способе 2: 200(4хL)+100(1хL) = 900L фут^*.

Полученные значения потерь соответствуют только заштрихо­ванным частим рулонов па рис. 2.9. Заметим, однако, что избыточ­ные рулоны шириной 5, 7 к 9 футов также следует рассматривать. как отходы производства, и соответствующие потери ввести в расчет. Так, при использовании способа 1 вариант А дает 300—200 — 100 избыточных рулонов шириной 7 футов, а вариант В — 7 избыточных рулонов такой же ширины. Соответствующая величии I дополнительных «потерь» составит 175(7 × L) = 1225 фут. При способе 2 не будет излишка рулонов шириной 7 и 9 футов. Однако используемый в нем вариант С дает 200—150=50 избыточных рулонов шириной 5 футов, чему соответствуют дополнительные потери, равные 50(5хL)=250L, фут". В результате получаем

Обшая площадь бумаги, теряемой,

в виде отходов при использовании = 1425L + 225L = 2650L фут²,

способа 1

Общая площадь бумаги, теряемой

в виде отходов при использовании = 900L + 250L = 1150L фут2.

способа 2

Таким образом, способ 2 лучше способа I, так как величина отходов при его реализации оказывается меньше.

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