Менеджмент: конспект лекций
Шрифт:
Надо спланировать перевозки, т. е. выбрать объемы Х ij поставок товара со склада i потребителю j , где i = 1,2,3; j = 1,2,3,4. Таким образом, всего в задаче имеется 12 переменных. Они удовлетворяют двум группам ограничений. Во—первых, заданы запасы на складах:
X 11 + Х 12 + Х 13 + Х 14 = 60,
X 21 + Х 22 + Х 23 + Х 24 = 80,
X 31 + Х 32 + Х 33 + Х 34 = 60.
Во—вторых,
X 11 + Х 21 + Х 31 = 50 ,
X 12 + Х 22 + Х 32 = 40 ,
X 13 + Х 23 + Х 33 = 70 ,
X 14 + Х 24 + Х 34 = 40 .
Итак, всего 7 ограничений типа равенств. Кроме того, все переменные неотрицательны – еще 12 ограничений.
Целевая функция – издержки по перевозке, которые необходимо минимизировать:
F = 2 X 11 + 5 Х 12 + 4 Х 13 + 5 Х 14 + X 21 + 2 Х 22 + Х 23 + 4 Х 24 +
+ +3 X 31 + Х 32 + 5 Х 33 + 2 Х 34 → min.
Кроме обсуждаемой, рассматриваются также различные иные варианты транспортной задачи. Например, если доставка производится вагонами, то объемы поставок должны быть кратны вместимости вагона.
Количество переменных и ограничений в транспортной задаче таково, что для ее решения не обойтись без компьютера и соответствующего программного продукта.
Линейное программирование имеет дело с числовыми переменными. Если вспомнить общую постановку оптимизационной задачи, приведенную в начале главы, то Х – вектор в конечномерном линейном пространстве, А – многогранник в таком пространстве. Рассмотрим несколько задач оптимизации, в которых Х и А имеют иную математическую природу.
3.2.2. Целочисленное программирование
Задачи оптимизации, в которых переменные принимают целочисленные значения, относятся к целочисленному программированию. Рассмотрим несколько таких задач.
Задача о выборе оборудования. На приобретение оборудования для нового участка цеха выделено 20000 долларов США. При этом можно занять площадь не более 38 м 2. Имеется возможность приобрести станки типа А и станки типа Б. При этом станки типа А стоят 5000 долларов США, занимают площадь 8 м 2 (включая необходимые технологические проходы) и имеют производительность 7 тыс. единиц продукции за смену. Станки типа Б стоят 2000 долларов США, занимают площадь 4 м 2 и имеют производительность 3 тыс. единиц продукции за смену. Необходимо рассчитать оптимальный вариант приобретения оборудования, обеспечивающий при заданных ограничениях максимум общей производительности участка.
Пусть Х – количество станков типа А, а У – количество станков
типа Б, входящих в комплект оборудования. Требуется выбрать комплект оборудования так, чтобы максимизировать производительность С участка (в тыс. единиц за смену):С = 7 Х + 3 У → max.
При этом должны быть выполнены следующие ограничения:
по стоимости (в тыс. долларов США)
5 Х + 2 У ≤ 20,
по занимаемой площади (в м 2)
8 Х + 4 У ≤ 38,
а также вновь появляющиеся специфические ограничения по целочисленности, а именно,
Х ≥ 0, У ≥ 0, Х и У – целые числа.
Сформулированная математическая задача отличается от задачи линейного программирования только последним условием целочисленности. Однако наличие этого условия позволяет (в данном конкретном случае) легко решить задачу перебором. Действительно, как ограничение по стоимости, так и ограничение по площади дают, что Х ≤ 4. Значит, Х может принимать лишь одно из 5 значений: 0, 1, 2, 3, 4.
Если Х = 4, то из ограничения по стоимости следует, что У = 0, а потому С = 7 Х = 28.
Если Х = 3, то из первого ограничения вытекает, что У ≤ 2, из второго У ≤ 3. Значит, максимальное С при условии выполнения ограничений достигается при У =2, а именно С = 21 + 6 = 27.
Если Х = 2, то из первого ограничения следует, что У ≤ 5, из второго также У ≤ 5. Значит, максимальное С при условии выполнения ограничений достигается при У =5, а именно С = 14 + 15 = 29.
Если Х = 1, то из первого ограничения имеем У ≤ 7, из второго также У ≤ 7. Значит, максимальное С при условии выполнения ограничений достигается при У = 7, а именно С = 7 + 21 = 28.
Если Х = 0, то из первого ограничения вытекает У ≤ 10, из второго У ≤ 9. Значит, максимальное С при условии выполнения ограничений достигается при У = 9, а именно, С = 27.
Все возможные случаи рассмотрены. Максимальная производительность С = 29 (тысяч единиц продукции за смену) достигается при Х = 2, У = 5. Следовательно, надо покупать 2 станка типа А и 5 станков типа Б.
Задача о ранце . Общий вес ранца заранее ограничен. Какие предметы положить в ранец, чтобы общая полезность отобранных предметов была максимальна? Вес каждого предмета известен.
Есть много эквивалентных формулировок. Например, можно вместо ранца рассматривать космический аппарат – спутник Земли, а в качестве предметов – научные приборы. Тогда задача интерпретируется как отбор приборов для запуска на орбиту. Правда, при этом предполагается решенной предварительная задача – оценка сравнительной ценности исследований, для которых нужны те или иные приборы.