Элементы целочисленного программирования

Специальные задачи линейного программирования Элементы целочисленного программирования Задача целочисленного линейного программирования В большинстве экономических задач параметры управления х1, х2, …, хn принимают целочисленные значения (число единиц продукции, число станков, число компьютеров и т.д.). В связи с этим возникает задача целочисленного линейного программирования. 3 Задача булевского программирования Задача булевского программирования — частный случай задачи целочисленного линейного программирования, где переменные x могут принимать всего лишь два значения — 0 и 1. 4 Методы целочисленного программирования Три группы методов: методы отсечения; комбинаторные методы; приближенные методы. Идея методов отсечения: 1. Вначале задача решается без требования целочисленности. 2. Если полученный оптимальный план целочисленен, то он и является решением задачи. В противном случае в задачу вводится дополнительное ограничение (правильное отсечение), которое должно удовлетворять следующим требованиям: • должно быть линейным; • должно отсекать найденный оптимальный нецелочисленный план; • не должно отсекать ни одного целочисленного плана. 3. Далее задача решается с учетом этого ограничения. После этого в случае необходимости добавляется еще одно ограничение и т.д. 5 Ральф Эдвард Гомори http://www.ralphgomory.com/ 6 Метод Гомори (1958 г.) 1. Сначала используется обычный симплексный метод без наложения условий целочисленности (хi ≥ 0). Полученный оптимальный план будет удовлетворять всем условиям задачи, кроме условия целочисленности. Такой план называется условно оптимальным. 2. Если среди переменных в условно оптимальном плане есть дробные, то составляется дополнительное ограничение (ограничение Гомори), которое как бы отсекает дробную часть допустимых решений, но оставляет в силе все прочие условия, которым должен удовлетворять оптимальный план. Дополнительное ограничение присоединяют к исходным ограничениям задачи. 3. К расширенной системе вновь применяется симплексная процедура. Если и на этот раз оптимальное решение окажется не целочисленным, то добавляется еще дополнительное ограничение и так процесс повторяется до тех пор, пока не будет получено оптимальное целочисленное решение (если оно существует). 7 Метод Гомори (графическая интерпретация) 8 Метод Гомори (графическая интерпретация) 9 Ограничение Гомори Пусть задача линейного программирования имеет конечный оптимум и на последнем шаге ее решения симплекс-методом были получены следующие уравнения, – выражающие в найденном оптимальном решении базисные переменные х1, …, хi, …, хm через свободные переменные хm+1, xm+2, …, xm+I, …, xn Таким образом, оптимальное решение задачи имеет вид: Xopt (β1, …, βi, …, βm, 0, …,0). Предположим, что компонента βi является нецелой. В этом случае неравенство – – правильное отсечение. 10 Дробная часть числа {a} обозначает дробную часть числа а, определенную соотношением: {a} = а – [а], где [а] – целая часть числа а – наибольшее целое число, не превосходящее а. 11 Пример. Задача о капиталовложениях Предлагается n инвестиционных проектов в основной капитал, тщательная экономическая экспертиза которых позволяет получить для каждого из проектов достаточно убедительные экономические оценки ожидаемого эффекта от их реализации c1, c2, …, cn и необходимых капиталовложений p1, p2, …, pn. Общий объем возможных капиталовложений ограничен величиной B. Необходимо так распорядиться имеющимися финансовыми ресурсами, чтобы максимизировать суммарный эффект от инвестиций. 12 Математическая модель 1, если j − й проект следует финансировать, x j ( j = 1, 2, ..., n ) : x j =  0, в противном случае. X = (x1 , x2 ,..., x j ,..., xn ) − инвестиционный план Задача ЦЛП с булевыми переменными: 1 x j =  , j = 1, 2, ..., n 0 n ∑p x j =1 j j ≤B n f ( X ) = ∑ c j x j → max j =1 13 Условие задачи Предлагается пять инвестиционных проектов, тщательная экономическая экспертиза которых позволяет получить для каждого из проектов достаточно убедительные экономические оценки ожидаемого эффекта от их реализации 80, 50, 75, 40, 45 и необходимых капиталовложений 110, 60, 80, 15, 30. Общий объем возможных инвестиций ограничен величиной 200. Необходимо так распорядиться имеющимися финансовыми ресурсами, чтобы максимизировать суммарный эффект от инвестиций. 14 Описание математической модели Переменные: x j ( j = 1, 2, 3, 4, 5) 1, если j − й проект следует финансировать, xj =  0, в противном случае. Ограничение: 110 x1 + 60 x2 + 80 x3 + 15 x4 + 30 x5 ≤ 200 Функция цели: 80 x1 + 50 x2 + 75 x3 + 40 x4 + 45 x5 → max 15 Транспортная задача The Hitchcock-Koopmans transportation problem Фрэнк Лорен ХИЧКОК Тьяллинг Чарльз КУПМАНС Джордж Бернард ДАНЦИГ 17 Транспортная задача Монжа - Канторовича Гаспа́р МОНЖ КАНТОРОВИЧ Леонид Витальевич 18 Общая постановка проблемы Имеется однородный груз известной массы. Груз рассредоточен в нескольких пунктах. Его необходимо доставить в другие пункты, потребность в которых в данном грузе известна. Известна и стоимость доставки единицы груза от каждого пункта отправления к каждому пункту назначения. Задача состоит в том, чтобы установить план перевозок, который потребует минимальных общих издержек. х11, …, хmn – распределение поставок. 19 Материальные потоки транспортной задачи А1, …, Аn – наличие (масса) груза в пункте отправления; В1, …, Вm – потребность в грузе в пунктах назначения; хij – количество поставляемого груза из пункта Аi в пункт Вj; i – номер пункта отправления (i = 1, 2,…, m); j – номер пункта назначения (j = 1, 2, …, n). Сij – стоимость доставки груза (цена, затраты) из пункта i в пункт j. 20 Пример транспортной задачи Ограничения по запасам груза: Ограничения по потребности в грузе: Функция цели: 21 Закрытая и открытая ТЗ 22 Предпосылки алгоритма решения ТЗ • Поскольку модель транспортной задачи содержит (m + n – 1) независимых уравнений, любой ее невырожденный опорный план включает (m + n – 1) переменных с положительным значением. Остальные переменные xij = 0. Из (m · n) возможных маршрутов перевозок в оптимальном плане транспортной задачи содержится не более (m + n – 1) переменных. • Если план (опорный или промежуточный) включает меньше, чем (m + n – 1) положительных переменных, то он называется – вырожденным планом. • В линейном программировании доказывается, что любая транспортная задача имеет оптимальный план (случаи несовместности исключены). 23 Метод потенциалов (Пример) Имеется три пункта отправления, например, металлургические мини-заводы, и четыре пункта назначения, например, машиностроительные заводы. Стоимость (цена) транспортировки единицы груза (в сотнях у.е. за тонну) представлены в таблице: 24 Предварительный анализ Производство равно потребностям, следовательно, имеем закрытую транспортную задачу. 25 Таблица ТЗ в общем виде 26 Этап I. Построение таблицы ТЗ 27 Этап I. 28 Этап II. Составление опорного плана (метод "северозападного угла") 29 Этап III. Оценка оптимальности плана 1) Проверка условия невырожденности: m + n – 1 = NЗК, NЗК – число занятых клеток в опорном (промежуточном) плане. Пример: m + n – 1 = 3 + 4 – 1 = 6; NЗК = 6. 2) Расчет потенциалов vj и ui для каждой занятой клетки по формуле: vj – ui = Cij, в расчетах всегда принимают u1 = 0. Пример: v1 – u1 = С11, v1 – u2 = С21, v2 – u2 = С22, v2 – u3 = С32, v3 – u3 = С33, v4 – u3 = С34, откуда откуда откуда откуда откуда откуда v1 = С11 + u1 = 2 + 0 = 2 –u2 = С21 – v1 = 1 – 2 = –1; u2 = 1 v2 = С22 + u2 = 3 + 1 = 4 u3 = v2 – С32 = 4 – 8 = –4 v3 = С33 + u3 = 13 – 4 = 9 v4 = С34 + u3 = 7 + (–4) = 3 30 Экономический смысл оценок vj и ui Задача, двойственная по отношению к транспортной задаче, состоит в следующем. Требуется максимизировать линейную форму n m j =1 i =1 L = ∑ b j v j − ∑ ai ui при условиях v j − ui ≤ cij , i = 1, 2, ..., m; j = 1, 2, ..., n. Каждому пункту производства Ai ставится в соответствие число ui, а каждому пункту потребления Bj сопоставляется число vj. Величины ui и vj – оценки единицы транспортируемого продукта в соответствующих пунктах. Неравенство означает, что приращение оценки единицы продукта при его перевозке по коммуникации AiBj не должно превышать транспортные расходы cij. 31 Этап III. 3) расчет оценок δij для свободных клеток по формуле: δij = vj – ui – Cij План оптимален, если все δi ≤ 0, и не является оптимальным в противном случае. Пример: δ12 = 4 – 0 – 4 = 0 δ13 = 9 – 0 – 6 = 3 δ14 = 3 – 0 – 10 = –7 δ23 = 9 – 1 – 7 = 1 δ24 = 3 – 1 – 4 = –2 δ31 = 2 – (-4) – 4 = 2 План не оптимален, т.к. не все δij ≤ 0. 32 Этап III. 33 Этап IV. Построение цепи (цикла) перемещения Из положительных оценок δij выбирается максимальная: δij* = max (vj – ui – Cij > 0) Пример: δij* = max (3; 1; 2) = 3 = δ13 Из свободной клетки с оценкой δij* строится цепочка перемещений по правилам: • Цепочку можно строить по горизонтали или вертикали, по ходу часовой стрелки или против хода часовой стрелки. • Цепочка должна закончиться в клетке с оценкой δij*. • Цепочка перемещений строится из свободной клетки с оценкой δij* до одной из занятых клеток, где делается поворот на 90 градусов. После этого снова осуществляется перемещение до занятой клетки и делается поворот на 90 градусов и так далее. Нужно вернуться в клетку, из которой начали перемещение, за наименьшее число поворотов (наиболее короткий путь). 34 Этап IV. 35 Этап V. Означивание цепи перемещения. 36 Этап VI. Построение таблицы для цикла перемещений. Среди значений плана xij отрицательной полуцепи находится минимальное: Q = min (xij)– Значение Q прибавляется к xij означенным «+» и вычитается из xij со знаком «–». В результате для клеток, которые являются вершинами цепи, получаем новый план. Пример: Q = min (90; 80; 80) = 80 37 Этап VII. Составление нового плана. 38 Этап III (2-я итерация). Оценка оптимальности плана 1) Проверка условия невырожденности: m + n – 1 = NЗК Пример: m + n – 1 = 6 ≠ NЗК = 5. План вырожденный. 39 Способ превращения плана в невырожденный Среди занятых клеток (xij > 0) выбираются клетки (фрагмент плана), где план записан по диагонали. В одну из свободных клеток, примыкающим к этим занятым клеткам, записывают «0». Причем среди «конкурирующих» клеток выбирается клетка с наименьшей величиной Cij. Пример: Из клеток (2,2) и (3,1) выбираем клетку (2,2), т.к. C22 < C31 (3 < 4). 40 Этап III (2-я итерация). Расчет потенциалов vj и ui для занятых клеток и оценок δij для свободных: (1, 1): u1 = 0. v1 – u1 = С11, откуда (1, 3): v3 – u1 = С13, откуда (2, 1): v1 – u2 = С21, откуда (2, 2): v2 – u2 = С22, откуда (3, 2): v2 – u3 = С32, откуда (3, 4): v4 – u3 = С34, откуда v1 = С11 + u1 = 2 + 0 = 2 v3 = С13 + u1 = 6 + 0 = 6 –u2 = С21 + v1 = 1 – 2 = –1; u2 = 1 v2 = С22 + u2 = 3 + 1 = 4 –u3 = С32 – v2 = 8 – 4 = 4; u3 = –4 v4 = С34 + u3 = 7 + (–4) = 3 (1, 2): δ12 = v2 – u1 – C12 = 4 – 0 – 4 = 0 (2, 3): δ23 = v3 – u2 – C23 = 6 – 1 – 7 = –2 (3, 1): δ31 = v1 – u3 – C31 = 2 + 4 – 4 = 2 (1, 4): δ14 = v4 – u1 – C14 = 3 – 0 – 10 = –7 (2, 4): δ24 = v4 – u2 – C24 = 3 – 1 – 4 = –2 (3, 3): δ33 = v3 – u3 – C33 = 6 + 4 – 13 = –3 План не оптимален, т.к. не все δij ≤ 0. 41 Этап III (2-я итерация). 42 Этапы IV и V (2-я итерация). Построение и означивание цепи перемещения. У нас только одно положительное δij : δij* = max (vj – ui – Cij > 0) = max (δ31) = 2 = δ31 43 Этапы IV и V (2-я итерация). 44 Этап VI (2-я итерация). Построение таблицы для цикла перемещений. Среди значений плана xij отрицательной полуцепи находим минимальное Q: Q = min (xij)– = min (100; 100) = 100 Прибавляем значение Q к xij, означенным «+», и вычитаем из xij со знаком «–». В результате получаем новый план. 45 Этап VII (2-я итерация). Составление нового плана. 46 Этап III (3-я итерация). Оценка оптимальности плана Проверка условия невырожденности: m + n – 1 = 6 ≠ NЗК = 5. План вырожденный. В таблице много диагональных фрагментов плана, поэтому необходимо найти клетку, в которую целесообразно записать «0»: min (C12, C21, C23, C32) = min(4; 1; 7; 8) = С21. Записываем «0» в клетку с индексом (2, 1) и превращаем план в невырожденный: 47 Этап III (3-я итерация). Расчет потенциалов vj и ui для занятых клеток и оценок δij для свободных: (1, 1): u1 = 0. v1 – u1 = С11, откуда (1, 3): v3 – u1 = С13, откуда (2, 1): v1 – u2 = С21, откуда (2, 2): v2 – u2 = С22, откуда (3, 1): v1 – u3 = С31, откуда (3, 4): v4 – u3 = С34, откуда v1 = С11 + u1 = 2 + 0 = 2 v3 = С13 + u1 = 6 + 0 = 6 –u2 = С21 – v1 = 1 – 2 = –1; u2 = 1 v2 = С22 + u2 = 3 + 1 = 4 –u3 = С31 – v1 = 4 – 2 = 2; u3 = –2 v4 = С34 + u3 = 7 + (–2) = 5 (1, 2): δ12 = v2 – u1 – C12 = 4 – 0 – 4 = 0 (2, 3): δ23 = v3 – u2 – C23 = 6 – 1 – 7 = –2 (3, 2): δ32 = v2 – u3 – C32 = 4 + 2 – 8 = –2 (1, 3): δ14 = v4 – u1 – C14 = 5 – 0 – 10 = –5 (2, 4): δ24 = v4 – u2 – C24 = 5 – 1 – 4 = 0 (1, 4): δ33 = v3 – u3 – C33 = 6 + 4 – 13 = –3 План оптимален, т.к. все δij ≤ 0. 48 Этап III (3-я итерация). 49 Анализ оптимального плана. Согласно оптимальному плану: • 1-й поставщик поставляет 1-му потребителю 10 т и 3-му потребителю – 80 т. • 2-й поставщик поставляет 2-му потребителю все свои запасы, то есть все 100 т. • 3-й поставщик поставляет 1-му потребителю 100 т и 4-му потребителю – 40 т. Стоимость перевозок для оптимального плана (таблица 3): 2·10 + 6·80 + 3·100 + 4·100 + 7·40 = 1 480 у.е. Стоимость перевозок для исходного плана (таблица 1): 2·90 + 1·20 + 3·80 + 8·20 + 13·80 + 7·40 = 1 920 у.е. Улучшение плана в сравнении с исходным: 1 920 – 1 480 = 440 у.е. 50 Составление опорного плана по методу "минимального элемента". Шаг 1. 51 Метод «минимального элемента». Шаг 2 52 Метод «минимального элемента». Шаг 2 53 Метод «минимального элемента». Шаг 2 54 Метод «минимального элемента». Шаг 2 55 Метод «минимального элемента». Шаг 3 Оцениваем стоимость перевозок: 2·10 + 4·80 + 1·100 + 8·20 + 13·80 + 7·40 = 1 920 Стоимость перевозок по методу «северо-западного угла»: 2·90 + 20·1 + 3·80 + 8·20 + 13·80 + 7·40 = 1 920 56 Задача о назначениях Постановка задачи Имеется некоторое число работ и некоторое число исполнителей. Любой исполнитель может быть назначен на выполнение любой (но только одной) работы, но с неодинаковыми затратами. Нужно распределить работы так, чтобы выполнить работы с минимальными затратами. Обычно функция стоимости задается как квадратная матрица C, состоящая из вещественных чисел, а целевую функцию можно записать в виде: 58 Математическая модель Задачу можно представить как задачу линейного программирования: Переменная xij представляет назначение исполнителя на работу , принимая значение 1 если исполнитель назначен на эту работу и 0 в противном случае. 59 Методы решения задачи Задача о назначениях – частный случай транспортной задачи, для которой мощности поставщиков и потребности клиентов равны 1 (и обычно совпадает размерность). Так же как для решения транспортной задачи был модифицирован симплекс-метод и разработан метод потенциалов, так и для задачи о назначениях был создан более краткий метод решения – венгерский метод. 60 Примеры • Организуется рекламная акция, в которой участвуют некоторое количество промоутеров. Мероприятия нужно провести в нескольких районах города. Как распределить промоутеров по районам, чтобы эффективность акции была максимальной? • На предприятии в цеху работают несколько рабочих, которым необходимо изготовить какое-то количество деталей разного вида. Каждый рабочий изготавливает разного вида детали с разным процентом брака. Как распределить заказ деталей по рабочим, чтобы суммарный процент брака был минимален? 61 Примеры Через отдел подготовки крупного издательства проходит множество рукописей книг. Эти рукописи необходимо распределять между сотрудниками. Каждая рукопись может быть охарактеризована оценками по таким критериям, как важность, срочность выполнения, тематика. В свою очередь, сотрудники могут быть охарактеризованы оценками по таким критериям, как качество работы, индивидуальная «пропускная способность», предпочитаемая тематика и т.д. Необходимо так распределить рукописи среди сотрудников, чтобы получить приемлемое качество выполнения всех работ при минимальных ресурсных затратах. 62 Примеры Большая фирма переезжает в новое здание. Возникает необходимость распределить сотрудников по помещениям. С одной стороны, каждый сотрудник выдвигает определенные требования к своим соседям (например, предпочитает некурящих) и к расположению комнаты (например, вблизи от коллег по совместному проекту). С другой стороны, каждое помещение имеет определенные характеристики. Необходимо найти такой вариант распределения, при котором, по меньшей мере, не ухудшился бы психологический климат в коллективе. 63 Пример 1 Некоторая компания имеет четыре сбытовые базы и четыре заказа, которые необходимо доставить различным потребителям. Складские помещения каждой базы вполне достаточны для того, чтобы вместить один из этих заказов. В таблице содержится информация о расстоянии между каждой базой и каждым потребителем. 64 Расстояние от сбытовых баз до потребителей, км Потребители I II III IV A 68 72 75 83 B 56 60 58 63 C 38 40 35 45 D 47 42 40 45 Сбытовая база 65 Требуется: Распределить заказы по сбытовым базам, чтобы общая дальность транспортировки была минимальной. Методическое указание: В задачах о назначении значения общего спроса и общего предложения для всех строк и столбцов равны единице. 66 Описание математической модели Переменные: хij = 1, если сбытовая база i обеспечивает заказ потребителя j (в противном случае хij = 0) Условия-ограничения по предложению: xA I + xA II + xA III + xA IV = 1 xB I + xB II + xB III + xB IV = 1 xC I + xC II + xC III + xC IV = 1 xD I + xD II + xD III + xD IV = 1 (1) (2) (3) (4) Условия-ограничения по спросу: xA I + xB I + xC I xA II + xB II + xC II xA III + xB III + xC III xA IV + xB IV + xC IV + xD I + xD II + xD III + xD IV =1 =1 =1 =1 (5) (6) (7) (8) 67 Описание математической модели Функция цели: 68 · xA I + 72 · xA II + 75 · xA III + 83 · xA IV + + 56 · xB I + 60 · xB II + 58 · xB III + 63 · xB IV + + 38 · xC I + 40 · xC II + 35 · xC III + 45 · xC IV + + 47 · xD I + 42 · xD II + 40 · xD III + 45 · xD IV → min 68 Пример 2. В распоряжении некоторой компании имеется 6 торговых точек 6 продавцов. Из прошлого опыта известно, что эффективность работы продавцов в различных торговых точках неодинакова. Коммерческий директор компании произвел оценку деятельности каждого продавца в каждой торговой точке. Результаты этой оценки представлены в таблице. 69 Объемы продаж, тыс. шт. Торговые точки I II III IV V VI Продавец A B 68 72 75 83 75 69 56 60 58 62 61 59 C 35 38 40 45 25 27 D 40 42 47 45 53 36 E 62 70 68 67 69 70 F 65 63 69 70 72 68 70 Вопрос Как коммерческий директор должен осуществить назначение продавцов по торговым точкам, чтобы достичь максимальный объем продаж? 71 Описание математической модели Переменные: хij = 1, если продавец i назначен на торговую точку j (в противном случае хij = 0) Условия-ограничения по предложению: xA I + xA II + xA III + xA IV + xA V + xA VI = 1 (1) xB I + xB II + xB III + xB IV + xB V + xB VI = 1 (2) xC I + xC II + xC III + xC IV + xC V + xC VI = 1 (3) xD I + xD II + xD III + xD IV + xD V + xD VI = 1 (4) xE I + xE II + xE III + xE IV + xE V + xE VI = 1 (5) xF I + xF II + xF III + xF IV + xF V + xF VI = 1 (6) 72 Описание математической модели Условия-ограничения по спросу: xA I + xB I + xC I + xD I + xE I + xF I = 1 (7) xA II + xB II + xC II + xD II + xE II + xF II = 1 (8) xA III + xB III + xC III + xD III + xE III + xF III = 1 (9) xA IV + xB IV + xC IV + xD IV + xE IV + xF IV = 1 (10) xA V + xB V + xC V + xD V + xE V + xF V = 1 (11) xA VI + xB VI + xC VI + xD VI + xE VI + xF VI = 1 (12) 73 Описание математической модели Функция цели: 68 · xA I + 72 · xA II + 75 · xA III + 83 · xA IV + 75 · xA V + 69 · xA VI + + 56 · xB I + 60 · xB II + 58 · xB III + 62 · xB IV + 61 · xB V + 59 · xB VI + + 35 · xC I + 38 · xC II + 40 · xC III + 45 · xC IV + 25 · xC V + 27 · xC VI + + 40 · xD I + 42 · xD II + 47 · xD III + 45 · xD IV + 53 · xD V + 36 · xD VI + + 62 · xE I + 70 · xE II + 68 · xE III + 67 · xE IV + 69 · xE V + 70 · xE VI + + 65 · xF I + 63 · xF II + 69 · xF III + 70 · xF IV + 72 · xF V + 68 · xF VI → max 74