Математические модели и их классификация

Введение. Классификация математических моделей. Чтобы составить математическую модель задачи необходимо: • Определить переменные данной задачи; • Определить ограничения, которые накладываются на переменные по условию задачи; • Определить цель, то есть целевую функцию задачи. Классификацию можно рассматривать по следующим элементам математической модели: исходным данным, искомым переменным, зависимостям, описывающим целевую функцию и ограничения. Исходные данные Переменные Зависимости Задача Обозначения Детерминированные Непрерывные Целочисленные Непрер.,целочисл. Линейные Линейные Нелинейные Лин. прогр-я. Целоч.прогр-я Нелин. прогр-я ЛП ЦЧП НЛП Случайные Непрерывные Линейные Стохастич.прогр-я СТП Исходные данные, которые заданы определенными постоянными величинами, называются детерминированными. Исходные данные, как например, имеющиеся ресурсы, производительность оборудования и другие, которые зависят от ряда случайных факторов (своевременности поставки ресурсов, исправности оборудования и т.д.), называются случайными величинами. Переменные могут быть непрерывными и дискретными. Непрерывными называются такие величины, которые в заданном интервале могут принимать любые значения, т.е. такие величины являются результатами измерений: масса добываемого угля, объем выпуска ткани и т.д. Дискретными или целочисленными называются такие величины, которые могут принимать только целые значения, т.е. такие величины являются результатом счета: количество машин, людей, зданий – нет смысла говорить о 0,3 паровоза и т.д. Зависимости между переменными в целевой функции и в ограничениях могут быть линейными и нелинейными. Сочетание различных элементов модели приводит к различным классам задач оптимизации. Различные классы задач требуют разных методов решения и как следствие разных программных средств. Наиболее распространенными задачами оптимизации, возникающими в экономике, планировании, управлении, являются задачи ЛП. Задачи оптимизации, которые требуют решения в технических системах, как правило, являются нелинейными. Раздел: Линейное программирование Построение математических моделей Линейное программирование (ЛП) – это наука о методах исследования и нахождения экстремальных значений линейной функции, на неизвестные которой наложены линейные ограничения. Эта линейная функция называется целевой. Ограничения, записанные с помощью неравенств – системой ограничений. Направление оптимизации целевой функции (max или min ) называется критерием оптимальности. В общем виде математическая модель задачи ЛП может быть записана: max Z = C1X1 + C2X2 + … + CnXn (min) При ограничениях: { a11x1 + a12x2 + … + x1nxn ≤ b1 a21x1 + a22x2 + … + x2nxn ≤ b2 … am1x1 + am2x2 + … + xmnxn ≤ bm x1 , x 2 , … , xn ≥ 0 n либо max Z = Σ cj xj (min) j=1 n ____ ____ при ограничениях Σ аij хj ≤bi ; хj ≥0 (i = 1,m ; j=1 , n) j=1 Допустимым решением (планом) задачи ЛП можно считать вектор х =(х1, х2, …, хn), удовлетворяющий системе ограничений. Множество допустимых решений образуют область допустимых решений. Допустимое решение, при котором целевая функция достигает своего экстремального значения (max или min), называется оптимальным. Существует два способа решения задач ЛП. Графический способ (используется если модель содержит только две переменные): • Построить прямые соответствующие системе ограничений; • Отметить ОДР, удовлетворяющую всем ограничениям системы; • Нанести на график ряд параллельных прямых, соответствующих уравнению целевой функции при различных возрастающих (убывающих) значениях целевой функции. Последняя точка, которую проходит прямая, смещаясь в область недопустимых решений, и будет оптимальной. И второй способ решения – алгебраический. Он используется для решения задач с любым количеством перемнных. Пример: Фабрика выпускает два вида красок: для наружных работ и для внутренних работ. Для производства красок используется два исходных продукта А и В. Исходный продукт Расход исходного продукта (т) Максимально возможный запас (т) Краска 1 Краска 2 А 1 2 6 В 2 1 8 Суточный спрос на краску 2 никогда не превышает спроса на краску 1 более чем на одну тонну. Спрос на краску 2 никогда не превышает двух тонн в сутки. Оптовые цены на краску 1 – 3 тыс. ден. ед., на краску 2 – 2 тыс. ден. ед. Какое количество краски должна производить фирма, чтобы доход был максимальным? Для построения мат. модели обозначим: 1. х1 – суточный объем производства краски 1 (т) х2 – суточный объем производства краски 2 (т). 2. Расход исходного продукта ≤ максимального запаса, это приводит к первым двум ограничениям. Ограничения на величину спроса на продукцию приводят к следующим двум ограничениям: { х1 + 2 х2 ≤ 6 2х1 + х2 ≤ 8 ; х1, х2 ≥ 0 Х2 – х1 ≤ 1 х2 ≤ 2 3. Суточный доход от продажи краски 1 вида составит 3 тыс. д.е., краски 2 вида – 2 тыс.д.е. Общий доход будет равен сумме доходов от продаж двух видов краски, который требуется максимизировать. Поэтому целевая функция будет иметь вид: max Z = 3x1 + 2 x2 Решим задачу графическим способом. Отобразим на графике все прямые, соответствующие ограничениям модели. Найдем область допустимых решений, удовлетворяющую всем ограничениям модели. Эта область - многоугольник ABCDEF. Построим ряд параллельных прямых, соответствующих уравнению целевой функции, например: 3x1+2x2=6, 3x1+2x2=12. Это так называемые линии уровня. Последняя точка , которую проходят прямые, двигаясь по направлению возрастания и смещаясь в область недопустимых решений, будет точка С – оптимальная. Т.С находится на пересечении двух прямых (1) и (2), поэтому решив систему этих двух уравнений, найдем координаты т.С. { х1 + 2 х2 = 6 2х1 + х2 = 8 { х1 = 6 - 2 х2 2(6 - 2 х2) + х2 = 8 … { х1 = 10/3 х2 = 4/3 Тогда т. С имеет координаты (10/3;4/3) и Z = 3 (10/3) + 2 (4/3) = 38/3 Оптимальному решению всегда соответствует одна из угловых точек пространства решений. Оптимальной точкой может быть одна, может быть несколько альтернативных оптимальных точек, или математическая модель может не иметь решений. Анализ математической модели на чувствительность после нахождения оптимального решения. Задача 1: На сколько сократить или увеличить запасы ресурсов? Прямые, проходящие через оптимальную точку, называются связывающими и активными ограничениями, а ресурсы, соответствующие им, относятся к дефицитным (используются полностью). Пример: Необходимо определить предельно допустимое увеличение запаса дефицитного ресурса, позволяющее улучшить найденное оптимальное решение, и предельно допустимое снижение запаса недефицитного ресурса, не изменяющее полученного оптимального решения. Передвигая ограничение (1) вверх до т.G, мы можем увеличить запас ресурса 1. Подставим координаты точки G (3;2) в (1) ограничение: 3 + 2 * 2 = 7 (т.) - максимально возможный запас 1 ресурса. При этом значение целевой функции также изменится, т.к. т.G станет оптимальной. Z = 3 * 3 + 2 * 2 = 13 (тыс. ден. ед.) Ограничение (2) можем передвигать до т. J, дальнейшее передвижение уже не влияет на область допустимых значений. Подставим координаты точки J (6;0) во (2) ограничении: 2 * 6 + 0 = 12 (т.) – максимально возможный запас 2 ресурса. При этом значение z изменится, т.к. оптимальной будет т.J, подставим ее координаты в целевую функцию: Z = 3 *6 + 0 = 18 (тыс. ден. ед.) (4) ограничение соответствует недефицитному ресурсу, поэтому рассмотрим его уменьшение, не изменяющее оптимального решения. Уменьшение спроса на краску 1 до величины 4/3 никак не повлияет на оптимальное решение. Полученное оптимальное решение не изменится, если спрос на краску 1 превысит спрос на краску 2 не менее чем на 2 тонн. ресурс Тип ресурса Максимальное изменение запаса ресурса ∆ V ∆ Z максимальное изменение дохода 1 Дефицитный 7 - 6 = 1 13 – 38/3 = 1/3 2 Дефицитный 12 – 8 = 4 18 – 38/3 = 16/3 3 Не дефицитный - 2 – 1 = - 3 4 Не дефицитный 4/3 – 2 = - 2/3 Задача 2 (задача анализа математической модели на чувствительность): Увеличение какого объема ресурсов более выгодно? Для этого вводятся характеристика ценности каждой допустимой единицы ресурса. Уi = ∆ Zi ∆ Vi Y1 = 1/3 тыс. д. е. Y2 = 4/3 тыс. д. е. Y3 = 0 Y4 = 0 При вложении дополнительных средств, в первую очередь, они должны быть направлены на увеличение ресурса 2. Задача 3: В каких пределах допустимо изменение коэффициентов целевой функции? Изменение коэффициентов целевой функции можно рассчитать, вращая прямую, соответствующую целевой функции, вокруг оптимальной точки, по часовой или против часовой стрелки. Рассмотрим изменение коэффициента С1 при переменной X1: Z = С1x1 + 2 x2. Значение с1 можно увеличивать, пока прямая, соответствующая целевой функции не совпадет с ограничением (2) по часовой стрелке или уменьшать, пока прямая, соответствующая целевой функции не совпадет с ограничением (1) против часовой стрелки. Приравнивая тангенсы углов наклонов целевой функции и соответствующих ограничений: с1/2=1/2, найдем минимальное значение с1=1. с1/2=2/1, найдем максимальное значение с1=4. Таким образом, интервал изменения с1, в котором точка по-прежнему остается единственной оптимальной, определяется интервалом: 1<=c1<=4. Как только коэффициент с1 становится меньше 1, оптимальной будет точка D. Если коэффициент с1 становится больше 4, оптимальной будет точка B. Те же вычисления можно выполнить и для коэффициента с2: Z = 3x1 + с2 x2. Алгебраический метод решения задач ЛП. Стандартная форма линейных оптимизационных моделей Алгебраический метод решения задач ЛП называется симплекс-методом. Прежде чем использовать симплекс-метод для решения линейных моделей, их необходимо привести к стандартной форме: 1. Все ограничения записываются в виде равенств с неотрицательной правой частью; 2. Значения всех переменных неотрицательны; 3. Целевая функция подлежит максимизации или минимизации. 1. Исходное ограничение можно представить в виде равенства, прибавляя остаточную переменную к правой части (≤) или вычитая избыточную переменную из правой части (≥). Если исходное ограничение:x1 +2x2 ≤ 6, то в стандартной форме: x1 +2x2 + S1 = 6, S1 ≥ 0 – остаточная переменная Если исходное ограничение:3x1 +2x2 ≥ 5, то в стандартной форме: 3x1 +2x2 - S2 = 5, S1 ≥ 0 – избыточная переменная Правую часть необходимо сделать неотрицательной, умножая правую и левую части на (-1). При этом знак меняется на противоположный. Если исходное ограничение:2x1 - x2 ≤ -5, то в стандартной форме: - 2x1 + x2 ≥ 5 - 2x1 + x2 - S1 ≥ 5 2. Любую переменную уi, не имеющую ограничения в знаке, можно представить в виде разности двух неотрицательных переменных: yi = yi‘– yi” ; yi’, yi”≥ 0 Такую подстановку необходимо сделать во всех ограничениях, которые содержат уi и в выражении для целевой функции. Особенность уi’ и уi” в том, что при любом допустимом решении только одна из этих переменных принимает положительное решение, то есть если уi’>0, то уi”=0 и наоборот. 3, Максимизация функции эквивалентна минимизации той же функции взятой с противоположным знаком. max Z= 5 х1 + 2 х2 + 3 х3 min (-Z)= - 5 х1 - 2 х2 - 3 х3 Эквивалентность означает, что при одной и той же совокупности ограничений оптимальные значения х1, х2, х3 будут одинаковы при различных знаках целевой функции. Пример: Привести к стандартной форме: min Z= 2 х1 + 3 х2 { х1 + х2 =10 - 2 х1 + 3 х2 ≤ -5 ; х1 не ограничено в знаке, х2 ≥ 0 7 х1 - 4 х2 ≤ 6 { х1 + х2 =10 2 х1 - 3 х2 ≥ 5 ; 7 х1 - 4 х2 ≤ 6 { х1 + х2 =10 2 х1 - 3 х2 - S2 = 5 ; 7 х1 - 4 х2 + S3 = 6 x1 = x1’ – x1” ; x1’, x1” ≥ 0 Z = 2x1’ – 2x1” + 3 x 2 { x1’ – x1” + х2 =10 2 x1’ – 2 x1” - 3 х2 - S2 = 5 ; x1’, x1”, x2, S3, S2 ≥ 0 7 x1’ – 7 x1” - 4 х2 + S3 = 6 Симплекс-метод Графический метод используется только для решения задач с двумя переменными. Для большего числа переменных используется алгебраический симплекс-метод. Процесс носит итерационный характер: вычисления повторяются, пока не будет найдено оптимальное решение. Нахождение оптимального решения начинается с исходной, допустимой угловой точки (обычно начала координат). Все переходы осуществляются к смежным угловым точкам, каждая из которых предварительно проверяется на оптимальность. Рассмотрим мат. модель, приведенную к стандартной форме, n – количество переменных, m - количество ограничений. Z = 3 х1 + 2 х2 + 0S1 + 0S2 + 0S3 + 0S4 { х1 + 2х2 + S1 = 6 2 х1 + х2 + S2 = 8 - х1 + х2 + S3 = 1 х2 + S4 = 2 х1, х2 , S1, S2, S3, S4 ≥ 0 В данном примере n = 6, m = 4, (n - m) = 2 Каждой угловой точке соответствует (n-m) нулевых переменных. Остальные переменные соответственно ненулевые. Нулевые переменные Ненулевые переменные A B C D E F х1 х2 S2 х2 S2 S1 S4 S1 S4 S3 S3 х1 S1 S2 S3 S4 S1 х1 S3 S4 x2 х1 S3 S4 x2 х1 S3 S2 x2 х1 S1 S2 х2 S4 S1 S2 Переменные, имеющие нулевые значения, называются небазисными, а остальные – базисные. При переходе от одной угловой точки к другой меняется состав базисных и небазисных переменных. Включаемой переменной называется небазисная переменная, которая будет включена в базисные на следующей итерации. Исключаемая переменная – базисная переменная, которая исключается из множества базисных на следующей итерации. Пусть модель содержит m-уравнений и n неизвестных, тогда (n – m) переменных должны быть равны нулю. Если базисное решение удовлетворяет требованию неотрицательности правых частей ограничений, оно называется допустимым базисным решением. Вычислительные процедуры симплекс-метода: 0. определить начальное допустимое базисное решение, приравнивая к нулю (n–m) небазисных переменных. 1. из числа небазисных переменных выбрать включаемую в новый базис переменную увеличение которой обеспечит улучшение значения целевой функции. Если такой переменной нет, то значение оптимально и решение заканчивается, иначе переходим к следующему шагу. 2. из числа переменных текущего базиса выбрать исключаемую переменную. 3. найти новое базисное решение и перейти к шагу 1. Рассмотрим предыдущий пример: в качестве начального решения используется решение, в котором две (6-4) переменные принимаются равными нулю. Если взять x1=x2=0, это обеспечит допустимость начального базисного решения: s1=6, s2=8,s3=1,s4=2. Данное решение соответствует точке A(началу координат) на графике. Занесем все данные в симплекс-таблицу. Симплекс-таблица: Базовые переменные x1 x2 S1 S2 S3 S4 Решение Z S1 -3 1 -2 2 1 6 S2 2 1 1 8 ← ведущая строка S3 S4 -1 1 1 1 1 1 2 ↑ ведущий столбец S2 - исключаемая х1 – включаемая Включаемая переменная в задаче max (min) - небазисная переменная являющаяся в Z уравнении наименьшим (наибольшим) коэффициентом; в случае равенства нескольких коэффициентов выбор делается произвольно. Если все коэффициенты неотрицательны (неположительны) – полученное решение есть оптимальное (условие оптимальности). Условие допустимости: в качестве исключаемой переменной при max (min) выбирается базисная переменная, для которой отношение постоянной в правой части соответствующего ограничения к положительному коэффициенту ведущего столбца – минимально, а в случае равенства нескольких отношений выбор делается произвольно. Поиск нового базисного решения осуществляется по методу Гаусса-Жордана: • новая ведущая строка = предыдущая ведущая строка / ведущий элемент; • новое уравнение = предыдущее уравнение – (коэффициент ведущего столбца предыдущего уравнения)*(новая ведущая строка) Базовые переменные x1 x2 S1 S2 S3 S4 Решение Z -1/2 3/2 12 S1 3/2 1 -1/2 2 2:3/2=4/3 Х1 1 1/2 1/2 4 4:1/2=8 S3 S4 3/2 1 1/2 1 1 5 2 5:3/2=10/3 2:1=2 Z: _ -3 -2 -3 -3/2 -3/2 -12 -1/2 3/2 12 S1: _ 1 2 1 6 1 1/2 1/2 4 3/2 1 -1/2 2 На следующей итерации – x2 – включаемая, s1 – исключаемая переменные. Итерационный процесс будет продолжаться, пока в z-строке (в задаче max) все переменные не станут положительными. Анализ математической модели на чувствительность по оптимальной симплекс-таблице. Из оптимальной симплекс-таблицы можно получить следующую информацию: • оптимальное решение; • статус ресурса (дефицитный ресурс или нет); • ценности ресурса; • изменение запасов ресурса • изменение коэффициентов целевой функции. Информация по первым трем пунктам непосредственно берется из симплекс-таблицы; для четвертого пункта требуются дополнительные вычисления. Базисные переменные Z x1 x2 S1 S2 S3 S4 Решение Z 1 1/3 4/3 38/3 Х2 1 2/3 -1/3 4/3 Х1 1 -1/3 2/3 10/3 S3 S4 -1 -2/3 1 1/3 1 1 3 2/3 1. x1=10/3; x2=4/3; Z=38/3; Полученные значения приводятся в столбце решений. Переменные, отсутствующие в столбце базисных переменных, имеют нулевое значение. 2. Статус ресурса можно установить по значениям остаточных переменных. Положительное значение остаточной переменной указывает на неполное использование исходного ресурса (недефицитный). S1 и S2 – дефицитные ресурсы S3 = 3 и S4 = 2/3 – недефицитные ресурсы 3. Ценность ресурса характеризуется величиной улучшения оптимального значения Z, приходящегося на единицу прироста объема данного ресурса. Ценности ресурсов определяются по значениям коэффициентов при переменных начального базиса оптимальной симплекс-таблицы: y1=1/3; y2=4/3; y3=0; y4=0. Несмотря на то, что ценности ресурсов представляются в стоимостном выражении, их нельзя отождествлять с действительными ценами на соответствующие ресурсы. Характеризуют ценность ресурса только относительно полученного оптимального решения. Для ценности ресурсов используют такие термины, как скрытая цена или двойственная оценка. 4. Изменение запасов ресурсов: Предположим, запас первого ресурса составит 6 + ∆1 тонн. Если выполнить все необходимые вычисления с новым запасом ресурсов для первого ограничения, то в оптимальной симплекс-таблице в столбце решений мы получим следующие значения: Базовые переменные Z x1 x2 S1 S2 S3 S4 Решение Z 1 1/3 4/9 38/3+ ∆1*1/3 Х2 1 2/3 -1/3 4/3+∆1*2/3 Х1 1 -1/3 2/3 10/3+∆1*(-1/3) S3 S4 -1 -2/3 1 1/3 1 1 3 - ∆1 2/3 - ∆1*2/3 Коэффициенты при ∆1 берутся из столбца S1, так как S1 соответствует первому ограничению, для которого мы ищем изменение запаса ресурса. ∆1 не может принимать значений, при которых какая-либо из базисных переменных становится отрицательной, то есть должно выполнятся условие неотрицательности правых частей ограничений оптимальной симплекс-таблицы. { 4/3 + (2/3) ∆1 ≥ 0 10/3 – (1/3) ∆1≥ 0 ; 3- ∆1 ≥0 2/3 – (2/3) ∆1 ≥ 0 { (2/3) ∆1 ≥ -4/3 (-1/3)∆1 ≥-10/3 ; -∆1 ≥-3 (-2/3) ∆1≥-2/3 { ∆1 ≥ -2 ∆1 ≤ 10 ∆1 ≤ 3 ∆1 ≤ 1 -2 ≤ ∆1 ≤ 1 6 – 2 = 4 тонн – min запас 1 ресурса 6 + 1 = 7 тонн – max запас 1 ресурса Любое значение ∆1 выходящее за пределы указанного интервала, приведет к недопустимости решения и новой совокупности базисных переменных. Значение Z изменяется по формуле 38/3+(1/3) ∆1 и при ∆1=1 Z=13 тысяч ден. ед. Рассмотрим изменение запаса второго ресурса ∆2 : 38/3 + (4/3) ∆2 { 4/3 – (1/3) ∆2 ≥ 0 10/3 + (2/3) ∆2 ≥ 0 3 + ∆2 ≥ 0 2/3 + (1/3) ∆2 ≥ 0 5. Диапазон изменения коэффициентов целевой функции: Предположим, что коэффициент при х1 изменится на (3+∂1), то Z = (3+∂1)х1+2х2. Если провести все необходимые вычисления до получения оптимальной симплекс-таблицы, то последнее Z уравнение будет таким: x1 x2 S1 S2 S3 S4 Решение Z 1/3-(1/3) ∂1 4/3+(2/3) ∂1 38/3+ (10/3) ∂1 Коэффициенты при ∂1 равны коэффициентам при соответствующих переменных в х1 уравнении симплекс-таблицы. { 1/3 – (1/3) ∂1 ≥ 0 Для максимизации: ≥ 4/3 + (2/3) ∂1 ≥ 0 ; Для минимизации: ≤ { ∂1 ≤ 1 ∂1 ≥ -2 ; 3-2=1 – min значение коэффициента 3+1=4 – max значение коэффициента При 1 ≤ С1 ≤ 4 оптимальные значения переменных остаются неизменными Предположим, что коэффициент при х2 изменится на (2+∂2), то Z = 3х1+(2+∂2)х2. Значение целевой функции будет меняться по правилу: 38/3+ (4/3) ∂2 { 1/3 + (2/3) ∂2 ≥ 0 4/3 - (1/3) ∂2 ≥ 0 ; { ∂2 ≥ -1/2 ∂2 ≤ 4 ; 2-1/2= 3/2 - min значение коэффициента 2+4=6 - max значение коэффициента Искусственное начальное решение. М-метод. Двухэтапный метод. Если ограничения модели имеют знаки ≤, то начальное допустимое базисное решение состоит только из остаточных переменных, если же в ограничениях присутствуют знаки ≥ или = , нельзя сразу же получить допустимое базисное решение. Пример: min Z = 4 х1 + х2 { 3х1 + х2 = 3 4х1 + 3х2 ≥ 6 х1 + 2х2 ≤4 х1, х2 ≥ 0 { 3х1 + х2 = 3 4х1 + 3х2 - х3 = 6 х1 + 2х2 + х4 = 4 х1, х2 , х3, х4 ≥ 0 n=4, m=3. Количество нулевых (n-m)=1. В данной ситуации нельзя быть уверенным в том, что при нулевом значении какой-либо переменной, все базисные переменные будут неотрицательными, поэтому вводятся искусственные переменные, которые выполняют роль остаточных в ограничениях со знаком ≥ или =. Эти переменные необходимы только для получения стартовой точки, в конечном оптимальном решении они должны принимать нулевые значения. Существует два метода с использованием искусственных переменных: 1. М-метод (метод больших штрафов); 2. двухэтапный метод. М-Метод R1, R2 – искусственные переменные, вводятся только в те ограничения, в которых нет остаточных переменных, т.е. имеющие знаки >=, =. Рассмотрим тот же пример. { 3х1 + х2 + R1 = 3 4х1 + 3х2 - х3 + R2= 6 х1 + 2х2 + х4 = 4 х1, х2 , х3, х4 , R1, R2 ≥ 0 6-3=3 х1, х2 , х3 =0; х4 = 4; R1= 3; R2 = 6 – начальное допустимое базисное решение. За использование искусственной переменной в составе целевой функции вводится «штраф»: достаточно большой положительный коэффициент М в задаче min и достаточно большой по абсолютному значению отрицательный коэффициент в задаче max. Z = 4х1 + х2 + M R1 + M R2 Так как М достаточно большое положительное число, то в задаче минимизации, в оптимальном решении, переменные R1 и R2 обратятся в ноль. Если решается задача максимизации, то этим переменным в целевой функции приписывается большой по абсолютной величине отрицательный коэффициент. Так как в целевой функции присутствуют базисные переменные R1 и R2 , их необходимо выразить через небазисные переменные, то есть из 1-го и2-го ограничений, и подставить в целевую функцию. R1 =3 - 3х1 - х2 R2= 6 - 4х1 - 3х2 + х3 Z = 4х1 + х2 + M (3 - 3х1 - х2) + M (6 - 4х1 - 3х2 + х3) = (4 - 7M) х1 + (1 – 4M) х2 + + Mх3+ 9M Z - (4 - 7M) х1 - (1 – 4M) х2 - Mх3 = 9M Z+(-4+7M)x1+(-1+4M)x2-Mx3=9M Итерация 0: Баз. Пер. х1 х2 х3 R1 R2 х4 Решение Z 7 М - 4 4 М - 1 - М 9 М R1 3 1 1 3 R2 4 3 -1 1 6 х4 1 2 1 4 Итерация 3 - Оптимальная таблица: Баз. Пер. х1 х2 х3 R1 R2 х4 Решение Z 7/5 – М - М -1/5 17/5 х1 1 2/5 -1/5 2/5 х2 1 -1/5 3/5 9/5 х3 1 1 -1 1 1 х1 = 2/5 ; х2 = 9/5 ; x3=1; Z = 17/5 Значения R1, R2=0 В оптимальном решении искусственные переменные имеют нулевое значение. Если хотя бы одна искусственная переменная имеет положительное значение в оптимальном решении – решение недопустимо. Недостаток М-метода заключается в том, что из-за больших коэффициентов М процесс вычисления может стать нечувствительным к значениям исходных коэффициентов. Двухэтапный метод (не использует коэффициенты М) 1 этап: Вводятся искусственные переменные, записывается новая целевая функция, соответствующая минимизации суммы искусственных переменных. Задача решается симплекс-методом. Если полученное решение новой целевой функции равно нулю, то исходная задача имеет допустимое решение. Осуществляется переход к этапу 2. Если на первом этапе значение целевой функции не равно 0, то исходное задача не имеет допустимых решений, процесс вычисления заканчивается. 2 этап: полученное оптимальное решение на первом этапе используется в качестве начального решения на втором этапе при исходной целевой функции. Значения искусственных переменных не используются. Рассмотрим тот же пример и решим двухэтапным методом. min Z = 4 х1 + х2 { 3х1 + х2 + R1 = 3 4х1 + 3х2 - х3 + R2= 6 х1 + 2х2 + х4 = 4 х1, х2 , х3 =0; х4 = 4; R1= 3; R2 = 6 – начальное допустимое базисное решение. I этап: r = R1+ R2 { 3х1 + х2 + R1 = 3 4х1 + 3х2 - х3 + R2= 6 х1 + 2х2 + х4 = 4 Т.к. в состав целевой функции входят базисные переменные, выразим базисные переменные через небазисные и подставим в целевую функцию. r = R1 + R2 = 3 - 3х1 - х2 + 6 - 4х1 - 3х2 + х3 = - 7х1 - 4х2 + х3 + 9 r + 7х1 + 4х2 - х3 = 9 итерация 0: Баз. Пер. Х1 х2 х3 R1 R2 х4 Решение r 7 4 - 1 9 R1 3 1 1 3 R2 4 3 -1 1 6 х4 1 2 1 4 Оптимальная таблица 1 этапа: Баз. Пер. Х1 х2 х3 R1 R2 х4 Решение r -1 -1 R1 1 1/5 3/5 -1/5 3/5 R2 1 -3/5 -4/5 3/5 6/5 х4 1 1 -1 1 1 Так как r=0, то переходим к этапу 2. Этап II: Min Z = 4x1+ x2 { х1 + (1/5)х3 = 3/5 х2 – (3/5)х3 = 6/5 х3 + х4 = 1 х1, х2, х3, х4 ≥ 0 4 - 3=1, если х3 = 0, то х1 = 3/5, х2 = 6/5, х4 = 1 – начальное допустимое базисное решение Выразим базисные переменные через небазисные: х1 =3/5 – (1/5) х3 х2= 6/5 + (3/5)х3 Z = 4 ( 3/5 – (1/5) х3 ) + ( 6/5 + (3/5) х3 ) = (-1/5) х3 + 18/5 Z + (1/5) х3 = 18/5 Баз. Пер. Х1 х2 х3 х4 Решение Z 1/5 18/5 х1 1 1/5 3/5 х2 1 -3/5 6/5 х4 1 1 1 Оптимальную таблицу получим на следующей итерации: х1 = 2/5, х2 = 9/5, Z = 17/5 Количество итераций в М-методе и в двухэтапном методе всегда одинаково, и между таблицами имеется взаимнооднозначное соответствие. Рассмотрим примеры: Необходимо ли использование искусственных переменных для получения начального решения в следующих задачах? 1. Max z=x1+x2 2x1+3x2=5 7x1+2x2<=6 x1,x2>=0 2.min z=x1+x2+x3+x4 2x1+x2+x3=7 4x1+8x2+x4=8 х1,x2,x3,x4>=0 Особые случаи применения симплекс-метода 1. Вырожденность 2. Альтернативное оптимальное решение 3. Неограниченные решения 4. Отсутствие допустимых решений Вырожденность Если по условию допустимости любая переменная может быть исключена из базиса и выбор делается произвольно, то на следующей итерации, по крайней мере, одна из базисных переменных становится равной нулю. В этом случае говорят, что решение является вырожденным. С практической точки зрения данная ситуация объясняется наличием в модели избыточных ограничений. Пример: max Z = 3 х1 + 9х2 { х1 + 4 х2 ≤ 8 - (1) х1 + 2 х2 ≤ 4 - (2) x1 , x 2 ≥ 0 0 итерация: Баз. Пер. Х1 х2 х3 х4 Решение Z - 3 - 9 х3 1 4 1 8 х4 1 2 1 4 1 итерация Баз. Пер. Х1 х2 х3 х4 Решение Z - 3/4 9/4 18 х2 1/4 1 1/4 2 х4 1/2 -1/2 1 2 итерация Баз. Пер. Х1 х2 х3 х4 Решение Z 3/2 3/2 18 х2 1 1/2 -1/2 2 Х1 1 -1 2 Через оптимальную точку проходят три прямые, такую точку называют переопределенной, одно ограничение является избыточным. Вырожденность может приводить к зацикливанию процесса вычислений, но вероятность зацикливания мала, поэтому особых методов предотвращающих это явление, не существует. Итерации симплекс-метода должны выполнятся до тех пор, пока результаты не будут удовлетворять условиям оптимальности, так как вырожденное решение может быть промежуточным. Альтернативное оптимальное решение Если прямая или плоскость, представляющая собой целевую функцию, параллельна прямой или плоскости, соответствующей связующему ограничению, целевая функция принимает одно и тоже оптимальное решение в нескольких точках пространства решений. Такие решения называются альтернативными. Пример: max Z = 2 х1 + 4 х2 { х1 + 2 х2 ≤ 5 - (1) х1 + х2 ≤ 4 - (2) x1 , x 2 ≥ 0 Альтернативное решение - можно определить при нулевых значениях коэффициентов, при небазисных переменных в Z. 0 итерация: Баз. Пер. Х1 х2 х3 х4 Решение Z - 2 - 4 х3 1 2 1 5 х4 1 1 1 4 1 итерация: Баз. Пер. Х1 х2 х3 х4 Решение Z 2 10 х2 ½ ½ 5/2 х4 1/2 - ½ 1 3/2 Z = 10; x2 = 5/2; x 4 = 3/2; Если в качестве включаемой в базис выбрать x1, в качестве исключаемой - x4, то получим второе альтернативное решение: Z = 10; x1 = 3; x 2 = 1; Информация о наличии альтернативных решений может быть полезной при решении практических задач, так как существует возможность выбора альтернативного решения в большей степени отвечающего сложившийся ситуации. Неограниченные решения Некоторые задачи могут допускать бесконечное увеличение значений переменных без нарушения наложенных ограничений. Это говорит о том, что модель недостаточно точна: • Не учтены одно или несколько ограничений, не являющихся избыточными; • Не точно оценены параметры ограничений. Пример: max Z = 2 х1 + х2 { х1 - х2 ≤ 10 - (1) 2 х1 ≤ 40 - (2) x1 , x 2 ≥ 0 Баз. Пер. Х1 х2 х3 х4 Решение Z - 2 - 1 х3 1 - 1 1 10 х4 2 1 40 Если на некоторой итерации небазисная переменная имеет в ограничениях не положительные коэффициенты, то пространство решений, в данном направлении, не ограничено. Если, кроме того,: коэффициент при это переменной в Z уравнении отрицателен (в задаче max) или положителен (в задаче min), то целевая функция так же не ограничена. Пример: max Z = 6 х1 - 2 х2 { 2 х1 - х2 ≤ 2 - (1) х1 ≤ 4 - (2) x1 , x 2 ≥ 0 Баз. Пер. Х1 х2 х3 х4 Решение Z - 6 2 х3 2 - 1 1 2 х4 1 1 4 Отсутствие допустимых решений Раздел: Двойственная задача ЛП. Тема: Взаимосвязь прямой и двойственной задачи. Двойственная задача – это вспомогательная задача ЛП, которая формулируется с помощью определенных правил из условий прямой или исходной задачи, приведенной к стандартной форме. Исходную задачу, приведенную к стандартной форме, можно записать в общем виде: max Z = C1X1 + C2X2 + … + CnXn (min) { a11x1 + a12x2 + … + а1nxn = b1 ( у1) a21x1 + a22x2 + … + а2nxn = b2 (у)2 … am1x1 + am2x2 + … + аmnxn = bm (у)m В состав n переменных xj входят остаточные и избыточные переменные. Max(min) Z= При ограничениях i=1,2,…m xj>=0 j=1,2…n Двойственная задача формулируется по следующим правилам: • Каждому ограничению прямой задачи соответствует переменная двойственной задачи. • Каждой переменной прямой задачи соответствует ограничение двойственной задачи. • Правые части ограничений становятся коэффициентами целевой функции двойственной задачи. Направление оптимизации, ограничения и знаки запишем в виде таблицы: Прямая задача Двойственная задача Целевая функция Целевая функция Ограничения Переменные max min ≥ Не ограничены в знаке min max ≤ Не ограничены в знаке Двойственная задача: Min(max) W= При ограничениях i=1..m j=1..n yi не огранич. в знаке Между прямой и двойственной задачами существует тесная взаимосвязь. Оптимальное решение одной из задач можно получить из данных симплекс-таблицы для оптимального решения другой задачи. Трудоемкость вычислений при решении задач зависит в большей степени от числа ограничений, чем от количества переменных, поэтому если в двойственной задаче ограничений меньше, то целесообразнее решать ее, а полученный результат использовать для нахождения оптимального решения прямой задачи. Пример: max Z = 5 х1 + 12 х2 + 4 х3 { х1 + 2 х2 + х3 ≤ 10 - (1) 2 х1 - х2 + 3 х3 = 8 - (2) x1 , x2 , x 3 ≥ 0 max Z = 5 х1 + 12 х2 + 4 х3 + 0 х4 - MR { х1 + 2 х2 + х3 + х4 = 10 - (1) 2 х1 - х2 + 3 х3 + R = 8 - (2) x1 , x2 , x 3, x4 , R ≥ 0 Оптимальное решение: Баз. Пер. Х1 х2 х3 х4 R Решение Z 3/5 29/5 - 2/5 + М 274/5 Х2 1 - 1/5 2/5 - 1/5 12/5 Х1 1 7/5 1/5 2/5 26/5 Двойственная задача: min w = 10 y1 + 8 y2 { y1 + 2 y2 ≥ 5 - (1) 2 y1 - y2 ≥ 12 - (2) y1 + 3 y2 ≥ 4 - (3) y1 + 0 y2 ≥ 0 - (4) 0 y1 + y2 ≥ - M - (5) y1 ≥ 0, y2 – не ограничена в знаке y2 = y 2’- y2 “ Баз. Пер. y1 y2’ y2“ Y3 х4 х5 R1 R2 R3 Решение Z 26/5 - М 12/5 - М - М 274/5 Y5 7/5 - 1/5 - 1 3/5 y2“ - 2/5 1/5 2/5 y1 1/5 2/5 29/5 y2 = 0 – 2/5 = - 2/5; y 1 = 29/5; w = 274/5; 1) max Z = min w = 274/5 , то есть значения целевых функций совпадают; 2) коэффициент при начальной базисной переменной в оптимальном Z уравнении прямой задачи равен разности между левой и правой частями ограничений двойственной задачи, соответствующих данной переменной. 29/5 = y1 – 0; y 1 = 29/5 -2/5 + М = y2 + М; y 2 = - 2/5; Оптимальное решение прямой задачи можно определить из симплекс-таблицы для оптимального решения двойственной задачи. Двойственная задача к двойственной есть ни что иное, как прямая задача. Тема: Двойственный симплекс-метод. В обычном симплекс-методе начальное решение допустимое, но не оптимальное. Итерационный процесс постепенно приводит решение к оптимальному. В двойственном симплекс-методе начальное решение оптимальное, но не допустимое. Итерационный процесс постепенно приводит его к допустимому. Такой метод решения подходит для определенного класса задач, в которых начальное решение оптимальное, но не допустимое. Например, min z=2x1+x2 3x1+x2>=3 4x1+3x2>=6 x1+2x2<=3 x1,x2>=0 Преобразуем все ограничения в неравенства со знаком <=, умножив правую и левую части на (-1) и приведем к стандартной форме, добавив остаточные переменные. Решение становится недопустимым. -3x1-x2+x3=-3 -4x1-3x2+x4=-6 x1+2x2+x5=3 x1,x2,x3,x4,x5>=0 min z-2x1-x2=0 Так как задача min, а в z-строке все коэффициенты отрицательные и нулевые, то начальное решение оптимальное. Если в правых частях ограничений есть хотя бы одно отрицательное значение, то решение недопустимое. Баз. Пер. x1 х2 х3 х4 х5 Решение Z -2 -1 Х3 -3 -1 1 -3 Х4 -4 -3 1 -6 Х5 1 2 1 3 Условие допустимости: В качестве исключаемой выбирается наименьшая отрицательная базисная переменная (по столбцу Решение). Если все базисные переменные неотрицательные, процесс вычислений заканчивается, так как полученное решение и оптимальное и допустимое. Условие оптимальности: Выбор включаемой переменной производится следующим образом. Вычисляются отношения коэффициентов z-строки к отрицательным коэффициентам исключаемой строки. В задаче min выбирается минимальное отношение, в задаче max - наибольшее отношение. При наличии альтернатив выбор делается произвольно. Если в отношениях все знаменатели положительные или нулевые, задача не имеет допустимых решений. После выбора включаемой и исключаемой переменных выполняются те же операции, как и в обычном симплекс-методе. Итак, x4 – исключаемая переменная x2 – включаемая переменная. Оптимальное решение: Баз. Пер. Х1 х2 х3 х4 х5 Решение Z -2/5 -1/5 12/5 Х1 1 -3/5 1/5 3/5 Х2 1 4/5 -3/5 6/5 Х5 -1 1 1 Полученное решение является и оптимальным и допустимым. Матричные вычисления. Матрица, расположенная под начальными базисными переменными симплекс-таблицы, называется обратной матрицей. Процесс соответствующих вычислений рассмотрим на примере пары прямой и двойственной задач, рассматриваемых на прошлой лекции. Пример: max Z = 5 х1 + 12 х2 + 4 х3 { х1 + 2 х2 + х3 ≤ 10 - (1) 2 х1 - х2 + 3 х3 = 8 - (2) x1 , x2 , x 3 ≥ 0 Начальная симплекс-таблица: Баз. Пер. Х1 х2 х3 х4 R Решение Z -5 -12 4 Х4 1 2 1 1 10 R 2 -1 3 1 8 Оптимальное решение прямой задачи: Баз. Пер. Х1 х2 х3 х4 R Решение Z 3/5 29/5 - 2/5 + М 274/5 Х2 1 - 1/5 2/5 - 1/5 12/5 Х1 1 7/5 1/5 2/5 26/5 Вычисления, связанные с определением новых значений элементов симплекс-таблицы, можно разделить на два типа: 1. вычисление столбцов коэффициентов ограничений; 2. вычисление коэффициентов строки, соответствующей целевой функции. 1. столбец на итерации i=обратная матрица на итерации i*столбец исходной модели Например, x1 столбец в опт. реш.= Или столбец решение в опт. табл.= 2. z-коэф-т при xj=, т.е. равен разности между левой и правой частями соответствующего ограничения двойственной задачи. Значения двойственных переменных yi на любой итерации: , где Сi – вектор-строка исходных коэффициентов целевой функции при базисных переменных прямой задачи A-1 – обратная матрица. Например, z-коэффициент при x1=y1+2y2-5 z-коэффициент при x2=2y1-y2-12 z-коэффициент при x3=y1+3y2-4 z-коэффициент при x4=y1-0 z-коэффициент при R=y2+M В оптимальном решении z-коэффициент при x1=y1+2y2-5=29/5+2*(-2/5)-5=0 . . . z-коэффициент при R=y2+M=-2/5+M Тема: Анализ построенной математической модели на чувствительность с использованием обратной матрицы и соотношений двойственности. После нахождения оптимального решения, в зависимости от рассматриваемой ситуации, необходимо получить новые значения элементов симплекс-таблицы. Если полученное решение не оптимальное, то с помощью обычного симплекс-метода необходимо получить оптимальное решение. Если полученное решение не допустимое, то с помощью двойственного симплекс-метода необходимо получить допустимое решение. К недопустимости решений могут привести изменения запасов ресурсов и добавление новых ограничений. К неоптимальности решения могут привести изменения коэффициентов целевой функции и ограничений, а также включение в модель нового вида производственной деятельности. Пример: Прямая задача: max Z = 3 х1 + 2 х2 { х1 + 2 х2 ≤ 6 - (1) 2 х1 + х2 ≤ 8 - (2) - х1 + х2 ≤ 1 - (3) х2 ≤ 2 - (4) x1 , x2 ≥ 0 Баз. Пер. Х1 х2 х3 х4 х5 Х6 Решение Z 1/3 4/3 38/3 Х2 1 2/3 - 1/3 4/3 Х1 1 - 1/3 2/3 10/3 Х5 - 1 1 1 3 Х6 - 2/3 1/3 1 2/3 Двойственная задача: min w = 6 y1 + 8 y2 + y3 + 2 y4 { y1 + 2 y2 - y3 ≥ 3 - (1) 2 y1 + y2 + y3 + y4 ≥ 2 - (2) y1 , y2 , y3 , y4 ≥ 0 Тема: Изменение условий задачи, влияющих на допустимость решения. 1. Изменение правых частей Предположим, запас исходного продукта А увеличен с 6 до 7 тонн. ( Х2 ) Х1 = ( обратн. матрица )х( Исходн столбец ) Х5 Х6 ( 2/3 - 1/3 )*( 7 )=( 2 ) - 1/3 2/3 8 3 -1 1 1 1 2 - 2/3 1/3 1 2 Z = 3 * 3 + 2 * 2 = 13. Полученное решение допустимое. Предположим, что максимальный суточный запас исходных продуктов составляет не 6 и 8, а 7 и 4 тонны. ( 2/3 - 1/3 )*( 7 )=( 10/3 ) - 1/3 2/3 4 1/3 -1 1 1 1 - 2 - 2/3 1/3 1 2 - 4/3 Z = 3* (1/3) + 2 * (10/3) = 23/3. Полученное решение недопустимое. Баз. Пер. Х1 х2 х3 х4 х5 Х6 Решение Z 1/3 4/3 23/3 Х2 1 2/3 - 1/3 10/3 Х1 1 - 1/3 2/3 1/3 Х5 - 1 1 1 - 2 Х6 - 2/3 1/3 1 - 4/3 Полученное решение недопустимое, поэтому воспользуемся двойственным симплекс-методом, чтобы привести его к допустимому решению. После применения двойственного симплекс-метода получим допустимое решение: x1 = 1 ; x2 = 2 ; Z = 7 ; 2. Добавление нового ограничения Если новое ограничение при текущем решении выполняется, то его добавление не изменит полученного решения. Если же новое ограничение при текущем решении не выполняется, то такое ограничение является связывающим и приводит к недопустимому решению. С помощью двойственного симплекс-метода находится новое решение. а) x1 ≤ 4 – новое ограничение (x1 = 10/3 , x2 = 4/3) Выполняется при текущем решении; б) x1 ≤ 3 – новое ограничение Не выполняется при текущем решении; Необходимо привести новое ограничение к стандартной форме, выразить базисные переменные, содержащиеся в ограничении через небазисные. И используя двойственный симплекс-метод, найти новое допустимое решение. x1 + x7 = 3 ; x7 ≥ 0 x1 – уравнение из оптимальной симплекс-таблицы: x1 - (1/3) x3 + (2/3) x4 = 10/3 x1 = 10/3 + (1/3) x3 - (2/3) x4 (1/3) x3 - (2/3) x4 + x7 = - 1/3 Баз. Пер. Х1 х2 х3 х4 х5 Х6 х7 Решение Z 1/3 4/3 38/3 Х2 1 2/3 - 1/3 4/3 Х1 1 - 1/3 2/3 10/3 Х5 - 1 1 1 3 Х6 - 2/3 1/3 1 2/3 Х7 1/3 - 2/3 1 - 1/3 После применения двойственного симплекс-метода получаем допустимое решение: x1 = 3 ; x2 = 3/2 ; Z = 12 ; ! Добавление нового связывающего ограничения не может улучшить значения целевой функции. Тема: Изменение условий задачи, влияющих на оптимальность решения 1. Изменение коэффициентов целевой функции Двойственные оценки изменяются в том случае, если меняются коэффициенты при базисных переменных. Если изменяются коэффициенты только при небазисных переменных, следует использовать текущие двойственные оценки. Пример: а) max Z = 3 х1 + 2 х2 изменяем на Z = 5 х1 + 4 х2 (у1, у2, у3, у4) = (коэффициенты при баз. перемен-х) х (обратн. матрица) = ( 2/3 - 1/3 ) = (4; 5; 0; 0;) х - 1/3 2/3 = (1; 2; 0; 0) - 1 1 1 - 2/3 1/3 1 Баз. Пер. Х1 х2 Х3 х4 х5 Х6 Решение Z 1 2 22 б) Z = 4 х1 + х2 ( 2/3 - 1/3 ) (у1, у2, у3, у4) = (1; 4; 0; 0;) х - 1/3 2/3 = (-2/3; 7/3; 0; 0) - 1 1 1 - 2/3 1/3 1 Баз. Пер. Х1 х2 Х3 х4 х5 Х6 Решение Z - 2/3 7/3 44/3 Баз. Пер. Х1 х2 Х3 х4 х5 Х6 Решение Z - 2/3 7/3 44/3 Х2 1 2/3 - 1/3 4/3 Х1 1 - 1/3 2/3 10/3 Х5 - 1 1 1 3 Х6 - 2/3 1/3 1 2/3 После применения обычного симплекс-метода получим оптимальное решение : x1 = 4 ; x2 = 0 ; Z = 16 ;. 2. Добавление нового вида производственной деятельности Пусть вводится новый вид производства более дешевого вида краски для наружных работ, требующий по ¾ тонны исходных продуктов А и Б на 1 тонну конечного продукта. Прибыль, получаемая от реализации 1 тонны новой краски равна 3/2 денежных единиц. Пример: Прямая задача: max Z = 3 х1 + 2 х2 + (3/2) х7 { х1 + 2 х2 + (3/4) х7 ≤ 6 - (1) 2 х1 + х2 + (3/4) х7 ≤ 8 - (2) - х1 + х2 - х7 ≤ 1 - (3) х2 ≤ 2 - (4) x1 , x2 , х7 ≥ 0 Составим ограничение двойственной задачи, соответствующее переменной х7 : х7 : (3/4) у1 + (3/4) у2 – у3 ≥ 3/2 В исходной таблице х7 рассматривается как небазисная переменная, поэтому двойственные оценки останутся неизменными (у1, у2, у3, у4) = (1/3; 4/3; 0; 0) z-коэффициент при x7: 3/4*1/3+3/4*4/3-0-3/2=-1/4 (столбец при х7 в опт реш) = (обратн матрица) х (коэффициенты при х7) = ( ¾ )=( ¼ ) = (обр матрица) х ¾ ¼ - 1 -1 - ¼ Обычный симплекс-метод: Баз. Пер. x1 х2 х3 х4 х5 x6 х7 Решение Z 1/3 4/3 - ¼ 38/3 Х2 1 2/3 - 1/3 ¼ 4/3 Х1 1 - 1/3 2/3 ¼ 10/3 Х5 - 1 1 1 - 1 3 Х6 - 2/3 1/3 1 - 1/4 2/3 x1 = 2 ; x2 = 0 ; x7 = 16/3 ; Z = 14 ;. ! Включение в модель нового вида производств. деятельности может улучшить значение целевой функции. Раздел: Транспортная модель Тема: Методы получения начального решения Транспортная модель используется для предоставления наиболее экономичного плана перевозки одного вида продукции из нескольких исходных пунктов в пункты назначения. Для построения транспортной модели используются следующие величины: • Объем производства в каждом исходном пункте аi ; • Спрос в каждом пункте назначения bj ; • Стоимость перевозки единицы продукции из каждого исходного пункта в каждой пункт назначения cij ;. Цель задачи состоит в определении количества продукции xij , которое следует перевезти из каждого исходного пункта в каждый пункт назначения, чтобы транспортные расходы были минимальными. m n min Z = Σ Σ Cij xij i=1 j=1 { n Σ хij ≤ ai j=1 m Σ хij ≥ bj i=1 xij ≥ 0 Транспортная задача называется сбалансированной или закрытой, если суммарный объем производства равен суммарному спросу: m n Σ ai = Σ bj i=1 j=1 Тогда в ограничениях знаки неравенства меняются на знаки равенства: { n Σ хij =ai j=1 m Σ хij = bj i=1 Сбалансированность модели является обязательным условием для применения специальных методов решения транспортной задачи. Транспортная модель может быть представлена с помощью транспортной таблицы, строки которой соответствуют исходным пунктам, столбцы – пунктам назначения, коэффициенты Сij располагаются в правом верхнем углу каждой ячейки. b1 b2 a1 x11 c11 x12 c12 a2 x21 c21 x22 c22 Пример: В исходных пунктах имеются запасы продукции 90, 400 и 110 тонн. Потребители должны получить продукт в количестве 140, 300, 160 тонн. Найти такое распределение груза, чтобы затраты на перевозку были минимальными, если матрица затрат имеет вид: C = ( 2 5 2 ) 4 1 5 3 6 8 3 3 Σ ai = Σ bj = 600 i=1 j=1 b1 b2 b3 Объем a1 2 5 2 90 a2 4 1 5 400 a3 3 6 8 110 спрос 140 300 160 min Z = 2 х11 + 5 х12 + 2х13 + 4х21 + х22 + 5х23 + 3х31 + 6х32 + 8х33 { х11 + х12 + х13 = 90 х21 + х22 + х23 = 400 х31 + х32 + х33 = 110 х11 + х21 + х31 = 140 х12 + х22 + х32 = 300 х13 + х23 + х33 = 160 xij ≥ 0 В данном случае задача сбалансирована, т.е. сумма объемов производства равна сумме спросов: 90+400+110=140+300+160=600. Если задача не сбалансирована, вводятся дополнительные фиктивные исходные пункты или пункты назначения, куда распределяется избыток или недостаток продукции. Т.к. пункт фиктивный, то стоимость перевозки берется, равной 0. Специальные методы решения транспортной задачи повторяют шаги симплекс-алгоритма: • Нахождение начального допустимого решения или опорного плана. • Проверка его на оптимальность • Нахождение нового решения, если решение не оптимально. Нахождение начального допустимого решения можно осуществить тремя способами: • Правило северо-западного угла • Метод минимальной стоимости • Приближенный метод Фогеля Метод северо-западного угла Переменной х11 приписывает минимальное значение по объему производства и по спросу. Вычеркивается строка или столбец, где ограничение на спрос или на объем производства выполнено. Корректируется спрос или объем производства. Переходят к ближайшей невычеркнутой ячейке таблицы. Процесс распределения завершается, когда остается невычеркнутой одна строка или столбец. b1 b2 b3 Объем a1 90 2 5 2 90 a2 50 4 300 1 50 5 400 a3 3 6 110 8 110 спрос 140 300 160 Базисными переменными являются переменные, соответствующие заполненным клеткам таблицы, т.е. x11, x21, x22, x23, x33. Количество базисных переменных определяется по формуле: m+n-1, где m и n – количество строк и столбцов соответственно. m n min Z = Σ Σ Cij xij i=1 j=1 Z = 90*2 + 50*4 + 300 + 50*5 + 110*8 = 1810 д.е. Х = ( 90 ) 50 300 50 110 Метод минимальной стоимости Из всей таблицы ищется ячейка, которой соответствует наименьшая стоимость, ей приписывается минимальное значение по объему производства и по спросу. Если таких переменных несколько, то выбирается любая. Вычеркивается строка или столбец, где ограничение выполнено, корректируются спросы и объемы производства. Далее среди не- вычеркнутых ищется ячейка с минимальной стоимостью. Процесс завершается, когда остается невычеркнутой одна строка или столбец. b1 b2 b3 Объем a1 2 5 90 2 90 a2 30 4 300 1 70 5 400 a3 110 3 6 8 110 спрос 140 300 160 1) х22 = 300, так как С22 = 1 – min; столбец 2 вычеркнут; 2) х13 = 90; строка 1 вычеркнута; 3) х31 = 110; строка 3 вычеркнута; 4) х21 = 30; столбец 1 вычеркнут; 5) х23 = 70; строка 2 вычеркнута; Z = 90*2 + 30*4 + 300 + 70*5 + 110*3 = 1280 денежных единиц Х = ( 90 ) 30 300 70 110 Приближенный метод Фогеля 1. Вычислить штраф для каждой строки и столбца, вычитая наименьший элемент строки или столбца из следующего за ним элемента (по величине) той же строки или столбца. 2. В строке или столбце с самым большим штрафом выбрать переменную с самой низкой стоимостью и придать ей минимальное значение по спросу и объему производства. Скорректировать значение спроса и объема, вычеркнуть строку или столбец, где ограничение выполняется. Строка или столбец с нулевым значением производства или спроса в дальнейших вычислениях не участвует. Если остается невычеркнутой строка или столбец с положительным объемом производства или спроса, найти базисную переменную с помощью метода наименьшей стоимости. Если всем невычеркнутым строкам или столбцам соответствуют нулевые объемы производства и спроса, найти нулевые базисные переменные, используя метод минимальной стоимости. 3. Вычислить новые значения штрафов для невычеркнутых строк и столбцов, перейти к пункту 2. Вычисления продолжаются, пока останется невычеркнутой одна строка или столбец. Количество базисных переменных: m+n-1. b1 b2 b3 Объем Штрафы a1 90 2 5 2 90 3 2 2 - - a2 50 4 300 1 50 5 400 3 1 1 1 4 a3 3 6 110 8 110 3 5 - - - Спрос 140 300 160 Штрафы 1 4 3 1 - 3 2 - 3 4 - 5 4 - - m + n – 1 = 5 Z = 1280 денежных единиц Тема: Метод потенциалов Метод потенциалов используется для проверки полученного начального решения на оптимальность. В методе потенциалов строке i и столбцу j транспортной таблицы ставятся в соответствие так называемые потенциалы Ui и Vj. Для каждой базисной переменной хij они должны удовлетворять следующему условию: Ui + Vj = Cij Это приводит к системе из m+n-1 уравнений, решая которую получаем значения потенциалов, предполагая, что U1=0. Оценки для небазисных переменных хij определяются из соотношения: Ui + Vj – Cij = Ĉij (Ĉij – оценка для небазисной переменной). Если все оценки для небазисных переменных неположительные, т.е. нулевые или отрицательные, то решение оптимально (аналогично условию оптимальности симплекс-метода в задаче минимизации). Если решение неоптимальное, необходимо выбрать включаемую в базис переменную и исключаемую из базиса переменную. Для включения в базис выбирается положительная наибольшая оценка небазисной переменной. V1 = 1 V2 = - 2 V3 = 2 U1 = 0 2 5 90 2 - 1 - 7 U2 = 3 30 4 300 1 70 5 U3 = 2 110 3 6 8 - 6 - 4 U1 + V3 - C11 = Ĉ13 или 0 + 1 – 2 = Ĉ13 или Ĉ13 = -1; х13 : U1 + V3 = C13 или 0 + V3 = 2 или V3 = 2; х23 : U2 + V3 = C23 или U2 + 2 = 5 или U2 = 3; х22 : U2 + V2 = C22 или 3 + V2 = 1 или V2 = - 2; х21 : U2 + V1 = C21 или 3 + V1 = 4 или V1 = 1; х31 : U3 + V1 = C31 или U3 + 1 = 3 или U3 = 2; Так как все оценки для небазисных переменных отрицательны, то решение оптимально. Нахождение исключаемой из базиса переменной (Построение цикла) Этот метод эквивалентен условию допустимости в симплекс-методе. Строится замкнутый цикл, который начинается и заканчивается выбранной не- базисной переменной, имеющей наибольшее положительное значение. Эта переменная будет включена в базис на следующей итерации. Каждая ячейка, стоящая на изломе цикла (контура перераспределения), должна содержать базисную переменную. Направление цикла может быть любым. Для каждого базисного решения и соответствующей небазисной переменной строится только один цикл. Если значения включаемой в базис переменной увеличивается на 1, то для сохранения допустимости решения значения базисных переменных на изломах цикла корректируются. Исключаемая из базиса переменная имеет наименьшее значение из значений ячеек, помеченных знаком «-». Все значения корректируются на эту величину. Ячейки, помеченные «+» увеличиваются, ячейки, помеченные «-». уменьшаются. Оптимальность нового базисного решения снова проверяется вычислением потенциалов. Процесс продолжается до тех пор, пока не будет получено оптимальное решение. Тема: Связь в транспортной задаче между методом потенциалов и симплекс-методом Потенциалы Ui и Vj представляют собой двойственные переменные. Сформулируем двойственную задачу из условий исходной транспортной задачи для m=2 и n=3: Объем x11 c11 x12 c12 x13 c13 a1 x21 c21 x22 c22 x23 c23 a2 спрос b1 b2 b3 n m min Z = Σ Σ Cij xij j=1 i=1 { n____ . .__ Σ хij = ai ; i=1,2 j=1 m .___.____ Σ хij = bj ; j=1,3 i=1 xij ≥ 0 Пусть для ограничений, соответствующих исходным пунктам, двойственные переменные обозначим U1 и U2 , а для пунктов назначения - через V1 , V2 и V3 . Тогда двойственная задача запишется в следующем виде: m n max w = Σ ai Ui + Σ bj Vj i=1 j=1 Ui + Vj ≤ Cij для всех i и j , Ui , Vj не имеют ограничений в знаке Чтобы определить коэффициенты при небазисной переменной xij в Z уравнении, необходимо найти разность между левыми и правыми частями в соответствующих уравнениях двойственной задачи. Uj + Vj - Cij = Ĉij На заключительной итерации потенциалы непосредственно дают оптимальные значения двойственных переменных. Потенциалы на заключительной итерации: U1 = 0 ; U2 = 3 ; U3 = 2 ; V1 = 1 ; V2 = - 2 ; V3 = 2 ; w = (90*0 + 400*3 + 110*2) + (110*1 + 300*(-2) + 160*2) = 1280 денежных единиц Задача: требуется распределить n работ по m станкам. Работа i, выполняемая на станке j связана с затратами Сij. Задача состоит в таком распределении по станкам, которое соответствует минимуму суммарных затрат. i Станки 1 2 … n Виды работ 1 С11 С12 … С1n 1 2 С21 С22 … С2n 1 … … … m Сm1 Сm2 … Сmn 1 1 1 … 1 Если какую-либо работу нельзя выполнить, то стоимость Сij берется равной очень большому числу М (для задачи минимизации) или 0 (для задачи максимизации). Если количество работ m не равно количеству станков n, то модель нужно сбалансировать X ij = { 0, если работа i не выполняется на станке j 1, если работа i выполняется на станке j n m Z = Σ Σ Cij xij j=1 i=1 { m____ Σ хij = 1 i=1 n Σ хij = 1 j=1 xij ≥ 0 Оптимальное решение задачи не изменится, если к любой строке или столбцу матрицы стоимостей прибавить или вычесть постоянную величину. Если можно построить новую Cij матрицу с нулевыми элементами, то эти нулевые элементы или их подмножества будут соответствовать оптимальному решению. Нулевые элементы получаются вычитанием наименьшего элемента в каждой строке и в каждом столбце матрицы. Пример: 1 2 3 Cij = 1 5 7 9 Р1= 5 2 14 10 12 Р2 = 10 3 15 13 16 Р3 = 13 С ’ij= 2 4 4 2 2 3 q1 = 0 q2 = 0 q3 = 2 С ’ij= 2 2 4 2 1 ↑ Нули в каждой строке и столбце соответствуют оптимальному решению. Z = C11 + C23 + C32 = 5 + 12 + 13 = Σ pi + Σ qj = 5 + 10 + 13 +2 Пример: 1 2 3 4 Р Cij = 1 1 4 6 3 1 2 9 7 10 9 7 3 4 5 11 7 4 4 8 7 8 5 5 С ’ij= 3 5 2 2 3 2 1 7 3 3 2 3 q 3 С ’ij= 3 2 2 2 2 1 4 3 3 2 В данном случае невозможно сразу найти оптимальное решение. • Проводим минимальное число прямых, чтобы все нули оказались вычеркнутыми. • Выбирается наименьший элемент среди невычеркнутых элементов. Он вычитается из каждого невычеркнутого элемента и прибавляется к каждому элементу, стоящему на пересечении проведенных прямых. Если оптимальное решение не найдено, то процедуру проведения прямых следует повторять до тех пор, пока не будет получено оптимальное решение. С ’ij= 2 1 1 3 2 3 2 4 2 ↑ нули в каждой строке (столбце) соответствуют оптимальному решению. Z = 1 + 5 + 10 + 5 = 21 Усложненные задачи транспортного типа. Классическая транспортная задача, которую мы рассмотрели, встречается редко. Обычно задачи приходится приводить к классическому транспортному виду. 1. Отдельные поставки от определенных поставщиков некоторым потребителям исключены, т.е. в матрице перевозок определенные клетки должны оставаться свободными. Это достигается искусственным завышением затрат на перевозки cij в клетках, перевозки через которые запрещены. Т.е. завышение должно быть до таких величин, которые заведомо больше всех значений cij в задаче. 2. Ряд транспортных маршрутов может иметь ограничение по пропускной способности. Например, маршрут AiBj может перевезти не более q единиц груза. Тогда Bj столбец разбивается на 2: Bj’=Bj-q – спрос в первом столбце и Bj’’=q – спрос во втором столбце. Затраты cij в столбце Bj’ ставятся искусственно завышенными (клетка блокируется). Далее задача решается обычным способом. M cij Bj’ Bj’’=q 3. Необходимо максимизировать целевую задачу транспортного типа. В этом случае в первую очередь стараются заполнить клетки с наиболее высокими значениями cij. В методе потенциалов в качестве включаемой в базис будет выбрана переменная, имеющая минимальное отрицательное значение оценки для небазисной переменной. Оптимальным будет план, в котором все оценки для небазисных переменных будут нулевыми или положительными. 4. Если в задаче о назначениях требуется найти максимальное значение целевой функции, исходную матрицу необходимо скорректировать: 1. умножить матрицу на (-1) 2. Сложить с максимальным положительным числом относительно всех значений исходной матрицы 3. Далее использовать обычный алгоритм задачи о назначениях. 5. Необходимо в одно время распределить груз различного вида по потребителям. Задачи такого типа называются многопродуктовыми транспортными задачами. Тогда поставщики m типов грузов разбиваются на m условных поставщиков, а потребители на n условных потребителей. Составляется полная транспортная таблица. Некоторые маршруты блокируются, т.е. им искусственно ставится высокая стоимость перевозки. Если поставки грузов различного вида независимы, то задачу можно представить в виде отдельных задач по каждому грузу. 6. Если допускается перевозка груза (частично или полностью) через другие исходные пункты или пункты назначения транзитом, то такая задача известна, как задача с промежуточными пунктами. Каждая вершина рассматривается и как исходный пункт и как пункт назначения. Т.е. число исходных пунктов и пунктов назначения равно их сумме. Например, имеется 3 завода и 2 центра распределения. В модели будет 5 исходных пунктов и 5 пунктов назначения. Для того, чтобы учесть транзитные перевозки, в каждом исходном пункте и пункте назначения предусмотрено дополнительное помещение (буфер) емкостью B>= 7. Задача не является транспортной, но в математическом отношении подобна транспортной, т.к. описывается аналогичной моделью. Рассмотрим примеры. 1. Модель производства с запасами. Фирма переводит свой завод на производство определенного вида изделий, которые будут выпускаться в течении четырех месяцев. Величины спроса в течении этих четырех месяцев составляют 100, 200, 180 и 300 изделий соответственно. В каждый месяц спрос можно удовлетворить за счет: 1. запасов изделий, произведенных в прошлом месяце, сохраняющихся для реализации в будущем; 2. производства изделий в течении текущего месяца; 3. производство изделий в более поздние месяцы в счет невыполненных заказов Затраты на одно изделие в каждом месяце составляют 4 д.е. Изделие, произведенное для более поздней реализации, влечет за собой доп. издержки на хранение в 0,5 д.е. в месяц. С другой стороны, каждое изделие, выпускаемое в счет невыполненных заказов, облагается штрафом в размере 2 д.е. в месяц. Объем производства в рассматриваемые 4 месяца предполагается 150, 180, 280 и 270 изделий. Требуется составить план, имеющий минимальную стоимость производства и хранения изделий. Решение. Задачу можно сформулировать как транспортную: Исходный пункт i - период производства i Пункт назначения j – период потребления j Предложение в пункте i – объем производства за период i Спрос в пункте j – реализация за период j Стоимость перевозки cij - стоимость производства и хранения за период i и j Стоимость производства в период i, i=j Стоимость производства в период I плюс издержки на хранение , ij 2. Имеется 5 ракет и 5 целей. Вероятность поражения цели каждой из ракет задана таблицей. Распределить ракеты по целям так, чтобы мат. ожидание числа пораженных целей было максимальным. 0,12 0,02 0,5 0,43 0,15 0,71 0,18 0,81 0,05 0,26 0,84 0,76 0,26 0,37 0,52 0,22 0,45 0,83 0,81 0,65 0,49 0,02 0,5 0,26 0,27 3. Имеется 4 базы и 3 цели. В силу различия в типах самолетов и высоте полета вес бомб, доставляемых с любой базы к любой цели, определяется матрицей: 8 6 5 Сij= 6 6 6 10 8 4 8 6 4 Дневная интенсивность каждой базы составляет 150 самолетовылетов в день. На каждую цель необходимо организовать 200 самолетовылетов в день. Определить план вылетов с каждой базы к каждой цели, дающий максимальный общий вес бомб, доставляемых к цели. Модели на сетях (графах). Теория графов. Графом называется пара G=(V,E). Элементы множества V называются вершинами графа, элементы множества Е - ребрами или дугами. Если множество Е состоит только из ребер, то граф называется неориентированным, если только из дуг, то ориентированным или орграфом. Если в Е есть и ребра и дуги, то граф называется смешанным. Контур или цикл – это замкнутый маршрут, где V1=Vn. Последовательность различных дуг или ребер, где V1<>Vn, представляют путь или цепь соответственно. Граф называется взвешенным, если его ребрам приписаны числа, называемые весами. Длиной пути называется сумма весов, входящих в него дуг или ребер. С помощью графов можно решить следующие задачи: Проектирование газопровода, имеющего минимальную стоимость; определение кратчайшего пути между двумя города в сети шоссейных дорог; определение максимальной пропускной способности трубопровода и так далее. Оптимизационные задачи на графах можно описать четырьмя типами моделей: • минимизация сети • нахождение кратчайшего маршрута • определение максимального потока • минимизация стоимости потока в сети с ограниченными пропускными способностями коммуникаций Рассмотренные модели связаны с определением расстояний и материальных потоков. 1. Минимизация сети Данная задача состоит в нахождении ребер, соединяющих все узлы графа и имеющих минимальную длину. В итоге должно получиться минимальное дерево-остов, граф, в котором отсутствуют циклы. Алгоритм : • начать с любого узла графа, соединить его с ближайшим узлом. Соединенные узлы образуют связное множество, остальные – несвязное. • В несвязном множестве выбрать узел, который расположен ближе других к любому из узлов связного множества. • Скорректировать связное и несвязное множества. • Повторять до тех пор, пока в связное множество не попадут все узлы сети. Рассмотрим задачу: телевизионная фирма планирует создание кабельной сети для обслуживания пяти районов-новостроек. Числа на ребрах указывают длину кабеля. Узел 1 представляет телевизионный центр, а остальные - районы-новостройки. Нужно найти такие ребра, которые потребуют кабель минимальной длины для связи (прямой или через другие пункты) всех районов с телевизионным центром. 0. C = {1} и Ĉ = {2,3,4,5,6} 1. C = {1,2} 2. C = {1,2,5} 3. C = {1,2,4,5} 4. C = {1,2,4,5,6} 5. C = {1,2,3,4,5,6} Минимальная длина кабеля: Z = 1 + 3 + 4 + 3 + 5 = 16 Алгоритм нахождения кратчайшего пути для сетей без циклов В основе лежит схема рекуррентных вычислений. Где dij - расстояние между узлами i и j, а Uj – кратчайшее расстояние между 1 и j (U1=0) Uj = min {Ui + dij} i 1 этап: U1 = 0; 2 этап: U2 = U1 + d12 = 0 + 2 = 2 (из 1) и U3 = U1 + d13 = 0 + 4 = 4 (из 1) 3 этап: U4 = min {U1 + d14 ; U2 + d24 ; U3 + d34 } = min {10;13;7} = 7 (из 3) 4 этап: U5 = min {U2 + d25 ; U4 + d45 } = min {7;15} = 7 (из 2) U6 = min {U3 + d36 ; U4 + d46 } = min {5;14} = 5 (из 3) 5 этап: U7 = min {U5 + d57 ; U6 + d67 } = min {13;7} = 7 (из 6) Двигаясь в обратном направлении, определяем путь: 1 → 3 → 6 → 7 Определение кратчайшего расстояния для сетей с циклами Сети содержат циклы, возникающие из-за возможности двустороннего движения; если дуга ориентирована (движение одностороннее), то расстояние в другом направлении полагается равным бесконечности. Пусть требуется определить кратчайший маршрут между вершиной 1 и любым другим узлом сети. Расстояния dij запишем в виде таблицы, строки и столбцы которой представляют узлы. 1 2 3 4 Ui 1 15 11 2 3 4 1 15 (12) 3 8 1 5 11 4 ∞ 3 16 (13) Vj 15(12) 11 16(13) 1. Пусть Vj – сумма длин дуг из узла 1 в узел j. Vj = min {Ui + dij} , где Ui – расстояние до узла i i V1=0 U1=V1=0 Ui=Vj, если i=j 2. Предположим i=1. Найти Vj – Ui для всех j. Если dij ≥ Vj – Ui для всех j, то между узлами i и j не существует более короткого пути. i = i + 1, вычисления повторить. Если dij < Vj – Ui , то вычислить новое значение V’j = Ui +dij . Vj заменяется на V’j и берется следующий узел, i = i + 1. Если значение Vj изменилось, то повторить шаг 2, используя измененные значения. 3. Полученные значения Vj определяют кратчайшее расстояние между узлами 1 и любым из узлов j. Для получения соответствующих цепей, найти столбец n, соответствующий узлу, до которого ищется кратчайшее расстояние. Найти строку i, для которой выполняется равенство Vn=Ui+din .Этот узел предшествует узлу n. Рассмотреть столбец i и для него найти соответствующую строку, т.е. предшествующий узел и т.д., пока не дойдем до 1 узла. 1) U1 = V1 = 0 V2 = min {U1 + d12} = 15 ; U2 = 15 V3 = min {U1 + d13 ; U2 + d23 } = min {11;19} = 11 ; U3 = 11 i=1,2 V4 = min {U2 + d24 ; U3 + d34 } = min {16;16} = 16 ; U4 = 16 i=2,3 2) j=1 j=3 j=3 j=4 i = 1 1 2 3 4 Vj – U1 * 15 11 * d1j * 15 11 * Vj-U1<=d1j - пересчитывать расстояния не требуется i = 2 1 2 3 4 Vj – U2 - 15 * - 4 1 d2j 3 * 4 1 Vj-U2<=d2j - пересчитывать расстояния не требуется i = 3 1 2 3 4 Vj – Ui - 11 4 * 5 d3j 8 1 * 5 V2-U3>d32 – расстояние до 2 узла пересчитываем: Vj’=Ui+dij, т.е. V2’=U3+d32=11+1=12, U2’=12 i = 4 1 2 3 4 Vj – Ui * - 4 - 5 * d4j * ∞ 3 * Так как вычислялось новое значение V’j, то нужно заново пересчитать шаг 2. Предположим, что шаг 2 пересчитан и пересчитано новое значение V4’. Найдем цепь, соединяющую узлы 1 и 4, т.е. n=4. Начинаем с последнего узла. Ему соответствует столбец 4. Для него должно выполняться равенство: Vn = din + Ui. V4=Ui+di4 – равенство выполняется для строки 2, переходим к узлу 2 и соответственно к столбцу 2. Ст. 4 : 13 = d24 + U2. ; i = 2 Ст. 2 : 12 = d32 + U3. ; i = 3 Ст. 3 : 11 = d13 + U1. ; i = 1 Итак, искомая цепь с кратчайшим маршрутом 4 ← 2 ← 3 ← 1 Рассмотрим еще один пример: i \ j 1 2 3 4 5 6 7 Ui 1 2 8 11 9 4 2 4 3 5 1 3 1 4 ∞ 2 3 4 5 9 2 23 15(6) 5 2 ∞ 7 9 5 (2) 6 8 3 5 1 10 1 7 10 4 2 11 Vj 4 3 15(6) 5 (2) 1 11 1) U2 = V2 = 0; V1 = U2 + d21 = 0 + 4 = 4 = U1 V3 = min {U1 + d13 ; U2 + d23} = 3 = U3 V4 = min {U1 + d14} = 15 = U4 V5 = min {U1 + d15 ; U2 + d25 } = 5 = U5 V6 = min {U2 + d26 ; U3 + d36 ; U4 + d46 ; U5 + d56 } = {1;5;17;12} = 1 = U6 V7 = min {U4 + d47 ; U5 + d57 ; U6 + d67 } = {38;14;11} = 11 = U7 2) i = 1 1 2 3 4 5 6 7 Vj – Ui * - 4 - 1 11 1 * * d1j * 2 8 11 9 * * i = 2 1 2 3 4 5 6 7 Vj – Ui 4 * 3 * 5 1 * d2j 4 * 3 * 5 1 * i = 3 1 2 3 4 5 6 7 Vj – Ui 1 - 3 * 12 * - 2 * d3j 1 4 * ∞ * 2 * i = 4 1 2 3 4 5 6 7 Vj – Ui - 11 * - 12 * * - 14 - 4 d4j 5 * 8 * * 2 23 i = 5 1 2 3 4 5 6 7 Vj – Ui - 1 - 5 * * * - 4 6 d5j 2 ∞ * * * 7 9 i = 6 1 2 3 4 5 6 7 Vj – Ui * - 1 2 14 4 * 10 d6j * 8 3 5 1 * 10 i = 7 1 2 3 4 5 6 7 Vj – Ui * * * - 5 - 9 - 10 * d7j * * * 10 4 2 * V’j = dij + Ui. или V’4 = d64 + U6 = 1 + 5 = 6 V’5 = d65 + U6 = 1 + 1 = 2 И еще шаг … 3) 7 ← 5 ← 6 ← 2 11 7 ← 6 ← 2 11 6 ← 2 2 5 ← 6 ← 2 2 4 ← 6 ← 2 6 3 ← 2 3 1← 2 4 1← 3 ← 2 4 1 ← 5 ← 6 ← 2 4 Представление задачи о кратчайшем пути в виде транспортной задачи с промежуточными пунктами. Задачу о кратчайшем пути можно представить как транспортную задачу с промежуточными пунктами. Рассмотрим сеть с одним исходным пунктом и одним пунктом назначения. Величина предложения в исходном пункте и величина спроса в пункте назначения равны 1, т.е. единица груза транспортируется из исходного пункта в пункт назначения по маршруту, имеющему минимальную длину пути. Емкость В равна 1, узлы 1 и 7 не могут рассматриваться в качестве промежуточных. «Стоимости перевозок» полагаются равными соответствующим расстояниям. Если маршрута не существует, стоимость берется завышенной - М. 15 1 11 М 1 М 4 1 1 0+В 1 1 М 0+В 0+В 0+В 1 Кратчайший путь: 1-3-2-4, кратчайшее расстояние :z=11+1+1=13. Данную задачу можно представить как задачу линейного программирования: Min z= - из исходного пункта - для промежуточных пунктов - в пункт назначения Xij=0 или 1. Xij представляет величину потока по дуге (i , j) . Суммарный поток, выходящий из узла 1 равен 1(1 ограничение), как и суммарный поток, входящий в пункт n (последнее ограничение модели). В любом промежуточном узле суммарный входящий поток равен суммарному выходящему потоку. Целевая функция требует, чтобы расстояние, пройденное единицей потока, было минимальным. Переменная xij может принимать значения, равные 0 или 1. Если xij=1, то дуга принадлежит кратчайшему пути, если xij=0, то дуга не принадлежит кратчайшему пути. Составим целевую функцию и ограничения для примера, рассмотренного ранее: Min z=15x12+11x13+3x21+4x23+x24+8x31+x32+5x34+100x42+3x43 При ограничениях: x12+x13=1 x12+x32+x42=x21+x23+x24 x13+x23+x43=x31+x32+x34 x24+x34=1 Тема: Максимальный поток Алгоритм определения максимального потока 1. Занести данные потока сети в таблицу. 2. Найти цепь соединения S с t, по которой поток принимает положительное значение (>0) . Если такой цепи нет, то перейти к 3. 3. Отметить ячейки в матрице потока в прямом направлении (-), в обратном направлении (+): Сij -- (Сij +) – S → t (t → S) и найти минимальное значение из ячеек, помеченных (-): Θ = min { Сij -} > 0 4. Скорректировать матрицу пропускных способностей. Вычесть Θ из всех ячеек, отмеченных минусом (Сij --) и прибавить Θ ко всем значениям ячеек, отмеченных плюсом (Сij +). Перейти к пункту 1. Данные операции дают возможность использовать остатки пропускных способностей от S к t и восстановить исходные пропускные способности, так как уменьшение пропускной способности дуги в одном направлении можно рассматривать как увеличение ее пропускной способности в обратном направлении. 5. Найти максимальный поток в сети. Пусть С = ‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌║ Сij ║ - исходная матрица потока, а С*=║ С*ij║ - последняя (модифицированная) матрица, когда нельзя построить цепь, по которой поток принимает положительное значение ( >0). Тогда матрица максимального потока х = ║ хij ║ : хij ={ Сij - Сij *, если Сij > Сij * 0, если Сij < Сij * Z = Σ хsj = Σ хjt = Σ Θ i j Рассмотрим пример. Каждая дуга сети обладает пропускными способностями в обоих направлениях, которые определяют максимальное количество потока, проходящего по данной дуге. Односторонняя дуга соответствует нулевой пропускной способности в запрещенном направлении. Пропускные способности Сij представляются в виде матрицы и таблицы. Найти максимальный поток от 1 узла к 4. С: 1 2 3 4 1 _ 5 1 9 2 + 6 _ 3 3 2 1 5 4 6 + 7 6 1).1 → 2 → 4 – строим цепь от S к t . Клетки 1→2 и 2→4 помечаем - « - » 2→1 и 4→2 помечаем– « + » Минимальное значение из ячеек, помеченных « - » min {5,3} = 3. Θ = 3 Если в ячейке знак «-» - вычитаем Θ, если же знак «+», то прибавляем Θ. 2). Следующая цепь из 1 в 4: 1 → 3 → 4 Θ = 1 1 2 3 4 1 2 _ 1 9 2 9 3 + 2 1 _ 5 4 6 10 + 6 3). Следующая цепь 1 → 4 1 2 3 4 1 2 _ 9 2 9 3 3 1 4 4 + 6 10 7 Θ = 9 С* - последняя модифицированная матрица, нельзя построить цепь, в которой поток >0. 1 2 3 4 1 2 2 9 3 3 1 4 4 15 10 7 Положительных потоков больше нет. Х = {0, если Сij – С*ij <0} Сij – С*ij, иначе Х: 1 2 3 4 1 3 1 9 2 3 3 1 4 9 + 3 +1 = 13 Z = Θ=13 Задачу о максимальном потоке можно рассмотреть как задачу ЛП. Пусть y - поток из источника 1 в сток n. Обозначим поток по дуге (i,j) через xij, получим следующую модель: Max z=y - источник , для всех k<> 1 или n - сток 0≤xij≤uij, для всех i,j. Uij – пропускная способность дуги (i,j) Для рассматриваемого примера: z=y x12+x13+x14=y x21+x24+x12+x32+x42 x13+x23+x43=x31+x34 x14+x24+x34=y Целочисленное программирование. Целочисленное программирование ориентировано на решение задач математического программирования, в которых все или некоторые переменные должны принимать только целочисленные значения. Задача называется полностью целочисленной, если условие целочисленности наложено на все ее переменные; когда это условие относится, лишь к некоторым переменным, задача называется частично целочисленной. Если при этом целевая функция и функции, входящие в ограничения, линейные, то задача является линейной целочисленной. Несмотря на то, что к настоящему времени разработан ряд методов решения целочисленных задач, ни один из них не обеспечивает желаемой эффективности соответствующих вычислительных процедур, что особенно проявляется при увеличении размерности задачи. Таким образом, в отличие от задач линейного программирования, время решения которых относительно невелико, реализация целочисленных алгоритмов в ряде случаев весьма затруднительна. Одна из основных трудностей в целочисленном программировании связана с эффектом ошибки округления, возникающим при использовании цифровых ЭВМ. Даже наличие алгоритмов, применяемых для решения задач с целочисленными коэффициентами и позволяющих обойтись без оперирования дробями (и, следовательно, избежать влияния ошибок округления), не упрощает ситуации, поскольку такие алгоритмы (в ряде случаев) сходятся чрезвычайно медленно. Присущие целочисленному программированию трудности вычислительного характера обусловили стремление исследователей найти альтернативные пути решения проблемы. Один из простейших подходов заключается в решении непрерывной модификации целочисленной задачи с последующим округлением координат полученного оптимума до допустимых целых значений. Округление в данном случае есть не что иное, как приближение. Например, если получено решение непрерывной задачи, содержащее число 10,1, можно приближенно заменить это число на 10 (то есть округлить до 10). Однако нет гарантии, что округленное решение будет удовлетворять ограничениям. Для линейной задачи с ограничениями в виде равенств округленное решение всегда не удовлетворяет этим ограничениям. Как следует из теории линейного программирования, округленное решение не может быть допустимым, поскольку это означало бы, что один и тот же базис (при условии равенства нулю небазисных переменных) определяет два различных решения задачи. Эффект округления не слишком заметен, когда (искомые) параметры задачи подчинены относительно нежестким ограничениям. Однако типичными для задач целочисленного программирования являются ограничения – равенства, достаточно жестко определяющие поведение релевантных переменных. Примером может служить условие x1 + x2 + ... + xn = 1, где xj = (0, 1) для всех j. В такой ситуации процедура округления не имеет смысла, и необходимо обратиться к другим алгоритмам решения. Несостоятельность округления подчеркивается также следующими соображениями. Несмотря на то, что целочисленные переменные обычно выражают количество неделимых предметов (например, машин, людей, кораблей), возможны и другие типы спецификации этих переменных. Так, решение о финансировании некоторого проекта представляется булевой переменной х (х = 0, если проект отклоняется, и х = 1, если проект принимается). В этом случае бессмысленно оперировать дробными значениями величины х, и процедура округления является логически неприемлемой. Так как практическая ценность задач с «кодированными» переменными не вызывает сомнений, в следующем разделе рассмотрены примеры задач такого рода. Материал раздела демонстрирует важную роль целочисленного программирования среди методов исследования операций. 1. Примеры задач целочисленного программирования. В данном разделе рассматриваются примеры решения задач, ни одна из которых не является ярко выраженной задачей целочисленного программирования. Значительно больший интерес представляют открываемые целочисленным программированием возможности приведения «некорректных» задач к стандартному виду задач математического программирования. Использование специальных приемов позволяет получить решение в ряде случаев, когда решить задачу с помощью прямых методов оказывается крайне затруднительным. 1.1. Задача с постоянными элементами затрат. В одной из типичных задач планирования производства рассматривается N видов промышленной продукции. Затраты на производство продукции вида j складываются из постоянных затрат в объеме Kj, не зависящем от количества произведенной продукции, и текущих издержек cj на производство единицы продукции. Таким образом, если xj - объем продукции вида j, функцию суммарных затрат можно записать следующим образом: Естественным выглядит стремление минимизировать Рассматриваемый критерий не является линейным по xj вследствие разрыва в начале координат. Поэтому задача с целевой функцией z оказывается непригодной для дальнейшего исследования. Введение дополнительных булевых переменных позволяет преобразовать задачу к виду, «более приемлемому» с аналитических позиций. Пусть что можно переписать в форме (линейного) неравенства: xj  Myj. Здесь М  0 достаточно велико, чтобы условие xj  M выполнялось для всех допустимых объемов выпуска продукции. Теперь исходную задачу можно сформулировать следующим образом: минимизировать при ограничениях 0  xj  Myj для всех j, yj = 0 или 1для всех j Рассмотрим подробнее ограничение xj  Myj. При xj  0 имеем yj = 1 и целевая функция включает постоянные затраты Kj. Если xj = 0 то yj может принимать значения 0 или 1, однако, поскольку Kj  0 и z требуется минимизировать, переменная yj должна быть равна нулю. Следует подчеркнуть, что исходная задача с постоянными элементами затрат не имеет никакого отношения к целочисленному программированию. Тем не менее «преобразованная» задача представляет собой частично целочисленную задачу с булевыми переменными («0 – 1» задачу). Необходимость рассмотренного преобразования была обусловлена исключительно аналитическими соображениями. В самом деле, булевы переменные являются вспомогательными, так как ассоциированную с ними информацию можно назвать полезной лишь условно. Например, yj = 1 в оптимальном решении означает, что xj  0. 1.2. Задача планирования производственной линии. Рассмотрим задачу, связанную с выполнением п различных производственных операций на одном станке за минимально возможное время. В процессе производства последовательно выполняется ряд операций, порядок которых устанавливается технологическими требованиями. Каждое изделие необходимо изготовить к заданному сроку. В задаче имеются три типа ограничений, связанных с (1) последовательным осуществлением операций, (2) неразветвленностью производственного процесса, и (3) наличием установленного срока изготовления каждого изделия. Ограничения второго типа отражают тот факт, что никакие две операции не выполняются (на станке) одновременно. 1. Рассмотрим первый тип ограничений. Обозначим через xj время начала операции j (отсчитываемое от некоторого исходного момента), а через aj – величину промежутка времени, требуемого для выполнения этой операции. Если операция i должна предшествовать операции j , то соответствующее ограничение записывается в виде неравенства: xi + ai  xj 2. Рассмотрим условие неразветвленности производственного процесса. Для операций i и j, не выполняемых на станке одновременно, или xi - xj  aj, или xj – xi  ai, когда в оптимальном решении j предшествует i или i предшествует j соответственно. Логические ограничения вида «или – или» не укладываются в рамки обычной задачи линейного программирования (так как порождают невыпуклое пространство допустимых решений). Эту трудность можно обойти путем введения вспомогательных булевых переменных Если М достаточно велико, ограничение «или – или» эквивалентно следующей системе неравенств: Myij + (xi – xj)  aj и M (1 – yij) + (xj – xi)  ai. В случае, когда для оптимального решения yij = 0, второе неравенство становится избыточным, а активным ограничением будет первое неравенство. Если же yij = 1, первое неравенство становится избыточным, а в качестве ограничения фигурирует второе неравенство. Таким образом, введение булевых переменных yij позволяет преобразовать эти ограничения к обычному виду ограничений линейной частично целочисленной задачи. 3. Учет заданных сроков изготовления осуществляется следующим образом. Пусть операция j должна быть завершена к моменту времени dj, тогда xj + aj  dj Если обозначить через t суммарное время, требуемое для выполнения всех п операций, рассматриваемая задача принимает следующий вид: минимизировать z = t при условии что xj + aj  t, j = 1, 2, ..., n, и выполняются ограничения трех перечисленных выше типов. 1.3. Задачи с дихотомией. Предположим, что в некоторой ситуации требуется выполнение k из общего числа m ограничений. При этом заранее неизвестно, какие именно ограничения должны выполняться. Запишем ограничения в виде неравенств: gi (x1, x2, ..., xn)  bi, i = 1, 2, ..., m. Определим новую переменную: Если М достаточно велико, выполнение по крайней мере k из m рассматриваемых ограничений обеспечивается соблюдением следующих условий: gi (x1, x2, ... xn)  bi + Myi, i = 1, 2, ..., m, y1 + y2 + ... + ym = m – k. Здесь yi = 0 или 1 для всех i. Отсюда следует, что правые части некоторых m – k приведенных неравенств можно записать в виде bi + M , и, таким образом, эти ограничения становятся избыточными. Важно отметить, что рассмотренный прием позволяет идентифицировать множество выполняющихся ограничений, на котором реализуется оптимум значений целевой функции (при заданном k). Аналогичная ситуация возникает, когда правая часть некоторого ограничения может принимать одно из нескольких возможных значений, т. е.: g (x1, x2, ..., xn)  b1, b2, ..., или br. Данное ограничение приводится к следующему виду: g (x1, x2, ..., xn)  y1 + y2 + ... + yr = 1, где 2. Методы решения задач целочисленного программирования. Методы решения задач целочисленного программирования можно классифицировать как (1) методы отсечений и (2) комбинаторные методы. Исходной задачей для демонстрации возможностей методов отсечений, используемых при решении линейных целочисленных задач, является задача с ослабленными ограничениями, которая возникает в результате исключения требования целочисленности переменных. По мере введения дополнительных ограничений, учитывающих требование целочисленности, многогранник допустимых решений ослабленной задачи постепенно деформируется до тех пор, пока координаты оптимального решения не станут целочисленными. Название «методы отсечений» связано с тем обстоятельством, что вводимые дополнительные ограничения отсекают (исключают) некоторые области многогранника допустимых решений, в которых отсутствуют точки с целочисленными координатами. В основе комбинаторных методов лежит идея перебора всех допустимых целочисленных решений. Разумеется, на первый план здесь выдвигается проблема разработки тестовых процедур, позволяющих непосредственно рассматривать лишь (относительно небольшую) часть указанных решений, а остальные допустимые решения учитывать некоторым косвенным образом. Наиболее известным комбинаторным методом является метод ветвей и границ, который также опирается на процедуру решения задачи с ослабленными ограничениями. При таком подходе из рассматриваемой задачи получаются две подзадачи путем специального «разбиения» пространства решений и отбрасывания областей, не содержащих допустимых целочисленных решений. В случае, когда целочисленные переменные являются булевыми, применяются комбинированные методы. Булевы свойства переменных существенно упрощают поиск решения. Методы, рассматриваемые в данной главе, предназначены для решения главным образом линейных целочисленных задач. Метод отсекающих плоскостей, разработанный Р. Гомори, включает дробный алгоритм (в отечественной литературе этот алгоритм называется также первым алгоритмом Гомори и циклическим алгоритмом целочисленного программирования), который используется при решении полностью целочисленных задач, а также алгоритм решения частично целочисленных задач (в отечественной литературе этот алгоритм называется также вторым алгоритмом Гомори и смешанным алгоритмом целочисленного программирования). Алгоритм, реализующий метод ветвей и границ, был предложен А. Лэнд и А. Дойг. Ниже представлена модификация этого алгоритма, базирующаяся на ветвящейся схеме Дейкина, которая обладает рядом преимуществ вычислительного характера. Для решения задач, содержащих только булевы переменные, обычно используется так называемый аддитивный алгоритм. 3. Алгоритмы, реализующие метод отсекающих плоскостей. Представленный ниже пример раскрывает смысл понятия «отсекающая плоскость». Рассмотрим следующую линейную задачу целочисленного программирования: максимизировать z = 7x1 + 9x2 при ограничениях -х1 + 3х2  6 7х1 + х2  35, х1, х2 – неотрицательные целые. Область допустимых решений задачи с ослабленными ограничениями, получаемой путем отбрасывания требования целочисленности переменных, изображена на рисунке 1: Рис.1 Оптимальное значение целевой функции z = 63 достигается в точке с дробными координатами х1 = 9/2 и х2 = 7/2. В основе метода отсекающих плоскостей лежит преобразование области допустимых решений задачи с ослабленными ограничениями в выпуклый многогранник, экстремальная точка которого является оптимальным решением исходной целочисленной задачи, при этом, естественно, все допустимые целочисленные решения исходной задачи должны лежать внутри или на границе построенного многогранника. На рисунке показано, как введение двух (некоторым образом выбранных) дополнительных ограничений позволяет получить новую экстремальную точку с координатами (4, 3), являющуюся оптимальным решением сформулированной выше задачи целочисленного программирования. Заметим, что область, отсеченная от множества допустимых решений ослабленной задачи, не содержит точек с целочисленными координатами (на рисунке эта область заштрихована). 3.1. Дробный алгоритм решения полностью целочисленных задач. Необходимым условием применения данного алгоритма является целочисленность всех коэффициентов и правых частей ограничений исходной задачи. Например, ограничение х1 + 1/3х2  13/2 можно записать в виде неравенства 6х1 + 2х2  39, в котором дроби отсутствуют. Последнее неравенство получено путем умножения обеих частей рассматриваемого ограничения на наименьший общий знаменатель входящих в него коэффициентов. Необходимость введения требования целочисленности параметров исходной задачи обусловлена следующими соображениями. Из дальнейшего рассмотрения будет видно, что как исходные, так и дополнительные переменные задачи, решаемой с помощью дробного алгоритма, должны быть целочисленными. Между тем наличие в ограничениях дробных коэффициентов приводит к нарушению целочисленности дополнительных переменных. В этом случае дробный алгоритм позволяет обнаружить отсутствие допустимого решения даже тогда, когда задача, записанная в исходных переменных, имеет допустимое целочисленное решение (см. задачу в качестве примера). Перейдем к описанию рассматриваемого алгоритма. На первом шаге решается задача с ослабленными ограничениями, не содержащими условия целочисленности переменных. Если полученное оптимальное решение оказывается целочисленным, то оно является также решением исходной задачи. В противном случае следует ввести дополнительные ограничения, порождающие (вместе с исходными ограничениями) новую задачу линейного программирования, решение которой оказывается целочисленным и совпадает с оптимальным решением исходной целочисленной задачи. Пусть последняя симплексная таблица задачи с ослабленными ограничениями имеет следующий вид: базисные переменные х1 … xi ... xm w1 … wj … wn решение z 0 ... 0 ... 0 0 x1 . . . 1 ... 0 ... 0 . . . . . . . . . . . . . . . . . . 1 . . . xi . . . 0 ... 1 ... 0 . . . . . . . . . . . . i . . . xm 0 ... 0 ... 1 m Здесь через xi (i = 1, 2, ..., m) обозначены базисные переменные, а через wj (j = 1, 2, ..., n) – небазисные переменные. Такая структура обозначений выбрана из соображений удобства. Рассмотрим i – ю строку симплексной таблицы, которой соответствует нецелое значение базисной переменной xi, и выразим xi через небазисные переменные: Каждую строку симплексной таблицы, порождающую аналогичное равенство, будем называть производящей строкой. Так как коэффициенты целевой функции можно считать целыми числами, переменная z также должна быть целочисленной, и верхнюю строку таблицы допустимо выбирать в качестве производящей. Кроме того, требование целочисленности z оказывается весьма существенным при доказательстве конечности рассматриваемого алгоритма. Пусть где N = [a] – наименьшее целое число, удовлетворяющее условию N  a. Отсюда следует, что 0  fi  1 и 0  fij  1. Таким образом, fi есть положительная дробь, а fij – неотрицательная дробь. В качестве примера рассмотрим следующую таблицу: a [a] f = a - [a] 1 1/2 -3 2/3 -1 -1 -2/5 -1 3/5 После подстановки приведенных выше тождеств уравнение, выражающее xi через небазисные переменные, приобретает следующий вид: . Поскольку все переменные xi и j принимают целые значения, правая часть уравнения должна быть целочисленной, откуда следует, что левая часть уравнения также должна принимать целые значения. Далее, так как fij  0 и j  0 для всех i и j, то Следовательно, выполняется неравенство: . Это означает, что поскольку fi. Так как левая часть рассматриваемого неравенства должна принимать целые значения, можно записать необходимое условие ее целочисленности в следующем виде: Последнее ограничение перепишем в виде равенства: где Si – неотрицательная дополнительная переменная, которая по определению должна принимать целые значения. Такое ограничение-равенство определяет отсечение Гомори для полностью целочисленной задачи. Из симплексной таблицы следует, что j = 0, и, таким образом, Si = - fi , т.е. данная компонента решения не является допустимой. Это означает, что полученное ранее решение непрерывной задачи не удовлетворяет новому ограничению. В такой ситуации следует использовать двойственный симплекс-метод, реализация которого обеспечивает отсечение некоторой области многогранника решений, не содержащей точек с целочисленными координатами. Преобразуем исходную таблицу путем приписывания к ней строки и столбца, соответствующих построенному отсечению Гомори для полностью целочисленной задачи. Получим новую таблицу: базисные переменные х1 … xi ... xm w1 … wj … wn Si решение z 0 ... 0 ... 0 0 x1 . . . 1 ... 0 ... 0 . . . . . . . . . . . . . . . . . . . . . 1 . . . xi . . . 0 ... 1 ... 0 . . . . . . . . . . . . . . . . . . . . . i . . . xm 0 ... 0 ... 1 m Si 0 ... 0 ... 0 -fi1 ... -fij ...-fin 1 -fi Если полученное (в результате применения двойственного симплекс-метода) решение является целочисленным, то процесс решения исходной задачи завершен. В противном случае необходимо ввести новое отсечение на базе полученной таблицы и вновь воспользоваться двойственным симплекс-методом. Описанная процедура повторяется до тех пор, пока не будет найдено целочисленное решение. Если на некоторой итерации при использовании двойственного симплекс – алгоритма обнаружится отсутствие допустимого решения, то рассматриваемая задача не имеет допустимого целочисленного решения. Название дробный алгоритм связано с тем обстоятельством, что все ненулевые коэффициенты введенного отсечения меньше единицы. При изучении дробного алгоритма может сложиться впечатление, что размеры симплексной таблицы неограниченно возрастают по мере добавления новых отсечений к набору ограничений исходной задачи. Это не соответствует действительности. Общее число ограничений порожденной задачи не может превышать количества переменных исходной задачи, а именно (m + n). В самом деле, если порожденная задача содержит более чем (m + n) ограничений, то одна или несколько дополнительных переменных Si, ассоциированных с отсечениями Гомори, должны стать базисными. В этом случае соответствующие равенства становятся избыточными и могут быть исключены из таблицы. Дробный алгоритм имеет два недостатка: 1. Ошибки округления, возникающие в процессе вычислений с помощью ЭВМ, в ряде случаев приводят к получению неверного (неоптимального) целочисленного решения. Трудности такого рода можно избежать путем раздельной записи в памяти ЭВМ числителей и знаменателей различных дробей (и, следовательно, исключить оперирование десятичными дробями). Однако количество разрядов в указанных целых числах может превысить возможности запоминающего устройства компьютера. 2. Решения, последовательно получаемые в процессе реализации алгоритма, не являются допустимыми, т. е. алгоритм не позволяет получить какое-либо целочисленное решение, отличное от оптимального. Это означает, что в случае вынужденного прекращения вычислений до момента окончания процесса решения в памяти ЭВМ не будет содержаться никакого «приемлемого» целочисленного решения исходной задачи. От первого из перечисленных недостатков свободен полностью целочисленный алгоритм, область применения которого ограничена множеством полностью целочисленных таблиц (т. е. таблиц, все коэффициенты которых целые), пригодных для применения двойственного симплекс – алгоритма. Введение специальных отсечений осуществляется таким образом, чтобы не нарушать условий целочисленности элементов таблицы. Тем не менее этот алгоритм также не обеспечивает получения какого-либо допустимого целочисленного решения до тех пор, пока не будет найдено оптимальное решение. Второй недостаток отсутствует у ряда алгоритмов, реализующих метод отсекающих плоскостей, поскольку в качестве исходного в этом случае берется целочисленное и допустимое, но не оптимальное решение. На каждом шаге итерации решение продолжает оставаться допустимым и целочисленным до тех пор, пока не будет получено оптимальное решение. Такие алгоритмы можно классифицировать как прямые, тогда как алгоритмы Гомори являются двойственными. Однако следует заметить, что прямые алгоритмы не обладают преимуществами вычислительного характера. Пример 1: Рассмотрим задачу, решенную графическим способом в начале раздела 3. Оптимальное решение соответствующей задачи с ослабленными ограничениями задается таблицей: Базисные переменные х1 х2 х3 х4 Решение z 28/11 15/11 63 x2 1 7/20 1/22 7/2 x1 1 -1/22 3/22 9/2 Так как полученное решение не является целочисленным, следует расширить данную таблицу путем введения некоторого отсечения. В качестве производящей строки можно выбрать любую из строк таблицы, содержащих нецелые компоненты решения. Обычно используется эмпирическое правило, согласно которому выбирается строка, соответствующая maxi fi. Поскольку в обе строки рассматриваемой таблицы входит одно и то же значение fi, а именно f1 = f2 = 1/2, любая из них может быть выбрана в качестве производящей. Строке с базисной переменной х2 соответствует равенство х2 +7/22х3 + 1/22х4 = 31/2 или х2 + (0 + 7/22)х3 + (0 + 1/22)х4 = (3 + 1/2) Следовательно, уравнение отсечения Гомори имеет вид: S1 – 7/22x3 – 1/22x4 = - 1/2. Получаем новую таблицу: Базисные переменные х1 х2 х3 х4 S1 Правые части z 28/11 15/11 63 x2 1 7/22 1/22 x1 1 -1/22 3/22 S1 -7/22 -1/22 1 -1/2 Использование двойственного симплекс-метода приводит к таблице: Базисные переменные х1 х2 х3 х4 S1 Решение z 1 8 59 x2 1 1 3 x1 1 1/7 -1/7 x3 1 1/7 -22/7 Так как решение опять не является целочисленным, необходимо продолжить процесс введения отсечений. Строке с базисной переменной x1 соответствует равенство: x1 + (0 + 1/7)х4 + (-1 + 6/7) S1 = (4 + 4/7), порождающее отсечение: S2 – 1/7x4 – 6/7S1 = - 4/7. Добавим это отсечение к последней таблице: Базисные переменные х1 х2 х3 х4 S1 S2 Правые части z 1 8 59 x2 1 1 3 x1 1 1/7 -1/7 х3 1 1/7 -22/7 S2 -1/7 -6/7 1 -4/7 В результате использования двойственного симплекс-метода получим таблицу: Базисные переменные х1 х2 х3 х4 S1 S2 Решение z 2 7 55 x2 1 1 3 x1 1 -1 1 4 x3 1 -4 1 1 x4 1 6 -7 4 которая дает оптимальное целочисленное решение исходной задачи: z = 55, x1 = 4, x2 = 3. Можно наглядно убедиться в том, что рассмотренные выше отсечения исключают некоторые области многогранника до допустимых решений. Первое отсечение S1 – 7/22x3 – 1/22x4 = - 1/2, записанное в переменных х1 и х2, после соответствующей замены принимает следующий вид: S1 – 7/22 (6 + x1 – 3x2) – 1/22 (35 – 7x1 – x2) = - ½ или S1 + x2 = 3. Это уравнение эквивалентно неравенству х2  3. Аналогичным образом второе отсечение S2 – 1/7x4 – 6/7S1 = - 4/7 порождает эквивалентное ограничение в переменных х1 и х2: х1 + х2  7. На рис.1 показано, как введение этих двух ограничений позволяет получить новую экстремальную точку с координатами (4, 3), в которой достигается оптимум исходной целочисленной задачи. Эффективность отсечения Гомори Из изложенного выше следует, что вид неравенства, определяющего некоторое отсечение, зависит от выбора производящей строки. Таким образом, одна и та же симплекс-таблица порождает различные отсечения. Возникает естественный вопрос: какое из них является наиболее эффективным? Эффективность отсечения характеризуется размерами области, отсекаемой от многогранника допустимых решений, что математически можно выразить следующим образом. Рассмотри неравенства: (1) (2) Будем говорить, что отсечение (1) более эффективно, чем отсечение (2), если fi  fk и fij  fkj для всех j, причем по крайней мере в одном случае выполняется строгое неравенство. Использование данного определения эффективности отсечения связано с существенными трудностями вычислительного характера. Поэтому были разработаны эмпирические правила, отражающие смысл этого определения. Два таких правила предписывают строить сечение на основе производящей строки, которой соответствует maxi fi (a) или (б). Второе правило обладает определенными преимуществами перед первым, так как оно теснее связано с данным выше определением эффективности отсечения. Пример 2: Оптимальное решение целевой функции z = 63 задачи с ослабленными ограничениями, рассмотренной в примере 1, достигается в точке с координатами х1 = 9/2 и х2 = 7/2. поскольку значение z является целым, соответствующая строка не может быть выбрана в качестве производящей. Первое из перечисленных эмпирических правил не позволяет осуществить наилучший выбор производящей строки, так как f1 = f2 = 1/2. Чтобы применить второе правило, необходимо вычислить все коэффициенты отсечения Гомори для каждой из производящих строк. Введем отсечения, соответствующие производящим строкам с базисными переменными х1 и х2: 21/22х3 + 3/22х4  1/2 (х1-строка), 7/22х3 + 1/22х4  (х2-строка). Так как в качестве производящей строки следует выбрать строку с базисной переменной х2. В примере 1 х2-строка была выбрана в качестве производящей случайным образом. Чтобы подтвердить правильность сделанного выбора, сравним два отсечения, ассоциированные с х1-строкой и х2-строкой. В примере 1 показано, что отсечение, соответствующее х2-строке, и записанное в переменных х1 и х2, имеет следующий вид: х23. С помощью аналогичной замены отсечение, соответствующее х1-строке, можно записать в виде неравенства: х2  10/3. Первое неравенство является более жестким и, следовательно, определяет более эффективное отсечение. Однако следует отметить, что использование рассмотренных эмпирических правил не всегда обеспечивает введение наиболее эффективного отсечения. 3.2. Алгоритм решения частично целочисленных задач Пусть xk – переменная частично целочисленной задачи, принимающая целые значения. Как и в случае полностью целочисленной задачи, рассмотрим соответствующую базисной переменной xk-строку симплекс-таблицы, содержащей решение задачи с ослабленными ограничениями. Эта строка порождает равенство: или . Поскольку некоторые из переменных j не являются целочисленными, для решения поставленной задачи нельзя применить процедуру отсечений, рассмотренных в предыдущем разделе. Тем не менее, исходя из той же общей идеи, можно построить отсечение другого типа. Для целочисленной переменной xk должно выполняться одно из двух неравенств: либо xk  [k], либо xk  [k] + 1. С учетом равенства, полученного из производящей строки, запишем эти условия в следующем виде: (1) (2) Пусть j+– множество значений j, для которых ; j- множество значений j, для которых . Из формул (1) и (2) получаем: , (3) . (4) Так как соотношения (1) и (2), а следовательно, (3) (4) не могут выполняться одновременно, имеется возможность объединить (3) и (4) в одно ограничение вида: , где Sk  0 есть неотрицательная дополнительная переменная. Последнее уравнение определяет искомое отсечение Гомори для частично целочисленной задачи и представляет собой необходимое условие целочисленности переменной xk . Дальнейшие преобразования расширенной таблицы следует проводить с помощью двойственного симплекс-метода. Рассмотренное отсечение введено без учета того обстоятельства, что некоторые из переменных j могут быть подчинены условию целочисленности. Запишем уравнение более эффективного отсечения в следующем виде: , где Пример 3: Рассмотрим пример 1. Пусть требование целочисленности наложено только на переменную х1. Запишем соотношение: откуда: Соответствующее отсечение Гомори для частично целочисленной задачи принимает следующий вид: или Добавим это ограничение к последней таблице: Базисные переменные х1 х2 х3 х4 S1 Правые части z 28/11 15/11 63 x2 1 7/22 1/22 7/2 x1 1 -1/22 3/22 9/2 S1 -1/22 -3/22 1 -1/2 В результате применения двойственного симплекс-метода получим таблицу: Базисные переменные х1 х2 х3 х4 S1 Решение z 23/11 10 58 x2 1 10/33 -1/3 10/3 x1 1 -1/11 1 4 х4 1/3 1 -22/3 11/3 Отсюда следует, что оптимальное значение целевой функции z = 58 достигается в точке с координатами х1 = 4 и х2 = 10/3. Значение х1 является целым, что и требовалось в соответствии с условиями задачи. Вычислительные возможности методов отсечений. Известен ряд способов построения отсечений других типов, каждый из которых в той или иной степени свободен недостатков вычислительного характера, присущих остальным типам отсечений. Тем не менее ни один тип отсечений не обеспечивает высокой эффективности соответствующих вычислительных процедур. Несмотря на то, что методы отсечений являются надежным средством решения некоторых задач, имеющих специальную структуру, общая точка зрения исследователей-практиков формулируется следующим образом: методы отсечений не подходят для решения целочисленных задач большой размерности. Более того, опыт показывает, что даже некоторые задачи сравнительно небольшой размерности не могут быть решены с помощью методов отсечений. Известны случаи, когда непреднамеренное изменение порядка следования ограничений делало несложную исходную задачу поистине гигантской по объему вычислений. Наиболее общий вывод о возможностях использования методов отсечений, по-видимому, заключается в признании того факта, что указанные методы не обеспечивают эффективного решения общей задачи целочисленного программирования. Однако некоторые идеи методов отсечений могут оказаться 9и оказываются) полезными для совершенствования других алгоритмов решения целочисленных задач. Метод ветвей и границ Этот метод решения задачи целочисленного программирования также опирается на решение задачи с ослабленными ограничениями. Однако в отличие от методов отсечений метод ветвей и границ непосредственно применим как к полностью, так и к частично целочисленным задачам. Согласно общей идее метода, сначала решается задача с ослабленными ограничениями (задача линейного программирования). Пусть xr - целочисленная переменная, значение которой в оптимальном решении ослабленной задачи является дробным. Интервал или (сравните с неравенствами, рассмотренными при построении отсечения Гомори для частично целочисленной задачи).Введение этих условий в задачу с ослабленными ограничениями порождает две не связанные между собой задачи. В таком случае говорят, что исходная задача разветвляется (или разбивается) на две подзадачи. Осуществляемый в процессе ветвления учет необходимых условий целочисленности позволяет исключить части многогранника допустимых решений, не содержащие точек с целыми координатами. Затем каждая подзадача решается как задача линейного программирования (с целевой функцией исходной задачи). Если полученный оптимум оказывается допустимым для целочисленной задачи, такое решение следует зафиксировать как наилучшее. При этом нет необходимости продолжать «ветвление» подзадачи, поскольку улучшить полученное решение, очевидно, не удастся. В противном случае подзадача в свою очередь должна быть разбита на две подзадачи – опять при учете условия целочисленности переменных, значения которых в оптимальном решении не являются целыми. Разумеется, как только полученное допустимое целочисленное решение одной из подзадач оказывается лучше имеющегося, оно фиксируется вместо зафиксированного ранее. Процесс ветвления продолжается, насколько это возможно, до тех пор, пока каждая подзадача не приведет к целочисленному решению или пока не будет установлена невозможность улучшения имеющегося решения. В этом случае зафиксированное допустимое решение является оптимальным. Эффективность вычислительной схемы можно повысить, введя в рассмотрение понятие границы, на основе которого делается вывод о необходимости дальнейшего разбиения каждой из подзадач. Если оптимальное решение подзадачи с ослабленными ограничениями обеспечивает худшее значение целевой функции, чем имеющееся решение, эту подзадачу далее рассматривать не следует. В таких случаях говорят, что подзадача прозондирована, и ее можно вычеркнуть из списка подзадач, порожденных исходной задачей. Иными словами, как только получено допустимое целочисленное решение некоторой подзадачи, соответствующее значение целевой функции может быть использовано в качестве (верхней в случае минимизации и нижней в случае максимизации) границы, наличие которой позволяет формализовать процедуру исключения прозондированных подзадач. Следует подчеркнуть исключительную важность проблемы выявления достаточно близкой к оптимальному решению границы уже на первых этапах вычислений. Успешное разрешение указанной проблемы находится в прямой зависимости от порядка, в котором порождаются и решаются различные подзадачи, а также от выбора переменной, инициирующей процесс ветвления. К сожалению, вопрос о «наилучшем» способе выбора переменной ветвления или последовательности решения конкретных подзадач пока еще не решен. Здесь можно воспользоваться эмпирическими правилами, которые широко применяются в программах для ЭВМ, использующих аппарат метода ветвей и границ, например в программе UMPIRE (Scientific Control Systems Ltd., London). Пример 1: Максимизировать z = 2x1 + 3x2 при ограничениях: 5х1 + 7х2 £ 35, 4х1 + 9х2 £ 36, х1, х2 ³ 0 – целые. На рисунке 1 изображена совокупность порожденных подзадач в виде дерева: Исходной является вершина 1, в которой сформулированная задача решается как задача линейного программирования. Оптимальное решение достигается в точке с координатами х1 = 312/17 и х2 = 26/17. Так как обе переменные принимают нецелые значения, любая из них может быть выбрана в качестве переменной, инициирующей процесс ветвления. Выбор переменной х2 порождает две подзадачи, связанные с условиями х2 £ 2 и х2 ³ 3 соответственно (заметим, что х2* = 26/17, поэтому [x2*] = 2), а именно подзадачи 2 и 3 (см. график, ассоциированный с вершиной 1). Порожденные подзадачи содержат все допустимые целочисленные решения исходной задачи, т.е. исходное множество допустимых целочисленных решений остается неизменным в процессе ветвления. На следующем шаге осуществляется выбор одной из подзадач – 2 или 3 для решения и при необходимости для дальнейшего ветвления. Важно отметить, что не существует точных способов реализации указанного выбора. Не менее важным является то обстоятельство, что выбор различных альтернатив приводит к разным последовательностям подзадач и, следовательно, к различным количествам итераций, обеспечивающих получение оптимального целочисленного решения. Продемонстрируем этот факт, пользуясь рис. 1. Предположим, что в первую очередь рассматривается вершина 2 (х2 £ 2). Оптимальное решение соответствующей задачи линейного программирования достигается в точке с координатами х1 = 41/5 и х2 = 2. (Это решение получено путем добавления ограничения х2 £ 2 к оптимальной таблице для задачи, отображенной вершиной 1, и последующего применения двойственного симплекс-метода).Так как значение х1 (= 41/5) продолжает оставаться нецелым, учет требований х1 £ 4 и х1 ³ 5 в задаче 2 порождает подзадачи 4 и 5. Опять предположим, что сначала мы рассматриваем вершину 4 (а не вершину 5 или вершину 3). Подзадача 4 имеет целочисленное решение z=14 при х1 = 4 и х2 = 2. Наличие у подзадачи 4 целочисленного решения не означает, что найден оптимум исходной задачи. Причиной такого вывода являются еще не решенные подзадачи 3 и 5, которые могут улучшить целочисленное решение z = 14. Целочисленное решение подзадачи 4 определяет нижнюю границу z = 14 значений целевой функции. Нет необходимости рассматривать те последующие подзадачи, для которых оптимальные значения z меньше указанной нижней границы. Обратившись затем к подзадаче 3 (полученной путем введения неравенства х2 ³ 3 в систему ограничений задачи 1), находим ее оптимальное решение z = 131/2, которое не превышает значения z = 14. Таким образом, вершина 3 далее не рассматривается, и поиск вдоль ветви х2 ³ 3 следует прекратить. На следующем шаге нужно исследовать вершину 5, которой соответствует оптимальное значение z, равное 142/7. Несмотря на то, что полученное значение превышает нижнюю границу z = 14, дальнейшее ветвление осуществлять нецелесообразно, поскольку разность между значением z, соответствующим вершине 5, и z меньше единицы и все коэффициенты целевой функции являются целыми числами. Таким образом, ветви, исходящие из вершины 5, в лучшем случае приведут к другому целочисленному решению, в котором z = 14. Если поиск других решений с тем же самым значением z не представляет интереса, вершина 5 должна быть исключена из рассмотрения. Из вышеизложенного следует, что оптимальное целочисленное решение исходной задачи ассоциировано с вершиной 4 (z = 14, х1 = 4, х2 = 2). Эта информация получена путем рассмотрения вершин 1, 2, 3, 4 и 5 в порядке 1 ® 2 ® 3 ® 4 ®5. (Можно прийти к такому же выводу, если сначала исследовать вершину 5, а не вершину 3). Заметим, что при движении по упомянутой выше цепочке подзадач (1 ® 2 ® 3 ® 4 ®5) в вершинах 3 и 5 мы не имеем сведений о качестве полученного ранее решения, выраженного через максимум z, до тех пор, пока не решим подзадачи, соответствующие указанным вершинам. По этой причине нельзя предугадать, является ли выбор ветви х2 ³ 3, осуществленный в вершине 1, более выгодным, чем выбор ветви х2 £ 2, или наоборот. Для иллюстрации этого факта предположим, что сначала исследуется вершина 3 (это означает, что подзадача, соответствующая вершине 2, остается пока не решенной), для которой z = 131/2, х1 = 21/4, х2 = 3. Так как значение х1 не является целым, исходящие из вершины 3 ветви х1 £ 2 и х1 ³ 3 порождают подзадачи 6 и 7. Пусть на следующем шаге решается подзадача 6. Получаем х2 = 31/9, и возникают две новые ветви х2 £ 3 и х2 ³ 4, приводящие к вершинам 8 и 9. Если далее рассмотреть подзадачу 8, получим оптимальное (целочисленное) решение z = 13, х1 = 2 и х2 = 3, откуда нижняя граница z = 13. Теперь необходимо исследовать вершины 2, 7 и 9, используя нижнюю границу z = 13 в качестве критерия, по которому осуществляется исключение соответствующих подзадач из имеющегося списка. Для вершины 9 оптимальное значение целевой функции z = 12 меньше нижней границы z, и подзадача 9 далее не рассматривается. Подзадача 7 исключается вследствие отсутствия допустимых решений. Для вершины 2 получаем z = 142/5, что превышает фиксированное значение z. Пара ветвей, исходящих из вершины 2, приводит к вершинам 4 и 5. Решив подзадачу 4, находим новое значение нижней границы z = 14, которое позволяет исключить из рассмотрения вершину 5, и процесс решения исходной задачи завершается получением оптимума, ассоциированного с вершиной 4. Поиск оптимального решения осуществляется в соответствии с последовательностью вершин 1 ® 3 ® 6 ® 8 ® 9 ® 7 ® 2 ® 4 ®5. Таким образом, начальный выбор вершины 3 привел к необходимости решения девяти подзадач, тогда как выбор вершины 2 – только пяти подзадач. Рассмотренный пример наглядно демонстрирует основной недостаток метода ветвей и границ, который заключается в отсутствии данных о количестве подзадач, требующих решения в связи с проблемой нахождения и верификации целочисленного оптимума. Это приводит не только к увеличению времени вычислений, но в ряде случаев и к переполнению памяти ЭВМ. Вычислительные возможности метода ветвей и границ Между алгоритмами метода ветвей и границ, положенными в основу большинства используемых программ для ЭВМ, и описанным выше алгоритмом имеются определенные различия, которые главным образом связаны с правилами выбора последовательности рассмотрения подзадач и переменных, инициирующих процессы ветвления в вершинах. Обычно это эвристические правила, разработанные в ходе машинных экспериментов. Главный недостаток изложенного выше алгоритма заключается в необходимости полностью решать задачи линейного программирования, ассоциированные с каждой из вершин. Для задач большой размерности это требует значительных и в известной степени неоправданных с практической точки зрения затрат машинного времени, так как при исследовании вершин в ряде случаев достаточно ограничиться информацией о значении оптимума целевой функции. Некоторые вершины, для которых известны оптимальные значения целевой функции, могут быть исключены из рассмотрения в результате сравнения указанных значений с границей при условии, разумеется, что мы располагаем «приемлемым» значением этой границы. Приведенные соображения используются при реализации процедуры, которая исключает необходимость решения всех подзадач, возникающих в процессе реализации метода ветвей и границ. В рамках этой процедуры осуществляется попытка «оценить» верхнюю границу (в задаче максимизации) оптимального значения целевой функции для каждой вершины. Вершина подлежит исключению из рассмотрения, как только значение верхней границы оказывается меньше значения целевой функции в наилучшем имеющимся оптимальном решении. Для оценивания верхних границ требуется сравнительно небольшой объем вычислений, что является главным преимуществом такого подхода. Основная идея состоит в оценивании штрафов (т.е. величин изменения целевой функции), связанных с введением ограничений xk £ [bk] или [xk ³ [bk] + 1 в оптимальную таблицу соответствующей подзадачи (для которой xk инициирует процесс ветвления). С учетом предположения о неизменности базиса искомую величину штрафа можно оценить непосредственно на основе коэффициентов целевой функции. Штрафы довольно легко вычислить, однако оценки штрафов не всегда верно отражают истинные изменения значений целевой функции. Иными словами, вычисление штрафов не обеспечивает получения точной границы и поэтому может оказаться неэффективным. Был осуществлен ряд попыток «модифицировать» оценки штрафов. Наиболее интересными представляются разработки, предполагающие использование методов отсечений. Тем не менее вычислительные схемы на «модифицированных» штрафах, также не являются достаточно эффективными, особенно при увеличении размерности задачи. Все это привело к отказу от использования методики оценивания штрафов в коммерческих программах для ЭВМ в пользу эвристических процедур, которые, как показывают экспериментальные расчеты для сложных задач большой размерности, в ряде случаев оказываются весьма эффективными. Несмотря на отмеченные недостатки метода ветвей и границ, можно утверждать, что в настоящее время алгоритмы метода являются наиболее надежным средством решения целочисленных задач, встречающихся в практических исследованиях. Все известные программы для ЭВМ основаны на методе ветвей и границ. Это не означает, однако, что любая целочисленная задача может быть решена с помощью рассматриваемого метода. Тем не менее проблема выбора между методом отсечений и методом ветвей и границ в подавляющем большинстве случаев обоснованно решается в пользу последнего.