Орлов А.И. Менеджмент (2003) (1142166), страница 58
Текст из файла (страница 58)
На приобретение оборудования длянового участка цеха выделено 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 станков типа Б.Задача о ранце. Общий вес ранца заранее ограничен.
Какие предметыположить в ранец, чтобы общая полезность отобранных предметов быламаксимальна? Вес каждого предмета известен.Есть много эквивалентных формулировок. Например, можно вместо ранцарассматривать космический аппарат – спутник Земли, а в качестве предметов научные приборы. Тогда задача интерпретируется как отбор приборов для запускана орбиту. Правда, при этом предполагается решенной предварительная задача оценка сравнительной ценности исследований, для которых нужны те или иныеприборы.С точки зрения экономики предприятия и организации производства болееактуальна другая интерпретация задачи о ранце, в которой в качестве «предметов»рассматриваются заказы (или варианты выпуска партий тех или иных товаров), вкачестве полезности – прибыль от выполнения того или иного заказа, а в качествевеса – себестоимость заказа.Перейдем к математической постановке.
Предполагается, что имеется nпредметов, и для каждого из них необходимо решить, класть его в ранец или некласть. Для описания решения вводятся булевы переменные Хk , k = 1,2,…, n (т.е.переменные, принимающие два значения, а именно, 0 и 1). При этом Хk = 1, еслипредмет размещают в ранце, и Хk = 0, если нет, k = 1,2,…, n. Для каждого предметаизвестны две константы: Аk - вес k-го предмета, и Сk - полезность k-го предмета, k= 1,2,…, n . Максимально возможную вместимость ранца обозначим В.Оптимизационная задача имеет видC1 Х1 + С2 Х2 + С3 Х3 + ….
+ СnХn → max ,А1 Х1 + А2 Х2 + А3 Х3 + …. + АnХn ≤ В.В отличие от предыдущих задач, управляющие параметры Хk , k = 1,2,…, n ,принимают значения из множества, содержащего два элемента - 0 и 1.К целочисленному программированию относятся задачи размещения(производственных объектов), теории расписаний, календарного и оперативногопланирования, назначения персонала и т.д. (см., например, монографию [2]).Укажем два распространенных метода решения задач целочисленногопрограммированияМетод приближения непрерывными задачами.
В соответствии с нимсначаларешаетсязадачалинейногопрограммированиябезучетацелочисленности, а затем в окрестности оптимального решения ищутсяцелочисленные точки.Методы направленного перебора. Из них наиболее известен метод ветвейи границ. Суть метода такова. Каждому подмножеству Х множества возможныхрешений Х0 ставится в соответствие число - "граница" А(Х).
При решении задачиминимизации необходимо, чтобы А(Х1) ≥ А(Х2), если Х1 входит в Х2 или совпадаетс Х2 .Каждый шаг метода ветвей и границ состоит в делении выбранного напредыдущем шаге множества ХС на два - Х1С и Х2С. При этом пересечение Х1С иХ2С пусто, а их объединение совпадает с ХС . Затем вычисляют границы А(Х1С ) иА(Х2С) и выделяют "ветвь" ХС+1 - то из множеств Х1С и Х2С, для которого границаменьше. Алгоритм прекращает работу, когда диаметр вновь выделенной ветвиоказывается меньше заранее заданного малого числаДля каждой конкретной задачи целочисленного программирования(другими словами, дискретной оптимизации) метод ветвей и границ реализуетсяпо-своему.
Есть много модификаций этого метода. Однако менеджеру нетнеобходимости вникать в подробности, относящиеся к вычислительнойматематике. Вместе с тем он должен знать о возможностях, предоставляемых емутеорией оптимизации.3.2.3. Теория графов и оптимизацияОдин из разделов дискретной математики, часто используемый припринятии решений - теория графов (см., например, учебные пособия [3,4]).
Граф это совокупность точек, называемых вершинами графа, некоторые из которыхсоединены дугами (дуги называют также ребрами). Примеры графов приведены нарис.5.Рис.5. Примеры графов.На только что введенное понятие графа "навешиваются" новые свойства.Исходному объекту приписывают новые качества. Например, вводится ииспользуется понятие ориентированного графа. В таком графе дуги имеютстрелки, направленные от одной вершины к другой. Примеры ориентированныхграфов даны на рис.6.Рис.6. Примеры ориентированных графов.Ориентированный граф был бы полезен, например, для иллюстрацииорганизации перевозок в транспортной задаче.
В экономике дугамориентированного или обычного графа часто приписывают числа, например,стоимость проезда или перевозки груза из пункта А (начальная вершина дуги) впункт Б (конечная вершина дуги).Рассмотрим несколько типичных задач принятия решений, связанных соптимизацией на графах.Задача коммивояжера. Требуется посетить все вершины графа ивернуться в исходную вершину, минимизировав затраты на проезд (илиминимизировав время).Исходные данные здесь - это граф, дугам которого приписаныположительные числа - затраты на проезд или время, необходимое дляпродвижения из одной вершины в другую. В общем случае граф являетсяориентированным, и каждые две вершины соединяют две дуги - туда и обратно.Действительно, если пункт А расположен на горе, а пункт Б - в низине, то времяна проезд из А в Б, очевидно, меньше времени на обратный проезд из Б в А.Многие постановки экономического содержания сводятся к задачекоммивояжера. Например:- составить наиболее выгодный маршрут обхода наладчика в цехе(контролера,охранника,милиционера),отвечающегозадолжноефункционирование заданного множества объектов (каждый из этих объектовмоделируется вершиной графа);- составить наиболее выгодный маршрут доставки деталей рабочим илихлеба с хлебозавода по заданному числу булочных и других торговых точек(парковка у хлебозавода).Задача о кратчайшем пути.
Как кратчайшим путем попасть из однойвершины графа в другую? В терминах производственного менеджмента: каккратчайшим путем (и, следовательно, с наименьшим расходом топлива и времени,наиболее дешево) попасть из пункта А в пункт Б? Для решения этой задачикаждой дуге ориентированного графа должно быть сопоставлено число - времядвижения по этой дуге от начальной вершины до конечной. Рассмотрим пример(рис.7).57112412245354Рис.7.
Исходные данные к задаче о кратчайшем пути.Ситуацию можно описать не только 6ориентированным графом с весами,3 но и таблицей (табл.7). В этой таблице двум вершинам –приписанными дугам,началу пути и концу пути – ставится в соответствие время в пути. В табл.7рассматриваются пути без промежуточных остановок. Более сложные маршрутысоставляются из элементарных отрезков, перечисленных в табл.4.Начало дуги1122333556Таблица 4.Исходные данные к задаче о кратчайшем пути.Конец дугиВремя в пути27314461255263224553Спрашивается в задаче: как кратчайшим путем попасть из вершины 1 ввершину 4?Решение. Введем обозначение: С(Т) - длина кратчайшего пути из вершины1 в вершину Т.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
