Оптимизация и исследование операций

y Оглавление В.М. Караулов МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ОБРАЗОВАНИЯ «ВЯТСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ» Факультет автоматики и вычислительной техники Кафедра прикладной информатики y II JJ В.М. Караулов Оптимизация и исследование операций Учебное пособие y Киров 2017 Стр. 1 из 136 JI JIxy y × y Оглавление В.М. Караулов Глава 1 Введение y II JJ Исследование операций — научная дисциплина, занимающаяся разработкой и практическим применением методов наиболее эффективного управления различными организационными системами. Цель исследования операций — количественное обоснование принимаемых решений по организации управления. Применение методов исследования операций предполагает: • построение экономических и математических моделей для задач принятия решения в сложных ситуациях или в условиях неопределенности; • изучение взаимосвязей, определяющих впоследствии принятия решений, и установление критериев эффективности, позволяющих оценить преимущество того или иного варианта действий. y Введение Стр. 2 из 136 JI JIxy y × y Оглавление 1.1 Основные понятия исследования операций 1.1 Основные понятия исследования операций y II JJ Операция — любое управляемое мероприятие, направленное на достижение цели. Результат операции зависит от способа ее проведения, другими словами — от выбора некоторых параметров. Определенный выбор параметров называется решением. Оптимальными считаются решения, которые по определенным соображениям предпочтительнее других. В качестве критериев оптимальности могут выступать показатели эффективности, принимающие максимальные, минимальные или целевые значения. Основная задача исследования операций — предварительное количественное обоснование оптимальных решений. Само принятие решения не относится к вопросам исследования операций. y Введение Стр. 3 из 136 JI JIxy y × y y y y Оглавление 1.1 Основные понятия исследования операций II JJ Примеры управленческих задач, для которых применяются методы исследования операций • календарное планирование производства с целью эффективного использования ресурсов; • организация поставок продукции потребителю; • управление запасами; • эксплуатация и ремонт оборудования; • комплектование штата персонала; • задачи планирования (определения) ассортимента выпускаемой продукции; • разработка долгосрочных программ развития производства. Инструментом количественных методов исследования является экономико-математическая модель операций. Модель — это абстрактное отражение реальности в упрощенном виде с целью исследования свойств объектов или процессов. Математическая модель строиться на основе математического аппарата, например, с помощью функций, уравнений, систем уравнений и неравенств и т. д. Экономико-математическая модель подразумевает, что за некоторыми математическими обозначениями, математическими операциями и свойствами скрываются конкретные экономические характеристики и закономерности. Составление модели операции требует понимания сущности описываемого явления и знания математического аппарата. Эффективность операции — это степень ее приспособленности к выполнению задачи — количественно выражается в виде критерия эффективности — целевой функции. Например, в задаче об использовании ресурсов критерий эффективности — прибыль от реализации произведенной продукции, которую нужно максимизировать; в транспортной задаче критерий эффективности — суммарные затраты на перевозку грузоов от поставщиков к потребителям, которые нужно минимизировать. Выбор критерия эффективности определяет практическую ценность исследования. Введение Стр. 4 из 136 JI JIxy × y Оглавление В.М. Караулов Глава 2 Модели линейного программирования y Линейное программирование Стр. 5 из 136 JI JIxy y II JJ y × y Оглавление 2.1 Общая постановка задачи линейного программирования 2.1 Общая постановка задачи линейного программирования Дана система m линейных уравнений с n переменными   a11 x1 + a12 x2 + . . . + a1j xj + . . . + a1n xn 6 b1 ,    a21 x1 + a22 x2 + . . . + a2j xj + . . . + a2n xn 6 b2 ,   ··· ··· ··· ···   ak1 x1 + ak2 x2 + . . . + akj xj + . . . + akn xn 6 bk , ak+1,1 x1 + ak+1,2 x2 + . . . + ak+1,j xj + . . . + ak+1,n xn = bk+1 ,     ak+2,1 x1 + ak+2,2 x2 + . . . + ak+2,j xj + . . . + ak+2,n xn = bk+2 ,     ··· ··· ··· ···   am1 x1 + am2 x2 + . . . + amj xj + . . . + amn xn = bm , y II JJ (2.1) и линейная функция F (x1 , x2 , . . . , xn ) = c1 x1 + x2 x2 + . . . + cj xj + . . . + cn xn . (2.2) Необходимо найти такое решение X = (x1 , x2 , . . . , xj , . . . , xn ), где x1 > 0, x2 > 0, ..., xj > 0, . . . , xn > 0, (2.3) при котором линейная функция F (2.1) принимает оптимальное (т. е. максимальное или минимальное) значение. Система (2.1) называется системой ограничений, а функция F — линейной функцией, линейной формой, целевой функцией или функцией цели. y Линейное программирование Стр. 6 из 136 JI JIxy y × y Оглавление 2.1 Общая постановка задачи линейного программирования y II JJ Оптимальным решением (оптимальным планом) задачи линейного программирования называется решение X ∗ = (x1∗ , x2∗ , . . . , xn∗ ) системы ограничений (2.1), удовлетворяющих условию (2.3), при котором линейная функция (2.2) принимает оптимальное (максимальное или минимальное) значение. Если системы ограничений (2.1) состоит лишь из неравенств одного вида (например «6»), то такая задача линейного программирования называется стандартной, если система ограничений состоит из одних уравнений — то задача называется канонической. Заметим, что при умножении на (−1) стандартная система ограничений может представлена неравенствами «6» или «>». y Линейное программирование Стр. 7 из 136 JI JIxy y × y Оглавление 2.1 Общая постановка задачи линейного программирования y II JJ Пример 2.1. Задача об использовании ресурсов (планировании производства). Для изготовления двух видов продукции на предприятии используют четыре вида ресурсов. Для изготовления одной единицы первого продукта используется одна единица первого ресурса две единицы второго и три единицы четвертого ресурса. Для изготовления одной единицы второго продукта используется три единицы первого ресурса и по одной единицы второго и третьего ресурсов. В наличии имеется 18 единиц первого ресурса, 16 единиц второго, 5 единиц третьего ресурса и 21 единицы четвертого ресурса. Прибыль (выручка), получаемая от первого и второго продуктов составляет соответственно 2 и 3 денежные единицы. Требуется составить оптимальный план производства, т. е. такие объемы выпуска первой и второй продукции, при которых прибыль (выручка) от реализации будет максимальной при заданных запасах ресурсов. Решение. Сначала проведем качественный анализ. В исследуемой операции в качестве неуправляемых (экзогенных) параметров выступают показатели технологических процессов, связанные с расходом ресурсов (нормы использования ресурсов), а также объемы ресурсов, которыми располагает фирма. К управляемым (эндогенным) переменным относятся объемы продукции, выпускаемые каждым технологическим процессом. Критерием оптимальности является размер прибыли, полученной от реализации произведенной продукции. y Линейное программирование Стр. 8 из 136 JI JIxy y × y Оглавление 2.1 Общая постановка задачи линейного программирования y II JJ Теперь построим экономико-математическую модель данной задачи. Обозначим через x1 и x2 — объем выпуска первой и второй продукции. Тогда прибыль от реализации первого продукта составит 2x1 , а второго — 3x2 . Таким образом, целевая функция имеет вид: F (x1 , x2 ) = 2x1 + 3x2 . В процессе производства затрачивается первый ресурс в объеме 1x1 для выпуска x1 единиц первой продукции и 3x2 — для выпуска x2 единиц второй продукции. Аналогичным образом получаем, что при плане производства (x1 , x2 ) второй ресурс расходуется в объеме 2x1 + 1x2 , третий ресурс — 0x1 + 1x2 и четвертый ресурс — 3x1 + 0x2 . С учетом того, что план использования ресурсов не может превышать имеющихся запасов ресурсов, экономико-математическая модель данной задачи имеет следующий вид: Найти F (x1 , x2 ) = 2x1 + 3x2 → max при ограничениях:  x + 3x2 6 18,   1 2x1 + x2 6 16,  x2 6 5, 3x1 6 21 и x1 > 0, x2 > 0. Целевая функция рассчитывает значение прибыли (выручки) фирмы при выпуске x1 и x2 единиц первой и второй продукции. Четыре неравенства в данной задаче оказывают, что затраты ресурсов не могут превосходить их запасы в 18, 16, 5 и 21 единиц. Ограничения x1 > 0 и x2 > 0 указывают на то, что объем производства может выражаться неотрицательными числами. y Линейное программирование Стр. 9 из 136 JI JIxy y × y Оглавление 2.1 Общая постановка задачи линейного программирования y II JJ В условиях задачи нормы расходов ресурсов на единицу продукции могут быть представлены в виде матрицы  1 2 0 3  3 1 1 , в которой строка — номер ресурса, а столбец — номер продукта. Вся задача может быть представлена в краткой форме в виде расширенной матрицы:   1 3 18 16  5  , 21 max  2 1  0 1  3 0 2 3 из которой легко восстанавливаются все условия задачи: три группы экзогенных параметров — нормы расхода ресурсов, запасы ресурсов, нормы прибыли и цель оптимизации. Для представления задачи в каноническом виде введем в каждое i-е неравенство дополнительную переменную x2+i > 0, i = 1, 2, 3, 4: F (x1 , x2 , x3 , x4 , x5 , x6 ) = 2x1 + 3x2 → max при ограничениях y  x + 3x2 + x3 = 18,   1 2x1 + x2 + x4 = 16,  x2 + x5 = 5, 3x1 + x6 = 21 xj > 0, j = 1, 2, 3, 4, 5, 6. и Расширенная матрица канонической формы имеет вид:   1 3 1  2 1 0 1 0 0  0 1 0 0 1 0  3 0 0 0 0 1 2 3 0 0 0 0 Линейное программирование 18 16  5  . 21 max Стр. 10 из 136 JI JIxy y × y Оглавление 2.2 Графический метод решения задачи линейного программирования 2.2 Графический метод решения задачи линейного программирования y II JJ Рассмотрим реализацию графического метода на примере 1. Рассмотрим модель задачи в стандартной форме. Она состоит из системы ограничений в виде 6 неравенств (два из которых x1 > 0 и x2 > 0) и целевой функции. Так как в модели присутствуют только две переменные, то множество всех решений системы ограничений можно изобразить на плоскости в системе координат Ox1 x2 . Множество всех решений линейного неравенства ax1 + bx2 6 c на плоскости изображается в виде полуплоскости с граничной прямой ax1 + bx2 = c. В условиях задачи система ограничений состоит из 6 неравенств, поэтому решением системы изображается в виде выпуклой многоугольной области, которая является пересечением 6 полуплоскостей. Если эта область ограничена, то это многоугольник — максимум 6-угольник. Такой многоугольник (или многоугольная область) называется многоугольником (многоугольной областью) допустимых решений. Оптимальное решение находится в одном из допустимых решений. В общем случае n переменных в системе ограничений решением системы является выпуклая многогранная область (как пересечение конечного числа n-мерных полупространств) в nмерном пространстве, а если эта область является ограниченной — то выпуклым n-мерным многогранником. y Линейное программирование Стр. 11 из 136 JI JIxy y × y Оглавление 2.2 Графический метод решения задачи линейного программирования y II JJ В условиях рассматриваемой задачи для построения области допустимых решений лучше воспользоваться представлением неравенств в форме «отрезков», т. е. в виде неравенства y x + 6 1. a b y Граничная прямая xa + b = 1 в системе координат Oxy отсекает от координатных прямых Ox и Oy отрезки a и b, т. е. пересекает координатные оси в точках (a, 0) и (0, b), а заданная полуплоскость содержит начало координат O(0, 0). Представим первые два неравенства в форме отрезков: x1 x + 2 6 1, 18 6 x1 x + 2 6 1. 8 16 (2.4) Они задают полуплоскости, граничные прямые которых S1 и S2 не параллельны координатным осям. Неравенство x2 6 5 задает полуплоскость с граничной прямой S3 : x2 = 5, параллельной Ox1 , а неравенство 3x1 6 21 задает полуплоскость с граничной прямой S4 : x1 = 7, параллельной Ox2 . Неотрицательность переменных x1 и x2 означает, что нужно рассматривать только точки в I четверти. В результате получаем, что множество всех допустимых решений является 6-угольником A1 A2 A3 A4 A5 A6 (рис. 2.1). y Линейное программирование Стр. 12 из 136 JI JIxy y × y S3 1 6 4 5 4 x5 Оглавление 2.2 Графический решенияx6задачи S4 3 21метод 18 F 2 3 max программирования 24 F линейного S1 A B S2 A B S3 A B S4 A B x 18 3 -2 1 -3 X1=(0,0,18,16,5,21) y y Bazis Теперь рассмотрим множество всех пар (x1x1, x2 ),1 x2для котоx3 x4 2 16 функции равно заданному x2 1Друрых значение целевой числу. 8 x6 3 F -2 гими словами, изобразим на плоскости линию уровня целевой 5 10 5 X2=(0,5,3,11,0,21) функции. Изобразим, например, линию прибыли уровня 6, т. е. 7 Bazis x1 x2 x1 F = 6. Данная 7линия10 задается уравнением 2x1 + 3x1 2 = 60 или x1 + x2 = 1. Это прямая, пересекающая 6-угольник x4 допустимых h 1 x2 1 24 3 2 F = 24 x yточка, лежащая 23 25на линии x6 F = 6 и0 в области решений. Любая A -1 8,666667 F допустимых решений характеризует план производства, который B 13,5 -1 X3=(3,5,0,5,12) может Этот план дает Bazis прибыль в 01 размере 6 A1 A2 5 x1 x2 A3 быть реализован. 3 x1 A4 6 4 x5 A5 7 2 x2 1 A6 Fx6 -1 6 B 4 2,666667 -0,66667 X4=(6,4,0,0,1,3) 2 3 X4=X* ден. AF=6 ед. (рис. 2.1). 17 16 15 14 13 S2 12 11 10 9 8 7 6 A3 5 A2 4 3 2 F=6 1 A1 -2 -1-1 0 1 2 3 -2 y 6 II JJ S4 S3 A4 S1 A5 A6 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 Рис. 2.1. Область допустимых решений и линия уровня F = 6 целевой функции Линейное программирование Стр. 13 из 136 JI JIxy y × y A 5 B 5 Оглавление 2.210Графический метод решенияX2=(0,5,3,11,0,21) задачи S4 A 7 Bazis x1 линейного программирования B 7 10 x1 F = 12 12 h x4 x2 x6 F 1 13 1 x1 0 60 x2 1 x2 0 4 0 y II JJ x y 11 Рассмотрим другую линию прибыли F = 12: + = 1. A -1 4,666667 Заметим, что это тоже прямая, пересекающая 6-угольник допуB 7,5 -1 A1 решений3 стимых и параллельная линии F X3=(3,5,0,5,12) = 6. Значит, A2 Bazis x1 x2 прибыль A3 5 x1 1 A4 6 4 x5 A5 2 x2 1 A6 7 F=6 Fx6 A -1 2,666667 B 4 -0,66667 6 X4=(6,4,0,0,1,3) 2 3 X4=X* можно увеличить до уровня 12 ден. ед. (рис. 2.2)). 0 17 16 15 14 13 S2 12 11 10 9 8 7 6 A3 5 A2 4 3 F = 12 2 F=6 1 A1 -2 -1-1 0 1 2 3 4 5 -2 S4 S3 A4 S1 A5 A6 6 7 8 9 10 11 12 13 14 15 16 17 18 19 Рис. 2.2. Область допустимых решений и линия уровня F = 12 целевой функции Заметим, что при увеличении уровня прибыли линия прибыли смещается вправо-вверх (по направлению стрелок). И пока такая линия прибыли пересекает многоугольник допустимых решений соответствующий уровень прибыли может быть достигнут. Максимальное значение прибыли будет достигнуто только в том случае, когда дальнейший сдвиг линии прибыли не возможен. Но из-за выпуклости многоугольника допустимых решений это может случиться только в случае, когда линия прибыли проходит через одну из угловых точек многоугольника допустимых решений (рис. 2.3). y Линейное программирование Стр. 14 из 136 JI JIxy y × y A -1 8,666667 Оглавление 2.213,5 Графический метод решенияF задачи B -1 линейного программирования X3=(3,5,0,5,12) A1 A2 5 Bazis x1 A3 A4 A5 A6 F=6 A B 3 5 6 4 2 7 2,666667 -1 4 -0,66667 2 3 17 16 15 14 13 S2 12 11 10 9 F = 24 8 7 6 A3 5 A2 4 3 2 F=6 1 A1 -2 -1-1 0 1 2 3 -2 x1 x5 x2 Fx6 X4=(6,4,0,0,1,3) X4=X* 6 1 x2 1 S4 y II JJ S3 A4 S1 A5 F = 24 A6 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 Рис. 2.3. Оптимальный уровень F = 6 целевой функции В данной задаче оптимальное решение достигается в точке X ∗ (6, 4) = A4 , которая является точкой пересечения двух прямых S1 и S2 , определяемых первыми двумя ограничениями (2.4) в системе ограничений. В данной точке F (6, 4) = 24. Это означает, что нужно производить 6 единиц первого продукта и 4 единицы второго, тогда прибыль достигнет максимального значения — 24 ден. ед. y Линейное программирование Стр. 15 из 136 JI JIxy y × y y y y Оглавление 2.2 Графический метод решения задачи линейного программирования II JJ Основные выводы из графического решения задачи линейного программирования Первый общий вывод (основанный на свойствах выпуклости): если в задаче линейного программирования имеется оптимальное решение, то оно обязательно содержится в одной из угловых точек (является вершиной) многогранной области допустимых решений. Каждой угловой точке многогранника допустимых решений в канонической системе ограничений соответствует базисное решение системы линейных уравнений1 и, наоборот, каждому базисному решению канонической системы ограничений соответствует угловая точка многогранника допустимых решений. Это свойство позволяет сделать еще один общий вывод. Второй общий вывод: Оптимальное решение задачи линейного программирования имеется среди базисных решений канонической системы ограничений (системы линейных уравнений). Поэтому для решения задачи линейного программирования достаточно найти все базисные решения канонической системы ограничений и выбрать среди них наилучшее. 1 Выделяют основные (базисные) и неосновные (свободные) переменные. Число основных переменных должно совпадать с максимальным числом линейно независимых уравнений в системе, остальные переменные принимаются неосновными. В базисном решении системы линейных уравнений неосновные переменные принимают нулевые значения , с учетом этого базисным переменным соответствуют однозначные (обычно не нулевые) значения. Линейное программирование Стр. 16 из 136 JI JIxy × y Оглавление 2.3 Симплексный метод решения задачи линейного программирования 2.3 Симплексный метод решения задачи линейного программирования y II JJ Пусть в модели линейного программирования n + m переменных и m уравнений-ограничений (в канонической форме). Предположим, что оптимальное значение целевой функции конечно. В этом случае вычислительная процедура симплексного метода будет выглядеть следующим образом: Шаг 1. Выбираем из уравнений m переменных, задающих допустимое исходное базисное решение. Как правило, в качестве исходного базисного решения могут быть взяты дополнительные переменные, введенные в условия-ограничения при приведении модели к каноническому виду. Каждая из этих переменных входит только в одно ограничение и не содержится в выражении целевой функции. Шаг 2. Проверяем, нельзя ли за счет одной из неосновных переменных, приравненных в начале к нулю, улучшить значение целевой функции, придавая этой переменной отличное от нуля положительное значение. Если такой неосновной переменной нет, прекращаем вычисления, так как оптимальное решение найдено. Шаг 3. Находим предельное (максимально допустимое) значение наденной переменной. Увеличение значения выбранной переменной возможно до тех пор, пока одна из m переменных, вошедших в пробное (базисное) решение, не обратится в нуль. Вводим новую переменную в пробное (базисное) решение. Шаг 4. Разрешаем систему m уравнений относительно переменных, вошедших в пробное (базисное) решение, и исключаем их из выражения целевой функции. Возвращаемся к шагу 2. Данный алгоритм приводит к оптимальному решению для любой модели линейного программирования за конечное число шагов (итераций). Такой способ решения задачи линейного программирования называется симплексным алгоритмом. y Линейное программирование Стр. 17 из 136 JI JIxy y × y Оглавление 2.3 Симплексный метод решения задачи линейного программирования y II JJ Пример 2.2. Рассмотрим реализацию симплекс-метода на примере задачи 1 об использовании ресурсов. Решение. Рассмотрим каноническую форму задачи и представим целевую функцию как уравнения в системе ограничений в канонической форме: оставим в правой части только свободный член, а все остальное перенесем в левую часть: F (x1 , x2 , x3 , x4 , x5 , x6 ) − 2x1 − 3x2 = 0. Шаг 1. В качестве основных (базисных) переменных выберем дополнительные переменные x3 , x4 , x5 , x6 ; неосновные (свободные) переменные — x1 , x2 . Заметим, что целевая функция изначально выражается через неосновные переменные. Теперь выразим основные переменные через неосновные в системе ограничений:  x   3 x4  x5 x6 = 18 − x1 − 3x2 , = 16 − 2x1 − x2 , = 5 − x2 , = 21 − 3x1 . В базисном решении неосновные переменные принимают нулевые значения, поэтому x1 = x2 = 0, а основные переменные будут равны соответствующим свободным членам в системе ограничений: x3 = 18, x4 = 16, x5 = 5, x6 = 21. Получили первое базисное решение X1 = (0, 0, 18, 16, 5, 21), которое является допустимым. Для этого решения значение целевой функции принимает нулевое значение: F (X1 ) = 0. y Линейное программирование Стр. 18 из 136 JI JIxy y × y y y y Оглавление 2.3 Симплексный метод решения задачи линейного программирования II JJ Значение целевой функции может быть улучшено (увеличено), если значение x1 или x2 взять положительным. Наибольший эффект может быть достигнут за счет переменной x2 , так как перед ней в целевой функции стоит наибольший по модулю коэффициент. Обычно используют следующий КРИТЕРИЙ ОПТИМАЛЬНОСТИ Для целевой функции, которую нужно максимизировать: если у целевой функции в каноническом виде имеется переменная с отрицательным коэффициентом, то её значение может быть улучшено; в противном случае значение целевой функции улучшить нельзя и полученное базисное решение X является оптимальным: X = X∗. Для целевой функции, которую нужно минимизировать: если у целевой функции в каноническом виде имеется переменная с положительным коэффициентом, то её значение может быть улучшено; в противном случае значение целевой функции улучшить нельзя и полученное базисное решение X является оптимальным: X = X∗. Линейное программирование Стр. 19 из 136 JI JIxy × y y II JJ Оглавление 2.3 Симплексный метод решения задачи линейного программирования В нашем случае это означает, что переменную x2 необходимо ввести в список основных (базисных) переменных. В симплексной таблице выделим столбец, содержащий переменную x2 . Выясним, за счет какой переменной это можно сделать. Если все переменные, кроме x2 , будут принимать нулевое значение, то из первого ограничения получаем 3x2 6 18 или x3 6 6; из второго ограничения x2 6 16; из третьего ограничения x2 6 5; из четвертого уравнения 0x2 6 21, т. е. может быть любым. Таким образом максимальное значение x2 будет равно min{6, 16, 5, ∞} = 5 и ограничением максимума является третье уравнение. Это уравнение еще называется разрешающим. В симплексной таблице выделим строку, содержащую коэффициенты разрешающего уравнения. На следующем шаге переменную x2 вводят в базис вместо x5 . В результате перехода значение целевой функции будет улучшено (увеличено) на 3 · 5 = 15. Результаты представим в виде симплекс-таблицы 2.1: Базис x3 x4 x5 x6 F x1 1 2 3 -2 Таблица 2.1. Результаты шага 1 x2 x3 x4 x5 x6 3 1 1 1 1 1 1 -3 bi 18 16 5 21 bi /aij 6 16 5 ∞ В последнем столбце таблицы рассчитываются оценочные отношения abiji , по которым определяется разрешающее уравнение. Во внимание принимаются только неотрицательные значения оценочных отношений, так как при делении на отрицательное число знак неравенства меняется на противоположный! Минимальное значение такого отношения соответствует разрешающему уравнению и базисной переменной, которую нужно вывести из базиса. y Линейное программирование Стр. 20 из 136 JI JIxy y × y Оглавление 2.3 Симплексный метод решения задачи линейного программирования y II JJ Шаг 2. В основные (базисные) переменные — x2 , x3 , x4 , x6 ; неосновные переменные — x1 , x5 . Выразим основные переменные через неосновные в системе ограничений и целевой функции:  x   2 x3  x4 x6 = 5 − x5 , = 18 − x1 − 3(5 − x5 ) = 3 − x1 + 3x5 , = 16 − 2x1 − (5 − x5 ) = 11 − 2x1 + x5 , = 21 − 3x1 . F − 2x1 − 3(5 − x5 ) = 0 ⇒ F − 2x1 + 3x5 = 15. Пересчет коэффициентов симплексной таблицы по правилу прямоугольника. Данное правило используют для упрощения процедуры вычислений коэффициентов симплексной таблицы. В симплексной таблице столбец будем называть разрешающим столбцом, если он содержит переменную, которую нужно будет ввести в список основных на следующем шаге. Строку, содержащую коэффициенты разрешающего уравнения, будем называть разрешающей строкой. Элемент таблицы, лежащий на разрешающей строке и разрешающем столбце, будем называть разрешающим элементом. y Линейное программирование Стр. 21 из 136 JI JIxy y × y y II JJ Оглавление 2.3 Симплексный метод решения задачи линейного программирования Пусть aij — разрешающий элемент, т. е. i-я строка и j-й столбец являются разрешающими. Для любого элемента dil разрешающей строки (коэффициента при переменной или свободного члена разрешающего уровнения) новое значение dil0 получается из старого dil путем его деления на разрешающий элемент: d dil0 = il . aij Для любого другого элемента dkl данной таблицы, не лежащей на разрешающей строке (l 6= i), пересчет осуществляется по следующей формуле: dkl = dil · dkj dkl · aij − dil · dkj = dkl − . aij aij Данную формулу хорошо иллюстрирует правило прямоуголь0 получается как отношение разника : значение элемента dkl ности произведений элементов диагонали прямоугольника, содержащей разрешающий элемент, и элементов другой диагонали к величине разрешающего элемента (табл. 2.2). Таблица 2.2. Прямоугольник расчета коэффициента d a −d d dkl = kl ij aij kj il Базис ··· xk ··· xi ... ··· ... ··· ... xl ··· dkl ··· dil ... ··· ... ··· ... xj ··· dkj ··· aij ... ··· ... ··· ... ··· ··· ··· ··· ··· ··· y Линейное программирование Стр. 22 из 136 JI JIxy y × y y II JJ Оглавление 2.3 Симплексный метод решения задачи линейного программирования Таким образом, на втором шаге получим базисное решение X2 = (0, 5, 3, 11, 0, 21) и F (X2 ) = 15. Результаты этих и дальнейших расчетов представлены в таблицах 2.3–2.5. Базис x3 x4 x2 x6 F x1 1 2 3 -2 Таблица 2.3. Результаты шага 2 x2 x3 x4 x5 x6 1 -3 1 -1 1 1 1 3 bi 3 11 5 21 15 bi /aij 3 51 2 ∞ 7 Базис x1 x4 x2 x6 x1 1 Таблица 2.4. Результаты шага 3 x2 x3 x4 x5 x6 1 -3 -2 1 5 1 1 -3 9 1 bi 3 5 5 12 bi /aij -1 1 5 11 3 F 21 2 -3 Базисное решение X3 = (3, 5, 0, 5, 0, 12) и F (X3 ) = 21. y Линейное программирование Стр. 23 из 136 JI JIxy y × y Базис x1 x5 x2 x6 x1 1 Таблица 2.5. x2 x3 -1/5 -2/5 1 2/5 3/5 F 4/5 Результаты шага 4 x4 x5 x6 3/5 1/5 1 -1/5 1 -1 4 5 3/5 y II JJ Оглавление 2.3 Симплексный метод решения задачи линейного программирования bi 6 1 4 3 bi /aij 24 Базисное решение X4 = (6, 4, 0, 0, 1, 3) и F (X4 ) = 24. В последней таблице у целевой функции нет коэффициентов со знаком «минус», поэтому значение целевой функции улучшить нельзя и полученное базисное решение является оптимальным, т. е. X ∗ = X4 = (6, 4, 0, 0, 1, 3) и F (X ∗ ) = 24 — максимальное значение целевой функции. Таким образом, план производства — 6 единиц первой продукции и 4 единицы второй продукции, максимальное прибыль при этом составит 24 ден. ед. y Линейное программирование Стр. 24 из 136 JI JIxy y × y Оглавление 2.4 Метод больших штрафов (М-метод) 2.4 Метод больших штрафов (М-метод) y II JJ При реализации симплекс-алгоритма на первом шаге в качестве основных переменных выбираются дополнительные переменные, вводимые в систему ограничений для получения ограничений в виде уравнения (равенства). При таком подходе в получаемом базисном решении основные переменные принимают значения, равные свободным членам либо значения противоположного знака. Таким образом, получаемое базисное решение не всегда получается допустимым. Например, изначально система ограничений могла быть несовместной. Для получения первого допустимого базисного решения используют искусственные переменные y1 >, y2 > 0, . . ., которые вводятся в те уравнения (или даже во все уравнения), в которых дополнительная переменная входит в левую часть со знаком, отличным от знака свободного члена. Знак коэффициентов искусственных переменных должен совпадать со знаком свободного члена. Тогда при выборе в качестве основных переменных y1 , y2 , . . . получается допустимое базисное решение. При реализации симплекс-алгоритма все искусственные переменные должны быть выведены из списка основных переменных. Чтобы это произошло в вводят функцию больших штрафов, которая ухудшает значение целевой функции. y Линейное программирование Стр. 25 из 136 JI JIxy y × y Оглавление 2.4 Метод больших штрафов (М-метод) Пусть исходная целевая функция на максимум имеет вид: F (x1 , . . . xn ) = c1 x1 + . . . + cn xn → max . y II JJ Рассмотрим функцию штрафов T (y1 , . . . , yn ) = M(y1 + y2 + . . .) и составим новую целевую функцию: F 0 (x1 , . . . xn , y1 , y2 , . . .) = c1 x1 + . . . + cn xn − M(y1 + y2 + . . .), где M — большое число (штраф) превышающее все коэффициенты целевой функции F . Для максимизации целевой функции F 0 все искусственные переменные yi необходимо вывести из списка основных. Но тогда Fmax совпадет с Fmax . Таким образом, исходная задача будет решена. Замечание. Если на последнем шаге симплекс метода будет получена симплекс-таблица, содержащая искусственные переменные в качестве основных переменных, то это будет означать, что какое-то уравнение в канонической системе ограничений без искусственной переменной не будет выполняться, т. е. исходная система ограничений является несовместной — не имеет решений. y Линейное программирование Стр. 26 из 136 JI JIxy y × y Оглавление 2.4 Метод больших штрафов (М-метод) y II JJ Пример 2.3. Реализация метода больших штрафов (Мметода). Найти решение задачи линейного программирования: Z(x1 , x2 , x3 , x4 ) = 18x1 + 16x2 + 5x3 + 21x4 → min при ограничении  1x1 + 2x2 + 0x3 + 3x4 > 2, 3x1 + 1x2 + 1x3 + 0x4 > 3; xj > 0, j = 1, 2, 3, 4. Решение. Перейдем к задаче на максимум и рассмотрим новую целевую функцию F (X) = −Z(X) = −18x1 − 16x2 − 5x3 − 21x4 . Приведем систему ограничений к каноническому виду. Так как правая часть больше левой, то для получения канонической формы вычтем в каждом неравенстве из левой части по дополнительной переменной, принимающей неотрицательные значения:  1x1 + 2x2 + 0x3 + 3x4 − x5 = 2, 3x1 + 1x2 + 1x3 + 0x4 − x6 = 3; x1 > 0, . . . , x6 > 0. Если взять в качестве базисных переменных x5 и x6 , то первое базисное решение X1 = (0, 0, 0, 0, −2, −3) будет недопустимым. y Линейное программирование Стр. 27 из 136 JI JIxy y × y Оглавление 2.4 Метод больших штрафов (М-метод) y II JJ В рассматриваемом примере обе дополнительные переменные x5 и x6 входят в левую часть ограничений со знаком, отличном от знака свободного члена правой части ограничения. Поэтому полученное базисное решение оказалось недопустимым. Воспользуемся искусственными переменными y1 и y2 . Введем их по одному в левую часть каждого ограничения (уравнение) с тем же знаком уравнения, что и свободный член в правой части:  1x1 + 2x2 + 0x3 + 3x4 − x5 + y1 = 2, 3x1 + 1x2 + 1x3 + 0x4 − x6 + y2 = 3; x1 > 0, . . . , x6 > 0, y1 > 0, y2 > 0. Теперь выберем в качестве основных переменные y1 и y2 , тогда неосновными будут x1 , . . . , x6 и первое базисное решение X1 = (0, 0, 0, 0, 0, 0, 2, 3), где y1 = 2 и y2 = 3, является допустимым. В результате реализации симплекс-метода все искусственные переменные должны быть выведены из базиса, иначе полученное на последнем шаге базисное решение окажется недопустимым (некоторые базисные переменные войдут в решение с отрицательными значениями). Чтобы в оптимальном решении не осталось искусственных переменных введем в целевую функцию большой штраф M за присутствие в целевой функции искусственных переменных. Рассмотрим вспомогательную целевую функцию y F 0 = −18x1 − 16x2 − 5x3 − 21x4 − M(y1 + y2 ), y где M — размер штрафа — большое число, превосходящее все коэффициенты в целевой функции. Заметим, что функция когда искусственные пеF 0 достигает своего максимума Fmax ременные обращаются в нуль и Fmax = Fmax . В нашем случае возьмем M = 100. Линейное программирование Стр. 28 из 136 JI JIxy × y Выразим основные (искусственные) неосновные переменные:  переменные y II JJ Оглавление 2.4 Метод больших штрафов (М-метод) через y1 = 2 − 1x1 − 2x2 − 0x3 − 3x4 + x5 , y2 = 3 − 3x1 − 1x2 − 1x2 − 0x4 + x6 ; подставим в целевую функцию и приведем подобные слагаемые: F 0 = −18x1 − 16x2 − 5x3 − 21x4 − 100(y1 + y2 ) = = −18x1 − 16x2 − 5x3 − 21x4 − − 100(2 − 1x1 − 2x2 − 0x3 − 3x4 + x5 + + 3 − 3x1 − 1x2 − 1x3 − 0x4 + x6 ) = = −500 + 382x1 + 284x2 + 95x3 + 279x4 − 100x5 − 100x6 . В целевой функции перенесем все переменные в левую часть, а свободный член оставим в правой части: F 0 − 382x1 − 284x2 − 95x3 − 279x4 + 100x5 + 100x6 = −500. (2.5) Для первого базисного решения X1 = (0, 0, 0, 0, 0, 0, 2, 3) значение целевой функции F 0 (X1 ) = −500 не является максимальным, так как согласно критерию оптимальности в выражении целевой функции (на максимум) имеются отрицательные коэффициенты при x1 , . . . , x4 . y Линейное программирование Стр. 29 из 136 JI JIxy y × y Оглавление 2.4 Метод больших штрафов (М-метод) y II JJ Наибольшее влияние на целевую функцию оказывает x1 , так как эта переменная входит в целевую функцию с максимальным по модулю коэффициентом (−382). На следующем шаге в базис введем x1 . Выясним вместо какой базисной переменной это можно сделать. Вычислим оценочное отношения для каждого уравнения. Из первого уравнения системы ограничений следует, что x1 6 12 = 2, а из второго — x1 6 33 = 1. Так как min{1, 2} = 1, то x1 6 1, максимальное значение переменной x1 ограничивается вторым уравнением в системе ограничений и оно достигается когда y1 = 0. Таким образом на следующем шаге из базиса выводится переменная y1 и вместо неё вводится x1 . Дальнейшие шаги осуществляются в соответствии с обычным симплекс-методом — с помощью симплекс-таблиц. Полное решение задачи представлено ниже. Таблица 2.6. Результаты ввода в базис переменной y2 (итоги первого шага М-метода) Базис x1 x2 x3 x4 x5 x6 y1 y2 bi bi /aij y1 1 2 3 -1 1 2 2 y2 3 1 1 -1 1 3 1 F -382 -284 -95 -279 100 100 0 -500 В данной таблице коэффициенты первых двух строк соответствуют первоначальным значениям канонической системы ограничений. Поменялись только коэффициенты целевой функции, они стали соответствовать формуле (2.5), полученной ранее с помощью обычной подстановки. y Линейное программирование Стр. 30 из 136 JI JIxy y × y Оглавление 2.4 Метод больших штрафов (М-метод) y II JJ Базисное решение X1 = (0, 0, 0, 0, 0, 0, 2, 3) является допустимым и значение целевой функции F 0 (X1 ) = −500. По критерию оптимальности это решение не является оптимальным и оно может быть улучшено за счет переменной x1 , у которой коэффициент в целевой функции входит с отрицательным значением (−382) и имеет наибольший модуль. Оценочные отношения, представленные в последнем столбце таблицы 2.6 показывают, что вторая строка является разрешающей, т. е. на следующем шаге в базис вводится переменная x1 вместо y2 . Результаты остальных шагов представлены в таблицах 2.7– 2.9 Базис y1 x1 F0 Таблица 2.7. Результаты второго шага М-метода x1 x2 x3 x4 x5 x6 y1 y2 bi bi /aij 2 -1/3 3 -1 1/3 1 -1/3 1 1/3 1 3 1 1/3 1/3 0 -1/3 0 1/3 1 ∞ 2 1 1 1 0 -156 -279 100 -27 0 127 -118 32 3 3 3 3 Базисное решение X2 = (1, 0, 0, 0, 0, 0, 1, 0) и F 0 (X2 ) = −118 может быть улучшено за счет x4 . Базис x4 x1 y F0 Таблица 2.8. Результаты третьего шага М-метода x1 x2 x3 x4 x5 x6 y1 y2 bi bi /aij 5/9 -1/9 1 -1/3 1/9 1/3 -1/9 1/3 3/5 1 1/3 1/3 0 -1/3 0 1/3 1 3 2 1 2 1 7 93 96 -25 -1 1 3 3 3 3 3 y Базисное решение X3 = (1, 0, 0, 13 , 0, 0, 0, 0) и F 0 (X2 ) = −25 может быть улучшено за счет x2 . Линейное программирование Стр. 31 из 136 JI JIxy × y Оглавление 2.4 Метод больших штрафов (М-метод) Базис x2 x1 F0 Таблица 2.9. Результаты четвертого x1 x2 x3 x4 x5 x6 1 -1/5 1 4/5 -3/5 1/5 1 2/5 -3/5 1/5 -2/5 1 3 6 4 шага y1 3/5 -1/5 94 М-метода y2 bi bi /aij -1/5 3/5 2/5 4/5 96 -24 y II JJ
Базисное решение X4 = 45 , 53 , 0, 0, 0, 0, 0, 0 и F 0 (X4 ) = −24 не может быть улучшено, так как все коэффициенты целевой функции положительны. Таким образом, X ∗ = X4 , Fmax = F 0 (X ∗ ) = Fmax = F (X ∗ ) = −24, а исходная целевая функция Z достигает своего минимума:
Zmin = 24 в точке X ∗ = 54 , 53 , 0, 0 , в частности, при x1 = 45 , x2 = 35 , x3 = x4 = 0. y Линейное программирование Стр. 32 из 136 JI JIxy y × y Оглавление 2.5 Решение задачи оптимизации с помощью «Поиска решения» 2.5 Решение задачи оптимизации с помощью «Поиска решения» y II JJ Реализация оптимизационных моделей легко осуществляется с помощью надстройки «Поиск решения» Excel. Вызов этой надстройки в MS Excel 2010 и более поздних версиях осуществляется через меню «Данные». Для первого вызова необходимо установить надстройку через главное меню «Файл», далее «Параметры / Надстройки / Управление: Надстройки Excel Перейти. . . ». y Линейное программирование Стр. 33 из 136 JI JIxy y × y Оглавление 2.5 Решение задачи оптимизации с помощью «Поиска решения» y II JJ Пример 2.4. Рассмотрим решение задачи линейного программирования с помощью надстройки «Поиск решения» на примере 1. Решение. Пусть x1 и x2 — объем выпуска первой и второй продукции. Тогда экономико-математическая модель данной задачи имеет следующий вид: Найти F (x1 , x2 ) = 2x1 + 3x2 → max при ограничениях:  x + 3x2 6 18,   1 2x1 + x2 6 16,  x2 6 5, 3x1 6 21 и x1 > 0, x2 > 0. Данная задача в краткой форме может быть представлена в виде расширенной матрицы:   1 3  2 1  0 1  3 0 2 3 18 16  5  , 21 max из которой легко восстанавливаются все условия задачи. y Линейное программирование Стр. 34 из 136 JI JIxy y × y y II JJ Оглавление 2.5 Решение задачи оптимизации с помощью «Поиска решения» Для решения средствами Excel нужно: 1. Ввести такую же таблицу в Excel, переставив последнюю строку в первую. 2. Добавить еще одну строку, сделав ее первой: первые два элемента пусть будут нулевыми (начальные значения переменных, которые потом будут изменяться), а под знаком «F » — выражение (формула) целевой функции F (первоначальное ее значение при нулевых переменных тоже будет нулевым). 3. Добавить еще один столбец из четырех элементов, в котором каждый элемент — выражение (формула), вычисляющее значение левой части соответствующего ограничения (при первоначальных нулевых переменных значения также будут нулевыми). В результате в Excel будет получена таблица 2.10: Таблица 2.10. Исходные данные A 1 2 3 4 5 6 7 B Продукт 1 C Продукт 2 D F (ЦФ) 2 1 2 3 3 3 1 1 Переменные (план производства) Коэффициенты ЦФ Ресурс 1 Ресурс 2 Ресурс 3 Ресурс 4 8 y E 18 16 5 21 План Запасы использования ресурсов ресурсов y Наиболее простой способ введения формул в ячейках D3:D7 следующий: в ячейке D3 запишем: =СУММПРОИЗВ($B$2:$C$2;B3:C3), в остальных ячейках соответствующие формулы получим с помощью копирования (протягивания). Линейное программирование Стр. 35 из 136 JI JIxy × y y y y Оглавление 2.5 Решение задачи оптимизации с помощью «Поиска решения» II JJ 4. Вызвать надстройку «Поиск решения» (будем считать, что данная надстройка установлена). В появившемся окне нужно: а) указать целевую ячейку $D$3; б) установить флажок на поиск максимального значения; в) ввести изменяемые ячейки $B$2:$C$2; г) добавить ограничения: — нажать кнопку «Добавить» — появится окно «Добавление ограничения»; — в левой части окна ввести вектор значений левой части ограничений $D$4:$D$7; — в правой части окна ввести вектор данных ограничений $E$4:$E$7; — в центральной части окна выбрать соответствующий знак неравенства (<=) и нажать кнопку «OK»; д) указать, что переменные могут принимать только неотрицательные значения (данный режим включен по умолчанию), выбрать поиск решения линейных задач симплекс-методом (в окошке «Выбирите метод решения»); е) на панели «Поиск решения» нажать кнопку «Найти решение». После этого покажется окно с результатами вычислений. В нем можно указать типы отчетов для получения дополнительной информации. В результате решения некоторые ячейки введенной таблицы поменяют свои значения (табл. 2.11). Линейное программирование Стр. 36 из 136 JI JIxy × y Таблица 2.11. Результаты поиска решения A 1 2 3 4 5 6 7 Переменные (план производства) Коэффициенты ЦФ Ресурс 1 Ресурс 2 Ресурс 3 Ресурс 4 B C Продукт 1 Продукт 2 D 6 4 F (ЦФ) 2 3 24 1 2 3 3 1 1 8 y II JJ Оглавление 2.5 Решение задачи оптимизации с помощью «Поиска решения» E 18 18 16 16 4 5 18 21 План испольЗапасы зования ресурсов ресурсов Таким образом, максимальное значение целевой функции равно 24 и достигается при x1 = 6 и x2 = 4, при этом для оптимального решения в системе ограничений первые два неравенства обращаются в равенства, а остальные — в строгие неравенства. Экономический смысл данного решения задачи заключается в следующем: оптимальный план производства предполагает производство 6 единиц продукции первого вида и 4 единицы продукции второго вида, этот план обеспечивает максимально возможную прибыль в размере 24 ден. ед. y Линейное программирование Стр. 37 из 136 JI JIxy y × y Оглавление В.М. Караулов Глава 3 Двойственность y II JJ Каждой задаче линейного программирования соответствует другая задача, называемая двойственной или сопряженной по отношению к исходной. Теория двойственности позволяет проводить качественные исследования задач линейного программирования, в частности, анализировать устойчивость оптимального плана. y Двойственность Стр. 38 из 136 JI JIxy y × y Оглавление 3.1 Экономическая интерпретация прямой и двойственной задач линейного программирования 3.1 y II JJ Экономическая интерпретация прямой и двойственной задач линейного программирования Пусть исходная задача линейного программирования — задача I об использовании ресурсов: предприятие 1 может производить несколько видов продукции P1 , . . . , Pn , используя при этом несколько видов ресурсов S1 , . . . , Sm ; известны запасы этих ресурсов — b1 , . . . , bm и норма их использования — aij — расход ресурса i-го вида при производстве единицы продукта Pj . Также известна норма прибыли cj — прибыль, получаемая при производстве и реализации единицы продукции Pj . Требуется составить план производства обеспечивающий максимальную совокупную прибыль, с учетом имеющихся норм использования ресурсов, прибыльности производства и запасов ресурсов. Экономико-математическая модель этой задачи имеет вид: найти такой план производства x1 , . . . , xj , . . . , xn , где xj — план производства продукта Pj , j = 1, . . . , n, чтобы F (x1 , . . . , xn ) = c1 x1 + . . . + cj xj + . . . + cn xn → max при ограничениях  a x + a12 x2 + . . . + a1j xj + . . . + a1n xn 6 b1 ,   11 1 a21 x1 + a22 x2 + . . . + a2j xj + . . . + a2n xn 6 b2 , ··· ··· ···   ··· am1 x1 + am2 x2 + . . . + amj xj + . . . + amn xn 6 bm , y x1 > 0, . . . , xj > 0, . . . , xn > 0. Двойственность Стр. 39 из 136 (3.1) (3.2) y (3.3) JI JIxy × y Оглавление 3.1 Экономическая интерпретация прямой и двойственной задач линейного программирования y II JJ Рассмотрим альтернативное поведение предприятия 1: прибыль можно получить в рамках осуществления производственного процесса, а можно получить прибыль, продав имеющиеся ресурсы. Построим экономико-математическую модель такого поведения. Пусть y1 , . . . , yi ,. . . , ym — цены, по которым предприятие 1 желает продать все свои ресурсы S1 , . . . , Si , . . . , Sm , т. е. в объемах b1 , . . . , bm предприятию 2. В рамках этой сделки предприятие 2 будет стремиться, чтобы Z(y1 , . . . , ym ) = b1 y1 + . . . + bi yi + . . . + bm ym → min . С другой стороны, фирма 1 пойдет на такую сделку только в том случае, когда прибыль от продажи ресурсов окажется не менее чем от их использовании в производственном процессе. При производстве единицы продукта Pj получается прибыль в размере cj , но при этом будет использоваться a1j единиц ресурса S1 , a2j единиц ресурса S2 , . . . , aij единиц ресурса Si , . . . , amj единиц ресурса Sm . Если эти объемы ресурсов будут проданы предприятию 2, то прибыль от продажи составит: a1j y1 + a2j y2 + . . . + aij yi + . . . + amj ym . Значит, предприятие 1 согласится продать свои ресурсы, если выгода от продажи ресурсов окажется не ниже от выгоды использовании в производственном процессе по всем видам продукции:  a11 y1 + a21 y2 + . . . + ai1 yi + . . . + am1 ym > c1 ;    a y + a22 y2 + . . . + ai2 yi + . . . + am2 ym > c2 ;    12 1 ... ... ... ... a y + a y + . . . + a yi + . . . + amj ym > cj ;  ij 1j 1 2j 2    . . . . . . . . . . ..   a1n y1 + a2n y2 + . . . + ain yi + . . . + amn ym > cn . y Двойственность Стр. 40 из 136 JI JIxy y × y Оглавление 3.1 Экономическая интерпретация прямой и двойственной задач линейного программирования y II JJ Таким образом, с учетом неотрицательности цен сделка по продаже ресурсов описывается следующей экономико-математической моделью: Z(y1 , . . . , ym ) = b1 y1 + . . . + bi yi + . . . + bm ym → min . (3.4)  a11 y1 + a21 y2 + . . . + ai1 yi + . . . + am1 ym > c1 ;    a y + a22 y2 + . . . + ai2 yi + . . . + am2 ym > c2 ;    12 1 ... ... ... ... a y + a y + . . . + a yi + . . . + amj ym > cj ;  ij 1j 1 2j 2    . . . . . . . . . . ..   a1n y1 + a2n y2 + . . . + ain yi + . . . + amn ym > cn . (3.5) y1 > 0, y2 > 0, . . . , yi > 0, . . . , ym > 0. (3.6) Это и есть модель задачи II линейного программирования, двойственной к исходной задаче, описываемой моделью (3.1)– (3.3). y Двойственность Стр. 41 из 136 JI JIxy y × y y II JJ Оглавление 3.1 Экономическая интерпретация прямой и двойственной задач линейного программирования Представление прямой и двойственной задач линейного программирования в виде расширенных матриц позволяет обнаружить связь между этими задачами не только в экономическом смысле, но и в представлении экономикоматематических моделей. Для прямой задачи I и двойственной задачи II расширенные матрицы имеет соответственно вид:     a11 a12 a22 ... ai2 ... m1 am2 c1 c2  a21  ...   ai1   ... a ... ... ... ... ... ... ... a1j a2j ... aij ... amj cj ... ... ... ... ... ... ... a1n a2n ... ain ... amn cn b1 b2  ...   bi   ...  bm  max a11 a21 a22 ... a2j ... 1n a2n b1 b2  a12  ...   a1j   ... a ... ... ... ... ... ... ... ai1 ai2 ... aij ... ain bi ... ... ... ... ... ... ... am1 am2 ... amj ... amn bm c1 c2  ...   cj   ...  cn  min Эти матрицы получаются друг из друга при помощи операции транспонирования, при этом цель оптимизации меняется на противоположную (максимум — на минимум, а минимум — на максимум) и в ограничениях знак неравенства меняется на противоположный («6» — на «>», а «>» — на «6»). y Двойственность Стр. 42 из 136 JI JIxy y × y Оглавление 3.1 Экономическая интерпретация прямой и двойственной задач линейного программирования 3.1.1 Первая теорема двойственности 3.1.1 y II JJ Пусть X — произвольное допустимое решение, а X ∗ — оптимальное допустимое решение прямой задачи на максимум. Пусть Y — произвольное допустимое решение, а Y ∗ — оптимальное допустимое решение двойственной задачи на минимум. Тогда F (X) 6 F (X ∗ ) = Z(Y ∗ ) 6 Z(Y ). Другими словами, оптимальные значения целевых функций прямой и двойственной задач совпадают. Данный факт легко объясняется экономическим смыслом прямой и двойственной задач. С одной стороны, затраты предприятия 2 не могут быть меньше, чем прибыль предприятия 2 при оптимальном плане. С другой стороны, если сделка состоится, то предприятие 2 на приобретение ресурсов затратит не более чем размер извлекаемой прибыли при производстве продукции. Поэтому минимальные затраты предприятия 2 совпадут с максимальной прибылью предприятия 1. y Двойственность Стр. 43 из 136 JI JIxy y × y Оглавление 3.1 Экономическая интерпретация прямой и двойственной задач линейного программирования 3.1.1 y II JJ Первая (основная) теорема двойственности. Если одна из двух взаимно-двойственных задач линейного программирования имеет оптимальное решение, то его имеет и другая, причем оптимальные значения их целевых функций равны: Fmax = F (X ∗ ) = Z(Y ∗ ) = Zmin . Если целевая функция одной из задач не ограничена, то условия другой задачи противоречивы. y Двойственность Стр. 44 из 136 JI JIxy y × y Оглавление 3.1 Экономическая интерпретация прямой и двойственной задач линейного программирования 3.1.2 3.1.2 Вторая теорема двойственности y II JJ Запишем прямую и двойственную задачи в каноническом виде: к прямой задачи введем дополнительные переменные (со знаком плюс) xn+1 , . . . , xn+m , а в двойственной введем дополнительные переменные (со знаком минус) ym+1 , . . . , ym+n . Установим соответствие между первоначальными переменными одной из двойственных задач и дополнительными переменными другой задачи (табл. 3.1). x1 l ym+1 Таблица 3.1. Соответствие между переменными Переменные исходной задачи I Первоначальные Дополнительные xj . . . xn xn+1 xn+2 . . . xn+i . . . xn+m x2 . . . l ... l ... l l l ... l ... l ym+2 . . . ym+j . . . ym+n y1 y2 . . . yi . . . ym Дополнительные Первоначальные Переменные двойственной задачи II Теорема. Положительным (ненулевым) компонентам оптимального решения одной из взаимно двойственных задач соответствуют нулевые компоненты оптимального решения другой задачи, т. е. для любых i = 1, . . . , m и j = 1, . . . , n: ∗ ∗ > 0, то y∗ = 0, и аналогичесли xj∗ > 0, то ym+j = 0; если xn+i i ∗ ∗ ∗ но, если yi > 0, то xn+i = 0; если ym+j > 0, то xj∗ = 0. y Двойственность Стр. 45 из 136 JI JIxy y × y Оглавление 3.1 Экономическая интерпретация прямой и двойственной задач линейного программирования 3.1.2 y II JJ Свойства, сформулированные в теореме можно выразить в виде условий дополняющей нежесткости:  m P ∗ ∗   xn+i yi = 0,  i=1 n P  ∗  xj∗ ym+j = 0.  j=1 Это означает, что между переменными взаимно двойственных задач при достижении оптимума (на последнем шаге решения каждой задачи симплексным методом) представляет соответствие между основными (обычно не равными нулю) переменными одной из двух двойственных задач и неосновными (равными нулю) переменными другой задачи, когда обе образуют допустимое базисное решение. Данный факт вытекает из следующего более общего утверждения. y Двойственность Стр. 46 из 136 JI JIxy y × y Оглавление 3.1 Экономическая интерпретация прямой и двойственной задач линейного программирования 3.1.2 y II JJ Вторая теорема двойственности. Компоненты оптимального решения двойственной задачи равны абсолютным значениям коэффициентов при соответствующих переменных целевой функции исходной задачи, выраженной через неосновные переменные ее оптимального решения. Данная теорема говорит о том, что на последнем шаге в последних симплексных таблицах прямой задачи I и двойственной задачи II коэффициенты последней строки одной таблицы соответствуют коэффициентам последнего столбца другой таблицы и, наоборот, коэффициенты последней строки второй таблицы соответствуют коэффициентам последнего столбца первой таблицы. Рассмотрим последние симплексные таблицы двух взаимнодвойственных задач линейного программирования, полученные в примерах 2 и 3 (таблицы 2.5 и 2.9). Таблица 3.2. Базис x1 x1 1 x5 x2 x6 F y Таблица Базис x2 x1 F0 Последняя симплексная таблица прямой задачи bi /aij x2 x3 x4 x5 x6 bi -1/5 3/5 6 -2/5 1/5 1 1 1 2/5 -1/5 4 3/5 1 3 -1 4 5 4/5 3/5 24 3.3. Последняя симплексная таблица двойственной задачи x1 x2 x3 x4 x5 x6 y1 y2 bi bi /aij 1 -1/5 1 4/5 -3/5 1/5 3/5 -1/5 3/5 1 2/5 -3/5 1/5 -2/5 -1/5 2/5 4/5 1 3 6 4 94 96 -24 Двойственность Стр. 47 из 136 JI JIxy y × y Оглавление 3.1 Экономическая интерпретация прямой и двойственной задач линейного программирования 3.1.2 y II JJ В базовой задаче на последнем шаге было получено оптимальное допустимое базисное решение X ∗ = (6; 4; 0; 0; 1; 3), 4 5 3 5 F = 24 − x3 − x4 , F (X ∗ ) = Fmax = 24. В двойственной задаче было получено допустимое базисное решение 4 3  Y∗ = ; ; 0; 0; 0; 0 , Z = 24+y3 +3y4 +6y5 +4y6 , Z(Y ∗ ) = 24. 5 5 Компоненты оптимального решения двойственной задачи y1∗ = 54 , y2∗ = 35 , y3∗ = 0, y4∗ = 0, y5∗ = 0, y6∗ = 0, равны (по абсолютной величине) коэффициентам при соответствующих переменных целевой функции прямой задачи, которую можно представить в виде 4 5 3 5 F = 24 − 0x1 − 0x2 − x3 − x4 − 0x5 − 0x6 . Верно и наоборот, компоненты оптимального решения прямой задачи x1∗ = 6, x2∗ = 4, x3∗ = 0, x4∗ = 0, x5∗ = 1, x6∗ = 3 равны (по абсолютной величине) коэффициентам при соответствующих переменных целевой функции двойственной задачи, которую можно представить (без учета функции штрафа и в первоначальной форме — на минимум) в виде y Z = 24 + 0y1 + 0y2 + 1y3 + 3y4 + 6y5 + 4x6 . Двойственность Стр. 48 из 136 JI JIxy y × y Оглавление 3.1 Экономическая интерпретация прямой и двойственной задач линейного программирования 3.1.2 y II JJ Замечание. Если в одной из взаимно двойственных задач нарушается единственность оптимального решения, то оптимальное решение двойственной задачи вырожденное (хотя бы одна базисная переменная обращается в нуль). Пусть xj∗ = a > 0 — базисная переменная и xk∗ = 0 — неосновная переменная в оптимальном решении X1∗ прямой задачи, а xj∗ = 0 — неосновная переменная и xk∗ = b > 0 — базисная переменная в другом оптимальном решении X2∗ прямой задачи. Пусть переменной xj∗ соответствует переменная yi∗ и xk∗ соответствует переменная yl∗ двойственной задачи. Тогда в случае единственности оптимума Y ∗ двойственной задачи по второй теореме двойственности из-за наличия оптимума X1∗ следует, что yi∗ = 0, а из-за наличия оптимума X2∗ следует, что yl∗ = 0 и одна из этих переменных должна быть базисной. Нарушение единственности оптимального решения исходной задачи наблюдается когда в выражении линейной (целевой) функции ее оптимального решения через неосновные переменные отсутствует хотя бы одна из неосновных переменных. y Двойственность Стр. 49 из 136 JI JIxy y × y Оглавление 3.2 Анализ моделей на чувствительность 3.2 Анализ моделей на чувствительность y II JJ Математическая модель позволяет получить оптимальные решения и ответить на разнообразные вопросы, касающиеся принятия оптимальных решений. Экономико-математический анализ решений осуществляется в двух основных направлениях: • при постановке задачи — вариантные расчеты по моделям с сопоставлением различных вариантов плана (параметрический, многокритериальный, структурный анализ); • после получения оптимального решения — анализ каждого из полученных решений в том числе, с помощью двойственных оценок (анализ решения, устойчивости решения, анализ пределов). y Двойственность Стр. 50 из 136 JI JIxy y × y Оглавление 3.2 Анализ моделей на чувствительность 3.2.1 y II JJ 3.2.1 Объективно обусловленные оценки и их смысл Компоненты оптимального решения двойственной задачи называются оптимальными (двойственными) оценками исходной задачи. Академик Л.В. Кантарович назвал их объективно обусловленными оценками. Экономический смысл этих оценок вытекает из второй теоремы двойственности — взаимосвязи компонент оптимальных решений прямой и двойственной к ней задачи линейного программирования (табл. 3.4). Таблица 3.4. Интерпретация двойственных оценок Компоненты оптимального решения исходной задачи I Число единиц продукции Остатки ресурсов, единиц P1 P2 S1 S2 S3 S4 x5∗ = 1 x6∗ = 3 x3∗ = 0 x4∗ = 0 x1∗ = 6 x2∗ = 4 l l l l l l y5∗ = 0 y6∗ = 0 y1∗ = 4/5 y2∗ = 3/5 y3∗ = 0 y4∗ = 0 Превышение затрат на ресурсы над ценой реализации (приведенная или нормированная стоимость) Объективно обусловленные оценки ресурсов (условные цены ресурсов или теневая цена) Компоненты оптимального решения двойственной задачи II Объективно обусловленные оценки ресурсов определяют степень дефицитности ресурсов: по оптимальному плану производства дефицитные (т. е. полностью используемые) ресурсы получают ненулевые оценки, а дефицитные — нулевые оценки. y Двойственность Стр. 51 из 136 JI JIxy y × y Оглавление 3.2 Анализ моделей на чувствительность 3.2.1 y II JJ Третья теорема двойственности. Компонентам оптимального решения двойственной задачи равны значениям частных производных линейной функции Fmax (b1 , . . . , bm ) по соответствующим аргументам, т. е. ∂Fmax = yi∗ , ∂bi i = 1, 2, . . . , m. (3.7) Доказательство этой теоремы установим на примере задачи об использовании ресурсов с помощью первой теоремы двойственности и геометрической интерпретации симплексного метода. По первой теореме двойственности Fmax = Zmin = b1 y1∗ + . . . + bi yi∗ + . . . + bm ym∗ . Небольшое изменении ∆yi запаса i-го ресурса меняет наклон линии уровня целевой функции двойственной задачи, но она по прежнему будет проходить через ту же угловую точку многогранника допустимых решений — базисное решение не измениться. Но в силу приращения ∆yi изменится слагаемое bi yi∗ на величину bi ∆yi∗ и на эту же величину изменится Zmin = Fmax . Поэтому ∆Fmax = yi∗ . ∆bi Объективно обусловленные оценки ресурсов (свободных членов в системе ограничений) показывают, на сколько денежных единиц изменится максимальная прибыль от реализации продукции (значение целевой функции) при изменении запаса соответствующего ресурса (свободного члена в системе ограничений) на единицу. y Двойственность Стр. 52 из 136 JI JIxy y × y Оглавление 3.2 Анализ моделей на чувствительность 3.2.2 3.2.2 Анализ устойчивости y II JJ Из доказательства третьей теоремы двойственности было получено, что при малом приращении ∆bi свободного члена bi в системе ограничения приводит к изменению целевой функции ∆Fmax = ∆bi ·yi∗ , где yi∗ — i-я компонента оптимального решения двойственной задачи. Малость приращения ∆bi означает, что в последней симплексной таблице также выполняется критерий оптимальности (для прямой задачи это отсутствие отрицательных коэффициентов в целевой функции при ее выражении в каноническом виде через неосновные переменные). Данное свойство может быть использовано для определения допустимых приращений ∆bi , в пределах которых сохраняются двойственные оценки. Пусть в прямой задаче I незначительно увеличились на ∆bi , i = 1, 2, . . . , m запасы ресурсов (свободные члены в системе ограничений) и оптимальный план в двойственной задаче II не изменился. Тогда если Y ∗ = (y1∗ , y2∗ , . . . , ym∗ ) оптимальное решение задачи II, то по третьей теореме двойственности Fmax = Zmin = (b1 + ∆b1 )y1∗ + . . . + (bm + ∆bm )ym∗ . (3.8) Подставим в эту формулу в выражения базисных переменных через неосновные переменные, полученные на последнем шаге симплексного метода. Сохранение оптимального решения задачи II означает, что в прямой задаче I выполняется критерий оптимальности: коэффициенты при переменных в выражении целевой функции (3.8) через неосновные переменные остаются неотрицательными. y Двойственность Стр. 53 из 136 JI JIxy y × y Оглавление 3.2 Анализ моделей на чувствительность 3.2.2 y II JJ Оказывается, что данные коэффициенты выражаются в виде линейной комбинации приращений ∆bi с коэффициентами, совпадающими с коэффициентами соответствующих столбцов последней симплексной таблицы прямой задачи I. Соответствие столбцов последней симплексной таблицы задачи I устанавливается с компонентами yi по второй теореме двойственности. Таким образом, симплексная таблица, полученная на последнем шаге симплексного метода, позволяет найти оптимальное решение прямой и двойственной задач, а также определить сохраненяются или нет объективно обусловленные оценки ресурсов (статус ресурсов) при заданном изменение запасов ресурсов (приращениях свободных членов в системе ограничений). y Двойственность Стр. 54 из 136 JI JIxy y × y Оглавление 3.2 Анализ моделей на чувствительность 3.2.2 y II JJ На практике обычно рассматривают пределы изменения свободных членов в системе ограничений (запасов ресурсов) отдельно по каждому уравнению. Таким образом для каждого ограничения определяется интервал изменения свободного члена (запасов ресурсов), в пределах которого сохраняется статус ограничения (значения объективно обусловленных оценок): дефицитные (т. е. полностью используемые ресурсы) остаются дефицитными, а недефицитные — недефицитными. В силу второй теоремы двойственности первоначальным — базисным переменным двойственной задачи II соответствуют дополнительные (неосновные) переменные задачи I с нулевыми значениями, а неосновным переменным двойственной задачи II соответствуют базисные (первоначальные) переменные задачи I и обычно и с ненулевыми значениями. Последняя симплексная таблица задачи I также позволяет найти пределы изменения запасов ресурсов по отдельным ресурсам. Например, для i-го ресурса необходимо рассчитать bi столбца свободных отрицательные оценочные отношения − ai,n+i членов bi к столбцу коэффициентов переменной xn+i . Тогда максимальное отношение среди отрицательных будет нижней границей ∆bi , а минимальное отношение среди положительных — верхней границей ∆bi изменения запаса bi ресурса i. y Двойственность Стр. 55 из 136 JI JIxy y × y Оглавление 3.2 Анализ моделей на чувствительность 3.2.2 y II JJ Малые изменения коэффициентов целевой функции не влияют на оптимальное решение прямой задачи I. Поэтому вызывает интерес определения пределов таких изменений. В силу взаимной двойственности задач линейного программирования коэффициентам целевой функции одной задачи соответствуют свободные члены в системе ограничений двойственной задачи. Поэтому пределы изменения коэффициентов целевой функции, сохраняющие оптимальное решение прямой задачи, — это пределы изменения свободных членов в системе ограничения двойственной задачи, сохраняющие двойственные оценки. Таким образом, результаты анализа устойчивости показывают пределы изменения отдельных входных параметров модели (в частности, коэффициенты целевой функции и / или свободные члены в системе ограничений), в пределах которых остаются неизменными соответствующие выходные параметры модели (соответственно, сохраняется первоначальный оптимальный план и / или объективно обусловленные оценки — теневые цены — свободных членов в системе ограничений). Результаты анализа чувствительности показывают на сколько будут изменяться выходные параметры модели (например, значение целевой функции) при изменении входных параметров модели (например, при изменении свободного члена в системе ограничений), в частности, при единичных изменениях. y Двойственность Стр. 56 из 136 JI JIxy y × y Оглавление 3.3 Анализ дополнительно закупаемых ресурсов 3.3 Анализ дополнительно закупаемых ресурсов y II JJ Пусть имеется задача об использовании ресурсов. Требуется составить план производства, обеспечивающий максимальную прибыль, но при этом имеется свободные финансовые средства в фиксированном объеме для приобретения дополнительных ресурсов по их известным ценам. Решение задачи может осуществляться по двум направлениям: Первое направление. Сначала ищется оптимальное решение без учета дополнительных ресурсов и из анализа устойчивости определяется наиболее дефицитный ресурс. Далее дополнительно приобретается дефицитный ресурс в объеме устойчивости и ищется новый оптимальный план использования ресурсов устойчивость этого плана. Далее процедура повторяется до тех пор, пока не будут использованы все финансовые средства. Второе направление. Строится модифицированная модель задачи, в которую включаются новые переменные — план закупок дополнительных ресурсов с учетом дополнительного ограничения на объем используемых финансовых ресурсов. y Двойственность Стр. 57 из 136 JI JIxy y × y y y y Оглавление 3.3 Анализ дополнительно закупаемых ресурсов II JJ Пример 3.1. Для изготовления четырех видов продукции на предприятии используют три вида ресурсов. Известны нормы расхода ресурсов при производстве продукции (сколько необходимо каждого ресурса для производства единицы каждого продукта): для изготовления одной единицы первого продукта необходимо 1,5 ед. первого ресурса, 4,5 ед. второго ресурса и 3 ед. третьего ресурса; для изготовления одной единицы второго продукта необходимо 4,5 ед. первого ресурса, 1,5 ед. второго ресурса и 3 ед. третьего ресурса, для изготовления одной единицы третьего продукта используется 3 ед. первого ресурса, 1,5 ед. — второго ресурса и 4,5 ед. — третьего ресурса; для изготовления одной единицы четвертого продукта используется три ед. первого ресурса, 6 ед. второго ресурса и 1,5 ед. третьего ресурса. В наличии имеется 90 ед. первого ресурса, 60 ед. второго и 120 единиц третьего ресурса. Стоимость ресурсов составляет 12, 10 и 9 ден. ед. за единицу соответствующего ресурса. Продукция реализуется по ценам 105, 126, 114 и 132 ден. ед. за единицу продукции соответственно. В распоряжении предприятия имеется финансовые ресурсы в объеме 2 000 ден. ед. на приобретение дополнительных ресурсов. Требуется составить оптимальный план производства, т. е. план, при котором прибыль от производства и реализации будет максимальной, если предполагается осуществить следующие варианты реализации плана: Вариант 1: финансовые ресурсы не использовать; Вариант 2: поэтапно осуществлять закупку дополнительных ресурсов, на основе анализа устойчивости предыдущего оптимального плана; Вариант 3: однократно осуществить закупку дополнительных ресурсов на основе вариантной оптимизационной модели. Двойственность Стр. 58 из 136 JI JIxy × y Оглавление 3.3 Анализ дополнительно закупаемых ресурсов y II JJ Решение. Вариант 1. Пусть x1 , x2 , x3 , x4 — план производства первого, второго, третьего и четвертого продуктов соответственно. С учетом условия задачи для реализации этого плана понадобится: ресурса 1 — 1.5x1 + 4.5x2 + 3.0x3 + 3.0x4 ед.; ресурса 2 — 4.5x1 + 1.5x2 + 1.5x3 + 6.0x4 ед.; ресурса 3 — 3.0x1 + 3.0x2 + 4.5x3 + 1.5x4 ед. По условию финансовые ресурсы не используются, поэтому получаем следующую систему ограничений на объем использования материальных ресурсов:   1.5x1 + 4.5x2 + 3.0x3 + 3.0x4 6 90, 4.5x + 1.5x + 1.5x + 6.0x 6 60,  3.0x1 + 3.0x2 + 4.5x3 + 1.5x4 6 120. 1 2 3 4 Целевая функция вычисляет прибыль F (x1 , x2 , x3 , x4 ) при выполнении плана X = (x1 , x2 , x3 , x4 ). Поэтому прибыль найдем как разность между выручкой от реализации и затратами производства (использования ресурсов): F = 105x1 + 126x2 + 114x3 + 132x4 − − (1.5x1 + 4.5x2 + 3.0x3 + 3.0x4 ) · 12 − − (4.5x1 + 1.5x2 + 1.5x3 + 6.0x4 ) · 10 − − (3.0x1 + 3.0x2 + 4.5x3 + 1.5x4 ) · 9 → max . После преобразования получим: y F = 15x1 + 30x2 + 22.5x3 + 22.5x4 → max . Двойственность Стр. 59 из 136 JI JIxy y × y Оглавление 3.3 Анализ дополнительно закупаемых ресурсов Экономико-математическая модель задачи имеет вид: F =15x1 + 30x2 + 22.5x3 + 22.5x4 → max  1.5x1 + 4.5x2 + 3.0x3 + 3.0x4 6 90, 4.5x1 + 1.5x2 + 1.5x3 + 6.0x4 6 60, 3.0x + 3.0x + 4.5x + 1.5x 6 120; 1 2 3 4 x1 , x2 , x3 , x4 > 0. y II JJ Реализация модели с помощью «Происка решения» MS Excel дает следующие результаты: X ∗ = (5, 5, 20, 0), F (X ∗ ) = 675, т. е. необходимо производить по 5 единиц первого и второго продукта, 20 единиц третьего и не производить четвертый продукт. «Отчет по результатам» показывает, что при реализации этого плана все ресурсы будут использоваться полностью. «Отчет по устойчивости» показывает, что ресурсы имеют следующие теневые цены (объективно-обусловленные оценки): 5.833 — первый ресурс; 0.833 — второй и третий ресурсы. Данные оценки являются устойчивыми, если запасы ресурсов будут увеличиваться не более 90 ед. первого ресурса, 90 ед. второго ресурса и 18 ед. третьего ресурса. y Двойственность Стр. 60 из 136 JI JIxy y × y Оглавление 3.3 Анализ дополнительно закупаемых ресурсов y II JJ Вариант 2. Из варианта 1 получаем, что увеличение запасов ресурса 1 дает бо́льший прирост прибыли, но ресурсы имеют разную стоимость, поэтому вложение 1 ден. ед. в приобретение ресурса 1 дает дополнительную прибыль в размере 5.833/12 = 0.486 ден. ед., а вложение в ресурс 2 — 0.833/10 = 0.083 ден. ед., а ресурс 3 — 0.833/9 = 0.093. Таким образом, выгоднее приобретать ресурс 1 в объеме интервала устойчивости, т. е. 90 ед. или на сумму 90 · 12 = 1080 ден. ед. Таким образом, на первом этапе закупаем 90 ед. первого ресурса, т. е. на сумму 1080 ден. ед. и оптимальный план производства описывается моделью F =15x1 + 30x2 + 22.5x3 + 22.5x4 → max  1.5x1 + 4.5x2 + 3.0x3 + 3.0x4 6 180, 4.5x1 + 1.5x2 + 1.5x3 + 6.0x4 6 60, 3.0x + 3.0x + 4.5x + 1.5x 6 120; 1 2 3 4 x1 , x2 , x3 , x4 > 0. Реализация модели с помощью «Происка решения» MS Excel дает следующие результаты: X1∗ = (0, 40, 0, 0), F (X ∗ ) = 1200, т. е. необходимо производить только второй продукт в количестве 40 единиц и при этом все ресурсы будут использоваться полностью. «Отчет по устойчивости» показывает, что ресурсы имеют следующие теневые цены (объективно-обусловленные оценки): 5.833 — первый ресурс; 0.833 — второй и третий ресурсы. Данные оценки являются устойчивыми, если запасы ресурсов будут увеличиваться не более 0 ед. для каждого ресурса. y Двойственность Стр. 61 из 136 JI JIxy y × y Оглавление 3.3 Анализ дополнительно закупаемых ресурсов На следующем (втором) этапе в распоряжении остается 2000 − 1080 = 920 (ден. ед.). y II JJ Так как в плане X1 нет допустимых увеличений запасов ни каких ресурсов, то это означает, что нужно увеличивать запасы сразу нескольких ресурсов. Поэтому на втором этапе закупим дополнительно каждого ресурса в объеме 20 единиц. Для этого понадобится 20 · 12 + 20 · 10 + 20 · 9 = 620 ден. ед., т. е. еще останется 300 ден. ед. Оптимальный план производства описывается моделью F =15x1 + 30x2 + 22.5x3 + 22.5x4 → max  1.5x1 + 4.5x2 + 3.0x3 + 3.0x4 6 200, 4.5x1 + 1.5x2 + 1.5x3 + 6.0x4 6 80, 3.0x + 3.0x + 4.5x + 1.5x 6 140; 1 2 3 4 x1 , x2 , x3 , x4 > 0. Реализация модели с помощью «Происка решения» MS Excel дает следующие результаты: X2∗ = (3.33, 43.33, 0, 0), F (X2∗ ) = 1350, т. е. необходимо производить первый продукт в объеме 3.33 ед. и второй продукт в количестве 43.33 ед., а остальные — не производить, и при этом все ресурсы будут использоваться полностью. «Отчет по устойчивости» показывает, что ресурсы имеют следующие теневые цены (объективно-обусловленные оценки): 5.833 — первый ресурс; 0.833 — второй и третий ресурсы. Данные оценки являются устойчивыми, если запасы первого и второго ресурсов будут увеличиваться не более 0 ед., а запасы третьего ресурса будут увеличиваться не более 60 ед. y Двойственность Стр. 62 из 136 JI JIxy y × y Оглавление 3.3 Анализ дополнительно закупаемых ресурсов y II JJ С учетом предыдущего шага на третьем этапе будем закупать третий ресурс на всю оставшуюся сумму, т. е. 300/9 = 33.33 ед. — это находится в пределах устойчивости решения задачи на предыдущем шаге. Оптимальный план производства описывается моделью F =15x1 + 30x2 + 22.5x3 + 22.5x4 → max  1.5x1 + 4.5x2 + 3.0x3 + 3.0x4 6 200, 4.5x1 + 1.5x2 + 1.5x3 + 6.0x4 6 140, 4.5x + 1.5x + 1.5x + 6.0x 6 113.33; 1 2 3 4 x1 , x2 , x3 , x4 > 0. Реализация модели с помощью «Происка решения» MS Excel дает следующие результаты: X3∗ = (1.48, 34.07, 14.81, 0), F (X2∗ ) = 1377.78, т. е. необходимо производить первый продукт в объеме 1.48 ед. и второй продукт в количестве 34.07 ед., третьего 14.81, а четвертый — не производить, и при этом необходимо закупить первого ресурса 110 ед., второго — 20 ед., третьего — 53.33. При этом все ресурсы будут использоваться полностью, а прибыль составит 1377.78 ден. ед. y Двойственность Стр. 63 из 136 JI JIxy y × y Оглавление 3.3 Анализ дополнительно закупаемых ресурсов y II JJ Вариант 3. Пусть x1 , x2 , x3 , x4 — план производства первого, второго, третьего и четвертого продуктов соответственно, а y1 , y2 , y3 — объемы закупок дополнительных ресурсов соответственно. Тогда ограничение на объем покупок дополнительных ресурсов составит: 12y1 + 10y2 + 9y3 6 2000. Ограничение на объем используемого первого ресурса соответственно составит: 1.5x1 + 4.5x2 + 3.0x3 + 3.0x4 6 90 + y1 , второго ресурса — 4.5x1 + 1.5x2 + 1.5x3 + 6.0x4 6 60 + y2 , третьего ресурса — 3.0x1 + 3.0x2 + 4.5x3 + 1.5x4 6 60 + y2 . Прибыль можно вычислить как разность между планируемой выручкой и планируемыми затратами на все ресурсы (включая и дополнительно приобретенные): π = 105x1 + 126x2 + 114x3 + 132x4 − − (1.5x1 + 4.5x2 + 3.0x3 + 3.0x4 ) · 12 − − (4.5x1 + 1.5x2 + 1.5x3 + 6.0x4 ) · 10 − − (3.0x1 + 3.0x2 + 4.5x3 + 1.5x4 ) · 9 → max . y После преобразования получим: π = 15x1 + 30x2 + 22.5x3 + 22.5x4 → max . Двойственность Стр. 64 из 136 JI JIxy y × y Оглавление 3.3 Анализ дополнительно закупаемых ресурсов y II JJ Реализация модели с помощью «Происка решения» MS Excel дает следующие результаты: X ∗ = (0.00, 0.00, 49.58, 0.00), F (X ∗ ) = 1487.50, т. е. необходимо производить только третий продукт в количестве 49.58 ед. и при этом необходимо закупить первого ресурса 133.13 ед., второго — 14.37 ед., третьего — 28.75. При этом все ресурсы будут использоваться полностью, а прибыль составит 1487.50 ден. ед. Полученный результат оказался лучше результата в варианте 2. Это объясняется тем, что в варианте 2 на этапе 2 были закуплены дополнительно все ресурсы в одинаковом объеме — 20 ед. Но как показывает реализация вариантной модели, этот выбор оказался не самым оптимальным. Таким образом, наиболее эффективное использование финансовых средств на покупку дополнительных материальных ресурсов дает оптимизационная модель, представленная в варианте 3. y Двойственность Стр. 65 из 136 JI JIxy y × y Оглавление 3.4 Отчеты «Поиска решения» Excel 3.4 Отчеты «Поиска решения» Excel y II JJ На основании отчетов поиска решения задачи линейного программирования можно получить решение двойственной задачи и другие результаты. Для этого при появлении окна «Результаты поиска решения» нужно выделить соответствующий отчет (щелкнуть левой кнопкой мыши по нужному типу отчета): «Результаты», «Устойчивость», «Пределы». Отчеты выводятся на других листах файла. Их можно просмотреть, нажав на соответствующую вкладку нижней части таблицы Excel. Для более удобного чтения отчетов полезно вводить коэффициенты модели вместе с их названиями, располагающимися в соседних ячейках. Данная информация автоматически включается в отчеты. y Двойственность Стр. 66 из 136 JI JIxy y × y y y y Оглавление 3.4 Отчеты «Поиска решения» Excel II JJ Приведем интерпретацию отчетов на примере задачи об использовании ресурсов. В отчете «Результаты» выводятся основные результаты вычислений. В таблицах «Целевая функция» и «Изменяемые ячейки» приводятся начальные и оптимальные значения целевой функции и изменяемых ячеек. В таблице «Ограничения» статус связанное говорит, что при оптимальном плане в системе ограничений соответствующее неравенство обращается в равенство, а несвязанное — в строгое неравенство (в задаче об использовании ресурсов это указывает на дефицитность или недефицитность ресурсов). Статус разница показывает оптимальное значение дополнительных переменных (в задаче об использовании ресурсов это остатки ресурсов после их оптимального использования). Двойственность Стр. 67 из 136 JI JIxy × y y y y Оглавление 3.4 Отчеты «Поиска решения» Excel II JJ В отчете «Устойчивость» выводятся дополнительные показатели, характеризующие устойчивость полученного решения. В таблице «Изменяемые ячейки» Нормированная (приведенная) стоимость — значения дополнительных двойственных переменных. Эти переменные показывают на сколько изменится целевая функция (прибыль) при принудительном выпуске единицы соответствующей продукции (включении дополнительной единицы продукции в оптимальный план производства). Допустимое увеличение показывает на сколько максимально можно увеличить коэффициент целевой функции, чтобы оптимальный план не изменился. Допустимое уменьшение — наоборот1 . В таблице «Ограничения» теневая цена — значение двойственной переменной, или объективно обусловленная оценка соответствующего ресурса (ограничения), показывает на сколько изменится целевая функция при увеличении запаса ресурса (свободного члена в системе ограничений) на единицу. Допустимое увеличение и уменьшение показывают границы, в которых могут изменяться запасы данного ресурса (изменение свободного члена в системе ограничений) при сохранении статуса ресурса (дефицитный ресурс будет оставаться дефицитным). В отчете «Пределы» указываются пределы изменения объема выпуска каждого вида продукции и какой вклад они вносят в значение целевой функции. 1 По отчету об устойчивости в примере 4 первый коэффициент при целевой функции может быть максимально увеличен на 4 и минимально уменьшен на 1. Таким образом, при изменении первого коэффициента в пределах от 1 до 6 (включая граничные значения) целевая функция будет принимать максимальное значение при x1 = 6 и x2 = 4 (граничные значения 1 и 6 первого коэффициента целевой функции будут соответствовать нескольким оптимальным планам). Двойственность Стр. 68 из 136 JI JIxy × y Оглавление В.М. Караулов Глава 4 Модели сетевого планирования и управления y II JJ Методы сетевого планирования и управления основаны на моделировании процесса с помощью сетевого графика и представляет собой совокупность расчетных методов, организационных и контрольных мероприятий по планированию и управлением комплексом работ. y Модели СПУ Стр. 69 из 136 JI JIxy y × y Оглавление 4.1 Сетевая модель и ее основные элементы 4.1 y II JJ Сетевая модель и ее основные элементы Сетевая модель — это план выполнения некоторого комплекса взаимосвязанных работ (операций), заданного в форме сети, графическое изображение которой называется сетевым графиком. Отличительная особенность сетевой модели — четкое определение всех временных взаимосвязей предстоящих работ. Главные элементы сетевой модели — события и работы. Термин «работы» используется в широком смысле: • во-первых это действительная работа — протяженный во времени процесс, требующий затрат ресурсов (временных, материальных или денежных); • во-вторых, это ожидание — протяженный во времени процесс, не требующий затрат труда (например, сушка после покраски); • в-третьих, это зависимость, или фиктивная работа — логическая связь между двумя или несколькими работами, не требующая затрат труда, материальных ресурсов или времени. Она указывает, что возможность одной работы непосредственно зависит от другой работы. Продолжительность фиктивной работы принимается равной нулю. y Модели СПУ Стр. 70 из 136 JI JIxy y × y y y y Оглавление 4.1 Сетевая модель и ее основные элементы II JJ Событие — это момент завершения какого-либо процесса, определяющий отдельный этап выполнения проекта. Событие может быть результатом отдельной работы или суммарным результатом нескольких работ. Событие может свершиться только тогда, когда закончатся все работы, ему предшествующие. Последующие работы могут начаться только тогда, когда событие свершится. Отсюда вытекает двойственный характер события: для всех непосредственно предшествующих ему работ оно является конечным, а для всех непосредственно следующих за ним — начальным. Предполагается, что событие не имеет продолжительности и свершается мгновенно. Поэтому каждое событие, включаемое в сетевую модель, должно быть полностью определено. Среди событий сетевой модели выделяют исходное и завершающее события. Исходное событие (исток) не имеет предшествующих работ и событий. Завершающее событие не имеет последующих работ и событий. Графическое изображение сетевой модели представляется в виде таблицы или графа. Например, события можно изображать вершинами графа — кружками, а работы — стрелками — ориентированными ребрами, или дугами, графа. Таким образом получаем сетевую модель — ориентированный граф «событияработы». Возможно альтернативное изображение сетевой модели в виде графа «работы-связи» (структурной модели), в котором вершинами изображаются работы, а ориентированными ребрами — связи между работами. Например, входящие стрелки показывают какие работы непосредственно предшествуют данной работе, а исходящие стрелки показывают какие работы непосредственно следуют после этой. Кроме того на сетевом графике отражают дополнительную информацию о комплексе работ. В частности, обычно на каждой работе-ребре указывают продолжительность работы, а также другую информацию. Модели СПУ Стр. 71 из 136 JI JIxy × y Оглавление 4.2 Построение сетевых графиков 4.2 Построение сетевых графиков y II JJ Сетевые графики составляются на начальном этапе планирования: 1. Процесс разбивается на отдельные работы, события, логические связи между ними и последовательностью выполнения. 2. За работами закрепляются ответственные исполнители. 3. С помощью ответственных оценивается длительность выполнения работ. 4. Затем составляется сетевой график. 5. События и работы упорядочиваются. 6. Потом вычисляются параметры событий и работ, определяются критический путь и резервы времени. 7. На заключительном этапе проводится анализ сетевого графика, его оптимизация и, при необходимости, строится новый график с пересчетом параметров событий и работ. y Модели СПУ Стр. 72 из 136 JI JIxy y × y Оглавление 4.2 Построение сетевых графиков 4.2.1 Правила построения сетевых графиков 4.2.1 y II JJ Сетевой график должен удовлетворять ряду свойств: 1. В сетевой модели не должно быть «тупиковых» событий, из которых не выходит ни одной работы, за исключением завершающего события. 2. В сетевой модели не должно быть «хвостовых» событий, кроме исходного, которым не предшествует хотя бы одна работа. 3. В сети не должно быть замкнутых контуров (иначе последующие работы окажутся также предшествующими) и петель (у работы начало и конец не могут совпадать). 4. Любые два события должны быть непосредственно связаны не более чем одной работой-стрелкой. 5. В сети рекомендуется иметь одно исходное и одно завершающее событие. Для корректировки сетевого графика можно вводить фиктивные события и фиктивные работы. Фиктивные работы — это работы, имеющие нулевую продолжительность. y Модели СПУ Стр. 73 из 136 JI JIxy y × y Оглавление 4.2 Построение сетевых графиков 4.2.2 4.2.2 Упорядочение сетевого графика y II JJ Для упорядочения сетевого графика все его вершины нумеруют. Начальному событию присваивают нулевое значение, а а завершающему — последний номер, кроме того, для каждой работы непосредственно предшествующее этой работе событие обозначают меньшим номером по сравнению с непосредственно последующему этой работе событию, т. е. стрелка-работа должна идти от меньшего номера к бо́льшему. Если нумерация вершин графика не удовлетворяет этим условиям, то их перенумеровывают. В целом, упорядочение сетевого графика заключается в таком расположении событий и работ, при котором для любой работы предшествующие ей событие расположено левее и имеет меньший номер по сравнению с завершающим эту работу событием. Это означает, что в упорядоченном графике все стрелкиработы направлены слева направо. y Модели СПУ Стр. 74 из 136 JI JIxy y × y Оглавление 4.2 Построение сетевых графиков 4.2.2 y II JJ Пример 4.1. Имеется данные о комплексе работ и времени их выполнения (табл. 4.1). Требуется построить сетевую модель и упорядочить ее. Таблица 4.1. Структурная таблица комплекса работ Процесс (работа) b1 b2 b3 b4 b5 b6 b7 b8 b9 b10 Предшествующий процесс b1 , b2 b5 b6 b4 b7 , b8 b3 , b9 Длительность процесса 3 2 4 3 2 4 2 1 2 4 Решение. Произведем упорядочение работ по рангам. В результате получим упорядоченную структурно-временную таблицу 4.2. Теперь можно представить упорядочение комплекса работ с точки зрения событий (табл. 4.3). Структурная модель в виде графа представлена на рис. 4.1, где через вершины графа обозначены работы, а через ребра — связи между работами. Представим модель в виде сетевого графика «событияработы» с начальным событием вершине 1 и завершающим событием в вершине 9. Для выполнения требований, предъявляемых к сетевым графикам, добавим фиктивную работу (2, 3), обозначив её на сетевом графике пунктирной стрелкой (рис. 4.2). В частности, фиктивная работа (2, 3) введена, чтобы «развести» параллельные процессы a1 и a2 . y Модели СПУ Стр. 75 из 136 JI JIxy y × y Оглавление 4.2 Построение сетевых графиков 4.2.2 Таблица 4.2. Упорядочение работ по рангам Процесс (работа) b1 b2 b3 b4 b5 b6 b7 b8 b9 b10 Предшествующий процесс b1 , b2 b5 b6 b4 b7 , b8 b3 , b9 a1 Длительность процесса 3 2 4 3 2 4 2 1 2 4 Ранг 1 1 1 1 2 3 4 2 5 6 a7 a5 Новая нумерация a2 a1 a4 a3 a5 a7 a8 a6 a9 a10 y II JJ a8 a2 a1 a8 a6 a7 a5 a a9 a23 a6 aa34 a4 a10 a10 Рис. 4.1. Структурная сеть a5 = 2 3 2 a5 = 2 3 2 y a9 a1 = 2 a1 = 2 a2 = 3 a2 = 3 4 a3 = 3 4 a3 = 3 a4 = 4a4 11 Модели СПУa = 2 5 5 a7 = 4 a6 = 1 a7 = 4 6 a8 = 2 6 a6 = 1 a 8 = 2 7 7 a9 = 2 a9 = 2 =4 8 a10 = 4 89 Рис. 4.2. Сетевой график 2 3 2 a5 = 2 a7 = 4 a5 5= 2 a7 =6 4 3 Стр. 76 из 5136 J I a J = 2 I6 xy y a10 = 4 × y Оглавление 4.2 Построение сетевых графиков 4.2.2 y II JJ Таблица 4.3. Упорядочение событий и работ по рангам Событие Процесс (работа) 2 3 4 5 6 7 8 9 10 11 a1 a2 a3 a4 a5 a6 a7 a8 a9 a10 y Модели СПУ Предшествующая работа a1 , a2 a4 a5 a7 a6 , a8 a4 , a9 Стр. 77 из 136 Время, ti 2 3 3 4 2 1 4 2 2 4 JI JIxy y × y Оглавление 4.2 Построение сетевых графиков a1 a7 a5 4.2.2 a8 a2 y II JJ a6 a9 Временной сетевой график. Дополнительное упорядочение комплекса работ предполагает изображение времени на сетевом графике. График ориентируется вдоль a10 оси времени OT . a4 На нем в некотором масштабе откладываются времена выполнения работ. Таким образом, стрелкой изображают работу так, чтобы ее проекция OT была равна времени выa5 = на 2 ось абсцисс a7 = 4 3 работы. 5 6 2 полнения этой a8 = 2 При построении временного сетевого графика расположение a2 = 3 a1 = 2 a6 = 1 вершин (узлов) по 4вертикали (по оси 7ординат) берется произ3 a9 = 2времени окончания вольным,a3 =абсцисса же каждого узла равна a4 = 4 a10 = 4 считается от соответствующей работы. Длина каждой стрелки 1 8 9 центра до центра кружка. Временной сетевой график для комплекса работ, заданного в табл. 4.1, показан на рис. 4.3. a3 2 a1 = 2 3 a5 = 2 5 6 a8 = 2 a2 = 3 a6 = 1 4 7 a9 = 2 a3 = 3 a4 = 4 1 a7 = 4 3 8 5 9 11 13 a10 = 4 9 17 T Рис. 4.3. Временной сетевой график y Модели СПУ Стр. 78 из 136 JI JIxy y × y Оглавление 4.2 Построение сетевых графиков 4.2.2 y II JJ Построение временного сетевого графика (рис. 4.3) начинается с вершины 1, помещенной в начале координат. Из этого узла исходят четыре стрелки: a1 , a2 , a3 и a4 , проекции которых на ось OT отражают период времени выполнения соответствующих работ: t1 = 2, t2 = 3, t3 = 3 и t4 = 3. Проекции стрелок на ось времени могут иметь большую длину чем продолжительность выполнения соответствующих работ. Это означает, для таких работ имеются резервы времени на их выполнение. Работа a5 начинается когда завершаются работы a1 и a2 . Это событие 3. Значит, работа a5 может начаться не раньше, чем в момент t = max{2; 3} = 3, когда окончена a2 . Продолжительность работы a5 равна t5 = 2, поэтому она завершается в момент времени t = 3 + 2 = 5 (это событие 5) и т. д. Событие 7 — начало работы a9 и завершение работ a8 и a6 . Но перед работой a6 должна быть выполнена работа a3 , а перед работой a8 должны быть выполнены работы a7 , a5 , a2 . Поэтому работа a9 начнется в период не ранее чем максимум чисел t3 + t6 = 3 + 1 = 4 и t2 + t5 + t7 + t8 = 3 + 2 + 4 + 2 = 11. Значит, событие 7 — окончание работ a6 , a8 и начало работы a9 свершится не ранее, чем в период t = max{4; 11} = 11. Аналогичным образом получаем, что работа a10 (изображаемая стрелкой) начинается в вершине 8 и это событие происходит не ранее чем в период t = max{4; 11 + 2} = 13. Работа a10 завершается последней и выполняется в течение периода t10 = 4. Вершина 9 означает окончание всего комплекса работ и на рисунке этот факт отмечен узел жирным кружком. Таким образом, временной сетевой график комплекса работ построен. y Модели СПУ Стр. 79 из 136 JI JIxy y × y Оглавление 4.2 Построение сетевых графиков 4.2.3 4.2.3 Критический путь y II JJ Одно из важнейших понятий сетевого — понятие пути. Путь — любая последовательность работ, в которой конечное событие каждой работы совпадает с начальным событием следующей за этой работы. Наибольший интерес представляют полные пути. Путь называется полным, если он соединяет исходное (начальное) событие сети с завершающим событием. Длиной пути (или продолжительностью пути) называется продолжительность выполнения всех работ на этом пути. Наиболее продолжительный полный путь в сетевом графике называется критическим. Работы и события, лежащие на критическом пути, также называются критическими. На критическом пути должны быть выполнены все работы, поэтому весь комплекс работ, изображенных на сетевом графике, не может быть выполнен ранее чем все работы, лежащие на критическом пути. Поэтому критические работы и события должны быть выполнены в срок, иначе будут сорваны сроки выполнения всего проекта работ. Эти события и работы самые напряженные по по срокам выполнения, они не имеют резервов времени. Остальные события и работы являются некритическими — они имеют резервы времени. Метод критического пути позволяет определить для таких событий и работ резервы времени (напряженность их выполнения). Для проекта работ, представленных в табл. 4.1 и на временном сетевом графике 4.3, критический путь, изображенный жирными стрелками, содержит работы a1 , a5 , a6 , a7 , a9 и a10 , поэтому y tкр = t1 + t5 + t6 + t7 + t9 + t10 = 3 + 2 + 4 + 2 + 2 + 4 = 17. Модели СПУ Стр. 80 из 136 JI JIxy y × y Оглавление 4.2 Построение сетевых графиков 4.2.3 y II JJ Линейная диаграмма проекта. Временной сетевой график позволяет определить критические пути проекта. Для счет их «безвредного» замедления перебросить часть сил и средств на ренебольшого проекта после упорядочения сетевого графика комендуется дополнить линейной проекта. В нем более важные, критические работы. Длядиаграммой сокращения продолжительности все работы параллельным оси продолжительность времени отрезком, проекта изображаются необходимо в первую очередь сокращать длинаработ, которого равна продолжительности этой работы. При належащих на критическом пути. личии фиктивной работы нулевой продолжительности Заметим, что на сетевом графике вообще может быть неона одинизображается точкой. События i и j, начало и конец работы (i, j) критический путь, а два или более; естественно, сумма времен помещают соответственно в начале и конце отрезка. Отрезки критических работ на каждом из них должна быть одна и та же. располагают один над другим, снизу вверх в порядке возрастаСледует отметить, что классический вид сетевого графика — это ния индекса i, а при одном и том же i — в порядке возрастания сеть,j.вычерченная без масштаба времени. Поэтому сетевой график, хотя и индекса дает четкоедиаграмма представлениепроекта о порядке следования работ, но недостаточно Линейная позволяет определить работы, нагляден для определения тех работ, которые должны в которые должны выполняться в каждый данныйвыполняться момент времени, критические также Врезервы времени некритичекаждый данныйпути, моментавремени. связи с этим небольшойдля проект после ских событий и работ. упорядочения сетевого графика рекомендуется дополнить линейной Линейная длялинейная проекта работдля табл. 4.1 и времендиаграммойдиаграмма проекта. Такая диаграмма рассматриваемой ного сетевого графика на рис. 4.3 представлена на рис. 4.4. сети показана на рис. 1.105. y Модели СПУ Рис. 1.105 Рис. 4.4. Линейная диаграмма проекта 212 Стр. 81 из 136 JI JIxy y × y Оглавление 4.3 Временные параметры сетевых графиков 4.3 Временные параметры сетевых графиков y II JJ Достаточно прости резервы, соответствующие некритическим работам, могут быть определены по сетевому графику. Назовем «некритической дугой» совокупность некритических работ и событий, начинающуюся и кончающуюся на критическом пути. Каждой некритической дуге соответствует определенный временной резерв, который может быть произвольным образом распределен между некритическими события и работами, лежащими на данной дуге. Этот резерв равен разности между суммой времен критических работ, лежащих на критическом пути, замыкающем дугу, и некритических, лежащих на самой дуге. Две работы, лежащие на некритической дуге, имеют, очевидно, одинаковые резервы. Но при этом нужно учитывать, что если на одной из этих работ будет реализован резерв времени в полном объеме, то для другой работы резерва времени уже не останется. Поэтому выделяют различные виды резервов. Более того, резервы времени, в первую очередь, определяют для событий. Тогда резервы работы могут быть определены через резервы событий, которые определяют эту работу. y Модели СПУ Стр. 82 из 136 JI JIxy y × y Оглавление 4.3 Временные параметры сетевых графиков y II JJ Временные параметры событий. Для события i рассматривают: tр (i) — ранний срок свершения события i; tп (i) — поздний срок свершения события i; R(i) — резерв времени события i. Событие i не может наступить ранее чем будут выполнены все работы на максимальном по продолжительности пути, соединяющего исходное (0) событие с событием i. Поэтому ранний срок наступления события i определяется по формуле: tр (i) = max t(Lпi ), Lпi где Lпi — любой путь, предшествующий i-му событию, т. е. путь от исходного до i-го события. Вычисление временных параметров обычно удобнее вычислять на основе рекуррентных соотношений. Если событие j имеет несколько предшествующих путей (несколько предшествующих событий i), то ранний срок свершения события j можно найти по формуле: tр (i) = max[tр (i) + t(i, j)]. i Поздний срок свершения события i не должен препятствовать выполнению всех работ на на максимальном по продолжительности пути, идущем от события i до завершающего события всего комплекса работ. Поэтому поздний срок свершения события i вычисляется по формуле: y tп (i) = tкр − max t(Lсi ), Lсi y где Lсi — любой путь, следующим за i-м событием, т. е. путь от i-го события до завершающего события сети. Модели СПУ Стр. 83 из 136 JI JIxy × y Оглавление 4.3 Временные параметры сетевых графиков y II JJ Посмотрим на поздний срок свершения события i с другой стороны. Представим себе, что данный проект работ реализуется в обратном хронологическом порядке (время идет в обратную сторону): события обозначаются теми же номерами, но сначала реализуется завершающее (последнее) событие, потом — предпоследнее, а исходное событие реализуется в последнюю очередь. Обозначим через tр0 (i) раннее начало события i обратного процесса. Тогда: tр0 (i) = max t(Lсi ), Lсi где Lсi — любой путь, следующим за i-м событием, т. е. путь от i-го события до завершающего события сети. Таким образом, tп (i) = tкр − tр0 (i), то есть позднему сроку свершения события i соответствует ранний срок свершение этого события рассматриваемого в обратном хронологическом порядке. Пусть событие i имеет несколько последующих путей (последующих событий j в обычном хронологическом порядке, то поздний срок свершения события i можно найти по рекуррентной формуле: tп (i) = min[tп (j) − t(i, j)]. j Резерв времени R(i) i-го события определяется как разность между поздним и ранним сроком его свершения: y R(i) = tп (i) − tр (i). y Данный резерв показывает максимальный период времени, на который может задержаться свершение данного события без срывов сроков завершения всего проекта. Модели СПУ Стр. 84 из 136 JI JIxy × y Оглавление 4.3 Временные параметры сетевых графиков y II JJ Временные параметры работ. Работа (i, j) определяется двумя событиями i и j. Каждое из этих событий имеет два временных параметра: ранний и поздний срок свершения. Поэтому у работы (i, j) можно определить 4 вида временных параметров — резервов времени работы (i, j). Таким образом, различные резервы работы (i, j) определяются за счет резервов событий i и j. С другой стороны, резерв данного события i может включать в резервы непосредственно предшествующей этому событию работе, а также работе, непосредственно следующей после этого события. Полный резерв времени Rп (i, j) работы (i, j) показывает, на сколько можно увеличить время выполнения данной работы при условии, что срок выполнения комплекса работ не измениться. Полный резерв работы (i, j) вычисляется по формуле: Rп(i,j) = iп (j) − iр (i) − t(i, j). Частный резерв времени первого вида R1 работы (i, j) есть часть полного резерва времени, на которую можно увеличить продолжительность работы, не изменив при этом позднего срока ее начального события. Этим резервом можно располагать при выполнении этой работы в предположении, что ее начальное и конечное события свершатся в свои самые поздние сроки. Резерв R1 (i, j) вычисляется по формулам: y Модели СПУ R1 (i, j) = tп (j) − tп (i) − t(i, j), R1 (i, j) = Rп (i, j) − R(i). Стр. 85 из 136 JI JIxy y × y Оглавление 4.3 Временные параметры сетевых графиков y II JJ Частный резерв времени второго вида, или свободный резерв Rс работы (i, j) есть часть полного резерва времени, на которую можно увеличить продолжительности работы, не изменив при этом раннего срока ее конечного события. Этим резервом можно располагать при выполнении данной работы в предположении, что ее начальное и конечное события свершаться в свои самые ранние сроки. Резерв Rс вычисляется по формулам: Rс (i, j) = tр (j) − tр (i) − t(i, j), Rс (i, j) = Rп (i, j) − R(j). Свободным резервом времени можно пользоваться для предотвращения случайностей, которые могут возникнуть в ходе выполнения работ. Если планировать выполнение работ по ранним срокам их начала и окончания, то всегда будет возможность при необходимости перейти на поздние сроки начала и окончания работ. y Модели СПУ Стр. 86 из 136 JI JIxy y × y Оглавление 4.3 Временные параметры сетевых графиков y II JJ Независимый резерв времени Rн работы (i, j)1 есть часть полного резерва времени, получаемая для случая, когда все предшествующие работы заканчиваются в самые поздние сроки, а все последующие работы начинаются в ранние сроки. Резерв Rн вычисляется по формулам: Rн (i, j) = tр (j) − tп (i) − t(i, j), Rн (i, j) = Rп (i, j) − R(i) − R(j). У работы (i, j) имеется независимый резерв, если Rн (i, j) > 0. Отрицательное значение Rн (i, j) реального смысла не имеет. Использование независимого резерва времени не влияет на величину резервов времени других работ. Независимые резервы стремятся использовать в случае, когда окончание предыдущей работы произошло в поздний допустимый срок, а последующие работы хотят выполнять в ранние сроки. Работы, лежащие на критическом пути, резервов времени не имеют (он равен нулю). y y 1 В ряде работ по системному планированию резерв времени Rп (i, j) называют свободным, а резерв Rс (i, j) специального названия не имеет. Модели СПУ Стр. 87 из 136 JI JIxy × y Оглавление 4.3 Временные параметры сетевых графиков y II JJ Резерв времени пути. Для пути L резерв времени R(L) определяется как разность между длиной критического пути и рассматриваемого пути: R(L) = tкр − t(L). Он показывает, на сколько в сумме могут быть увеличены продолжительности всех работ, принадлежащие этому пути. Любая из работ пути L на его участке, не совпадающая с критическим путем (некритической дуги), обладает резервом времени. Резерв пути L формируется из резервом событий, лежащих на пути L. В то же время, резерв R(L) не складывается из резервов времени работ, лежащих на его пути L, и не всегда складывается из резервов событий на этом пути. Например, пусть на пути L есть два последовательных некритических события i и j. Тогда они имеет одинаковый резерв времени и при полном использовании этого резерва для одного события будет означать исчезновение резерва для другого события. y Модели СПУ Стр. 88 из 136 JI JIxy y × y y y y Оглавление 4.3 Временные параметры сетевых графиков II JJ Пример 4.2. Рассчитаем временные параметры сети, задаваемой проектом в табл. 4.1 и его линейной диаграммой на рис. 4.4. Решение. Сначала рассчитаем временные параметры сети для событий. На первом этапе найдем ранние сроки свершения событий, используя рекуррентные формулы: Событие 1: tр (1) = 0. событие 2: tр (2) = tр (1) + t(1, 2) = 0 + 2 = 2. Событие 5: tр (5) = tр (1) + t(1, 5) = 0 + 3 = 3. Событие 3: tр (3) = max{tр (1) + t(1, 3); tр (2) + t(2, 3)} = = max{0 + 3; 2 + 0} = 3. Событие 4: tр (4) = tр (3) + t(3, 4) = 3 + 2 = 5. Событие 6: tр (6) = tр (4) + t(4, 6) = 5 + 4 = 9. Событие 7: tр (7) = max{tр (5) + t(5, 7); tр (6) + t(6, 7)} = = max{3 + 1; 9 + 2} = 11. Событие 8: tр (8) = max{tр (1) + t(1, 8); tр (7) + t(7, 8)} = = max{0 + 4; 11 + 2} = 13. Событие 9: tр (9) = tр (7) + t(7, 8) = 13 + 4 = 17. Модели СПУ Стр. 89 из 136 JI JIxy × y Оглавление 4.3 Временные параметры сетевых графиков y II JJ На втором этапе найдем поздние сроки свершения событий. Заметим, что начальное событие 1 и завершающее 9 являются критическими, поэтому для них ранние и поздние сроки свершения совпадают. Для остальных событий будем использовать рекуррентные формулы: Событие 9: tп (9) = tр (9) = 17. Событие 8: tп (8) = tп (9) − t(8, 9) = 17 − 4 = 13. Событие 7: tп (7) = tп (8) − t(7, 8) = 13 − 2 = 11. Событие 6: tп (6) = tп (7) − t(6, 7) = 11 − 2 = 9. Событие 5: tп (5) = tп (7) − t(5, 7) = 11 − 1 = 10. Событие 4: tп (4) = tп (6) − t(4, 6) = 9 − 4 = 5. Событие 3: tп (3) = tп (4) − t(3, 4) = 5 − 2 = 3. Событие 2: tп (2) = tп (3) − t(2, 3) = 3 − 0 = 3. Событие 1: tп (1) = tр (1) = 0. На третьем этапе найдем критические события и резервы времени для некритических событий. Для критических событий ранние и поздние сроки свершения совпадают, значит, критическими событиями являются: 1, 3, 4, 4, 6, 7, 8, 9. Они образуют критический путь и критические процессы (работы) (1, 3), (3, 4), (4, 6), (6, 7), (7, 8) и (8, 9). Некритическими являются события 2 и 5. Они имеют резервы времени: R(2) = tп (2)−tр (2) = 3−2 = 1; y Модели СПУ R(5) = tп (5)−tр (5) = 10−3 = 7. Стр. 90 из 136 JI JIxy y × y y y y Оглавление 4.3 Временные параметры сетевых графиков II JJ Теперь рассчитаем временные параметры для работ. Критические работы не имеют ни каких резервов времени. Поэтому вычислим резервы времени для некритических работ (1, 2), (2, 3), (1, 5), (5, 7) и (1, 8). Общие (или полные) запасы (резервы) времени: Rп (1, 2) = tп (2) − tр (1) − t(1, 2) = 3 − 0 − 2 = 1; Rп (2, 3) = tп (3) − tр (2) − t(2, 3) = 3 − 2 − 0 = 1; Rп (1, 5) = tп (5) − tр (1) − t(1, 5) = 10 − 0 − 3 = 7; Rп (5, 7) = tп (7) − tр (5) − t(5, 7) = 11 − 3 − 1 = 7; Rп (1, 8) = tп (8) − tр (1) − t(1, 8) = 13 − 0 − 4 = 9. Частные резервы времени первого вида: R1 (1, 2) = Rп (1, 2) − R(1) = 1 − 0 = 1; R1 (2, 3) = Rп (2, 3) − R(2) = 1 − 1 = 0; R1 (1, 5) = Rп (1, 5) − R(1) = 7 − 0 = 7; R1 (5, 7) = Rп (5, 7) − R(5) = 7 − 7 = 0; R1 (1, 8) = Rп (1, 8) − R(1) = 9 − 0 = 9. Частные резервы времени второго вида (свободный резерв): R1 (1, 2) = Rп (1, 2) − R(2) = 1 − 1 = 0; R1 (2, 3) = Rп (2, 3) − R(3) = 1 − 0 = 1; R1 (1, 5) = Rп (1, 5) − R(5) = 7 − 7 = 0; R1 (5, 7) = Rп (5, 7) − R(7) = 7 − 0 = 7; R1 (1, 8) = Rп (1, 8) − R(8) = 9 − 0 = 9. Независимые резервы времени: R1 (1, 2) = Rп (1, 2) − R(1) − R(2) = 1 − 0 − 1 = 0; R1 (2, 3) = Rп (2, 3) − R(2) − R(3) = 1 − 1 − 0 = 0; R1 (1, 5) = Rп (1, 5) − R(1) − R(5) = 7 − 0 − 7 = 0; R1 (5, 7) = Rп (5, 7) − R(5) − R(7) = 7 − 7 − 0 = 0; R1 (1, 8) = Rп (1, 8) − R(1) − R(8) = 9 − 0 − 0 = 9. Модели СПУ Стр. 91 из 136 JI JIxy × y y y y Оглавление 4.3 Временные параметры сетевых графиков II JJ Для некритических путей определим резервы времени. В нашем примере имеется три некритических (дуги) пути: L1 = (1, 2, 3), L2 = (1, 5, 7) и L3 = (1, 8). Найдем их продолжительность: t(L1 ) = t(1, 2) + t(2, 3) = 2 + 0 = 2; t(L2 ) = t(1, 5) + t(5, 7) = 3 + 1 = 4; t(L3 ) = t(1, 8) = 4. Они стягивают участки критического пути протяженностью соответственно tр (3) = 3, tр (7) = 11 и tр (8) = 13. Поэтому резервы этих дуг составляют: R(L1 ) = tр (3) − t(L1 ) = 3 − 2 = 1; R(L1 ) = tр (7) − t(L2 ) = 11 − 4 = 7; R(L3 ) = tр (8) − t(L3 ) = 13 − 4 = 9. Эти полные некритические пути содержат только одну из некритических дуг, поэтому их резервы совпадают с резервом соответствующей дуги. Например, полный путь (1, 5, 7, 8, 9) содержит некритическую дугу L2 и поэтому имеет резерв времени 7. Модели СПУ Стр. 92 из 136 JI JIxy × y Оглавление 4.4 Оптимизация сетевого графика 4.4 Оптимизация сетевого графика y II JJ После построения сетевого графика и расчета его временных характеристик проводят его анализ и принимают меры по оптимизации. Элементы анализа: • анализ топологии сети (контроль построения сети, определение целесообразности выбора работ и степени их расчленения); • классификация и группировка работ по величинам резервов, степени напряженности работ; y Модели СПУ Стр. 93 из 136 JI JIxy y × y Оглавление 4.4 Оптимизация сетевого графика y II JJ Коэффициент напряженности работы. Степень трудности выполнения в срок работы определяется величиной ее резервов, но более точную характеристику дает коэффициент напряженности работы. Коэффициентом напряженности Kн работы (i, j) называется отношение продолжительности несовпадающих (заключенных между одними и теми же событиями) отрезков пути, одним из которых является путь максимальной продолжительности, проходящей через данную работу, а другой — критический путь: Kн (i, j) = t(Lmax ) − tкр , tкр − tкр где t(Lmax ) — продолжительность максимального пути, проходящего через работу (i, j); tкр — продолжительность (длина) 0 — продолжительность отрезка рассматкритического пути; tкр риваемого пути, совпадающего с критическим путем. Коэффициент напряженности Kн (i, j) работы (i, j) можно выразить через полный резерв Rп этой работы: Kн (i, j) = 1 − Rп . tкр − tкр Значение коэффициента напряженности Kн (i, j) может изменяться в пределах от 0 (для работ, у которых отрезки максимального из путей, не совпадающим с критическим путем, состоят из фиктивных работ нулевой продолжительности) до 1 (для работ критической дуги). По коэффициентам напряженности работ производят их классификацию по зонам: • критическая зона — Kн (i, j) > 0,8; • подкритическая зона — 0,6 6 Kн (i, j) 6 0,8; • резервная — Kн (i, j) < 0,6. y Модели СПУ Стр. 94 из 136 JI JIxy y × y y y y Оглавление 4.4 Оптимизация сетевого графика II JJ Оптимизация сетевого графика — это процесс улучшения организации выполнения комплекса работ с целью сокращения длины критического пути, выравнивая коэффициентов напряженности работ, рационального использования ресуров: • перераспределение всех видов ресурсов из зон менее напряженных в более напряженные; • сокращение трудоемкости критических работ за счет передачи части работ на другие пути, имеющие резервы времени; • параллельное выполнение работ критического пути; • пересмотри топологии сети, изменением состава работ и структуры сети. Модели СПУ Стр. 95 из 136 JI JIxy × y Оглавление В.М. Караулов Глава 5 Классические методы оптимизации y II JJ В общем случае задача оптимизации представляется с помощью нелинейной целевой функции и нелинейной системой ограничений. Неотрицательность переменных не обязательна. Если ограничения представляются в виде уравнений, число ограничений меньше числа переменных, переменные не являются дискретными и все функции имеют непрерывные частные производные до второго порядка, такие задачи можно решать классическими методами дифференциального исчисления. На практике реализация такого подхода может вызывать существенные проблемы, поэтому возникает необходимость поиска альтернативных методов решения. Классические методы остаются как основа для теоретического анализа. y Классические методы оптимизации Стр. 96 из 136 JI JIxy y × y Оглавление 5.0.1 В.М. Караулов Метод множителей Лагранжа y II JJ Рассмотрим частный случай — функции от двух переменных, а ограничение состоит из одной функции (как в предыдущем примере): max f (x, y), при ограничении g(x, y) = b. Если X ∗ = (x∗ , y∗ ) — решение задачи, то это значит, линия уровня Fmax для целевой функции и линия уровня b для ограничения g(x, y) = b в точке X ∗ касаются и векторы нормалей линий в этой точке будут коллинеарны (координаты пропорциональны): fx0 = λgx0 , fy0 = λgy0 , где λ — некоторый коэффициент пропорциональности. Перепишем эти условия: fx0 − λgx0 = 0, fy0 − λgy0 = 0. Последнее условие и ограничение b − g(x, y) = 0 — это условие стационарности точки (x, y, λ) (условие первого порядка) функции L(x, y, λ) = f (x, y) + λ(b − g(x, y). Эта функция называется функцией Лагранжа или лагранжианом. Данные наблюдения позволяют построить алгоритм нахождения условного экстремума. y Классические методы оптимизации Стр. 97 из 136 JI JIxy y × y Оглавление В.М. Караулов y II JJ Алгоритм нахождения условного экстремума двумерной задачи max f (x, y) с одним ограничением g(x, y) = b: 1. Сначала составляется функция Лагранжа L(x, y, λ) = f (x, y) + λ(b − g(x, y)). 2. Вычисляются частные производные функции Лагранжа: Lx , Ly , Lλ .  3. Решается система Lx = 0, Ly = 0, L = 0 λ (условие первого порядка) и находится решение X ∗ = (x∗ , y∗ ). Для общей задачи max F (x1 , . . . , xn )  g (x , . . . , xn ) = bi ;   1 1 g (x , . . . , xn ) = bi ; при ограничениях · ·2· 1   gm (x1 , . . . , xn ) = bi функция Лагранжа имеет вид: L(x1 , . . . , xn , λ1 . . . λm ) = F (x1 , . . . , xn ) + m X
λi bi − gi (x1 , . . . , xn ) , i=1 т. е. на каждое ограничение в форме равенства используется свой множитель Лагранжа. Необходимое условие первого порядка для нахождения экстремума (стационарной точки функции Лагранжа) имеет вид: Lxj (x1∗ , . . . , xn∗ , λ∗1 , . . . , λ∗m ) = y = Fxj (x1∗ , . . . , xn∗ ) Lλi (x1∗ , . . . , xn∗ , λ∗1 . . . λ∗m ) − m X λ∗i gix (x1∗ , . . . , xn∗ ) = 0, j i=1 = bi −gi (x1∗ , . . . , xn∗ ) = 0, i = 1, . . . , m. y Если целевая функция является строго вогнутой, а функции ограничений выпуклыми, то данное условия оказывается достаточным для нахождения экстремума. Классические методы оптимизации Стр. 98 из 136 JI JIxy × y Оглавление 5.0.2 В.М. Караулов Неотрицательность переменных y II JJ Рассмотрим простейшее ограничение форме неравенства для задачи нелинейного программирования: max F (x1 , . . . , xn ) при ограничениях x1 > 0, . . . , xn > 0. Согласно теореме Вейерштрасса наибольшее и наименьшее значение целевой функции нужно искать во внутренних точках локального экстремума, т. е. в точках, для которых Fxj = 0, j = 1, . . . , n, либо на границе, т. е. в точках, для которых при некоторых j = 1, . . . , n значение xj = 0. Но если в граничной ∗ , 0, x∗ , . . .) достигается максимум, то в точке X ∗ = (. . . , xj−1 j+1 окрестности точки X ∗ в направлении оси j функция F (X) убывает, т. е. Fxj (X ∗ ) < 0. Данные условия можно объединить в систему: Fxj (X ∗ ) 6 0, y Fxj (X ∗ ) · xj∗ = 0, xj∗ > 0, Классические методы оптимизации Стр. 99 из 136 j = 1, . . . , n. JI JIxy y × y Оглавление 5.0.3 В.М. Караулов Условия Куна-Таккера y II JJ Пусть в задаче нелинейного программирования ограничения представлены в форме неравенств max F (x1 , . . . , xn )  g (x , . . . , xn ) 6 bi ;   1 1 g (x , . . . , x ) 6 bi ; при ограничениях · ·2· 1 · · · n   gm (x1 , . . . , xn ) 6 bi . Переведем систему неравенств в систему уравнений с помощью дополнительных неотрицательных переменных Z(z1 , . . . zm ), zi > 0 и получим задачу: max F (x1 , . . . , xn )  g1 (x1 , . . . , xn ) + z1 = bi ;    g2 (x1 , . . . , xn ) + z2 = bi ; ··· при ограничениях · · ·   g (x , . . . , xn ) + zm = bi , m 1   z1 > 0, . . . , zm > 0. Без учета ограничений на неотрицательность дополнительных переменных данную задачу можно решить с помощью функции Лагранжа: L(xj , λi , zi ) = F (x1 , . . . , xn ) + λ1 (b1 − g1 (x1 , . . . , xn ) − z1 )+ + . . . + λm (bm − gm (x1 , . . . , xn ) − zm ). Условия экстремума точки (X ∗ , Λ∗ , Z ∗ ) будут иметь вид: Lxj (X ∗ , Λ∗ , Z ∗ ) = y ∗ = Fxj (X ) − m X λ∗i gix (x1∗ , . . . , xn∗ ) = 0, j j = 1, . . . , n, i=1 ∗ ∗ Lλi (X ∗ , Λ , Z ) = bi − gi (x1∗ , . . . , xn∗ ) − zi∗ = 0, Lzi (X ∗ , Λ∗ , Z ∗ ) = −λ∗i = 0, i = 1, . . . , m. Классические методы оптимизации Стр. 100 из 136 JI JIxy y × y Оглавление В.М. Караулов y II JJ Второе условие позволяет явным образом выразить дополнительные переменные, с тем чтобы их подставить в функцию Лагранжа и уменьшить число переменных: zi = bi −gi (x1 . . . , xn ). Неотрицательность по Z требует корректировки третьего условия: Lzi (X ∗ , Λ∗ , Z ∗ ) = −λ∗i 6 0, m m X X Lzi (X ∗ , Λ∗ , Z ∗ ) · zi∗ = − λ∗i (bi − gi (x1∗ , . . . , xn∗ )) = 0, i=1 bi − i=1 gi (x1∗ , . . . , xn∗ ) > 0, i = 1, . . . , m. Таким образом мы получаем условия Куна-Таккера для решения (X ∗ , Λ∗ ) задачи нелинейного программирования при наличии ограничения в форме неравенства: Fxj (X ∗ ) − m X λ∗i gix (x1∗ , . . . , xn∗ ) = 0, j i=1 bi − gi (x1∗ , . . . , xn∗ ) > 0, i = 1, . . . , m. m X λ∗i (bi − gi (x1∗ , . . . , xn∗ )) = 0, λi > 0. i=1 Такие же условия можно получить для функции Лагранжа: y L(xj , λi ) = F (x1 , . . . , xn ) + λ1 (b1 − g1 (x1 , . . . , xn ))+ + . . . + λm (bm − gm (x1 , . . . , xn )) y с учетом неотрицательности множителей Лагранжа λi и дополнительных переменных zi . Классические методы оптимизации Стр. 101 из 136 JI JIxy × y Оглавление В.М. Караулов y II JJ Алгоритм выделения условий Куна-Таккера Пусть имеется задача нелинейного программирования, в которой ограничения представлены в форме неравенств и переменные неотрицательные: max F (x1 , . . . , xn )  g (x , . . . , xn ) 6 bi ;   1 1 g (x , . . . , xn ) 6 bi ; при ограничениях · ·2· 1   gm (x1 , . . . , xn ) 6 bi , x1 > 0, . . . , xn > 0. 1. Сначала составим функции Лагранжа:
L(xj , λi ) = F (x1 , . . . , xn ) + λ1 b1 − g1 (x1 , . . . , xn ) +
+ . . . + λm bm − gm (x1 , . . . , xn ) . 2. Найдем частные производные функции Лагранжа. 3. Для оптимального решения (X ∗ , Λ∗ ) у функции Лагранжа частные производные по xj должны быть неположительными, по λi неотрицательными, плюс условия дополняющей нежесткости для переменных xj и для переменных λ (аналоги условий дополняющей нежесткости в задаче линейного программирования). y Классические методы оптимизации Стр. 102 из 136 JI JIxy y × y Оглавление В.М. Караулов y II JJ Таким образом условия Куна-Таккера для решения (X ∗ , Λ∗ ) имеют вид: Lxj = Fxj − n X m X j = 1, . . . , n, i=1 Lxj · xj = i=1 λi gix 6 0, j n  X i=1 Fxj − m X  λi gix · xj = 0, j i=1 Lλi = bi − gi > 0, m m X X λi · Lxj = λi · (bi − gi ) = 0, i=1 xj > 0, j = 1, . . . , n, i = 1, . . . , m, λi > 0, i = 1, . . . m, i=1 где все переменные, функции и производные вычисляются в точке (X ∗ , Λ∗ ). В случае когда целевая функция является строго вогнутой, а функции ограничений выпуклые, то система неравенств, входящих в условия Куна-Таккера, имеет единственное решение в точке глобального максимума. y Классические методы оптимизации Стр. 103 из 136 JI JIxy y × y Оглавление В.М. Караулов y II JJ Условия Куна-Таккера полностью характеризуют решение задачи, но они мало пригодны для отыскания самого решения. Их можно использовать для аналитической проверки конкретного решения на оптимальность. Поэтому для отыскания оптимальных решений на практике применяют другие методы. Точка (0, 0) не удовлетворяет условиям Куна-Таккера — в ней λ1 = λ2 = 0, а L0x2 = 80. Точка (1/2, 0) также не удовлетворяет условиям, так как λ1 = 0, а L0x2 = 86. Точка (0, 1) является решением задачи. В ней выполняются все условия КунаТаккера: x1 = 0, x2 = 1, λ1 = 60, λ2 = 0, F (X ∗ ) = 70. Важную роль при поиске оптимума играет свойство выпуклости: если в задаче на максимум целевая функция является вогнутой, а ограничения — строго выпуклыми функциями, то условия Куна-Таккера становятся достаточными для поиска глобального экстремума. y Выпуклое программирование Стр. 104 из 136 JI JIxy y × y Оглавление В.М. Караулов Глава 6 Выпуклое программирование y Выпуклое программирование Стр. 105 из 136 JI JIxy y II JJ y × y Оглавление 6.1 Задача выпуклого программирования 6.1 Задача выпуклого программирования y II JJ Рассмотрим задачу нелинейного программирования при ограничениях в форме неравенств: F (x1 , . . . , xn ) → max(min)  g (x , . . . , xn ) 6 bi ;   1 1 g (x , . . . , x ) 6 bi ; при ограничениях · ·2· 1 · · · n   gm (x1 , . . . , xn ) 6 bi (неотрицательность переменных может быть включена в систему ограничений). Если все ограничения gj (X) являются выпуклыми функциями на некотором множестве M, а целевая функция F (X) в случае максимизации является вогнутой (в случае минимизации — выпуклой), то такая задача является задачей выпуклого программирования. Если в задаче выпуклого программирования (на максимум) целевая функция является строго вогнутой, а ограничения — строго выпуклые и область решения этой системы ограничений не пуста и ограничена, то задача выпуклого программирования всегда имеет единственное решение. Это решение достигается во внутренней (стационарной) точке области ограничений или на границе этой области (если нет стационарных точек). В общем случае в задаче линейного программирования область оптимальных решений является выпуклым множеством. y Выпуклое программирование Стр. 106 из 136 JI JIxy y × y Оглавление 6.1 Задача выпуклого программирования y II JJ Для проверки функции на выпуклость можно использовать критерий Сильвестра: дважды дифференцируемая функция является выпуклой тогда и только тогда, когда неотрицательны все главные миноры ∆k матрицы Гёссе (вторых частных производных): Fx1 x1 Fx1 x2 . . . Fx1 xk Fx2 x1 Fx2 x2 . . . Fx2 xk ∆k = ··· ··· ··· ··· Fxk x1 Fxk x2 . . . Fxk xk Если все главные миноры являются строго положительными, то функция является строго выпуклой. Задачи линейного программирования являются частным случаем задач выпуклого программирования, так как линейные функция являются одновременно выпуклыми и вогнутыми. Поэтому одним из способов решения задачи выпуклого программирования является приближение (аппроксимация) выпуклых (вогнутых) функций кусочно-линейными и поиск решения алгоритмами задач линейного программирования. y Выпуклое программирование Стр. 107 из 136 JI JIxy y × y Оглавление 6.2 Аппроксимация задачи выпуклого программирования кусочно-линейным. . . 6.2 Аппроксимация задачи выпуклого программирования кусочно-линейным программированием y II JJ Наиболее простая аппроксимация получается для сепарабельных функций. Функция называется сепарабельной, если её можно представить в виде суммы n функций, по одной для каждой переменной xj . Для сепарабельных целевой функции и ограничений постановка задачи имеет вид: n X F= fj (xj ) → max(min) j=1 при ограничениях n X gij (xj ) 6 bi , i = 1, . . . , m; xj > 0, j = 1, . . . , n. j=1 Приближённый метод решения задачи состоит в кусочнолинейной аппроксимации функций fj (xj ) и gij (xj ), т. е. замене на определенном интервале по xj нелинейных функций линейными и получении на этом интервале решения обычным симплексным методом. Для построения кусочно-линейной аппроксимации выбирают некоторую сетку значений xj : y (pj ) a1 6 xj(1) < xj(2) < . . . < xj 6 a2 , y где [a1 , a2 ] — область изменений переменной xj . Для получения более высокой степени аппроксимации увеличивают сетку значений xj(k) . Например, можно между каждыми точками xj(k) и xj(k+1) добавить точку в их середину. Выпуклое программирование Стр. 108 из 136 JI JIxy × y Оглавление 6.2 Аппроксимация задачи выпуклого программирования кусочно-линейным. . . 6.2.1 6.2.1 Метод средневзвешенных y II JJ Любое значение xj будем выражать, используя средневзве(kj ) шенную функцию сетки значений xj xj = xj(1) w1 + xj(2) w2 + ... + с весами wkj > 0: (p ) xj j wpj = pj X (kj ) xj wkj , kj =1 где w1j + . . . + wpj = 1, причем для внутренних точек xj отрезка  (kj ) (kj +1)  xj , xj ненулевыми будут только веса wkj и w(kj +1) ; если (k ) xj = xj j , то wkj = 1, а остальные веса нулевые. Оптимизационная модель принимает вид: max F (x1 , . . . , xn ) = f1 (x1 ) + . . . + fn (xn ) ≈ p1 X ≈ pn X

f1 x1(k1 ) wk1 + . . . + fn xn(kn ) wkn k1 =1 kn =1 при ограничениях n X j=1 gij (xj ) ≈ p1 X
gi1 x1(k1 ) wk1 k1 =1 w1j + . . . + wpj = 1, y + ... + Выпуклое программирование pn X
gn1 xn(kn ) wkn 6 bi , kn =1 wkj > 0, j = 1, . . . , n, Стр. 109 из 136 i = 1, . . . , m. JI JIxy y × y Оглавление 6.2 Аппроксимация задачи выпуклого программирования кусочно-линейным. . . Пример 6.1. 6.2.1 Найти минимум функции Z = 2(x1 − 1)2 + (x2 − 2)2 если x12 + x2 6 4, x1 > 0, x2 > 0 методом средневзвешенных. y II JJ Решение. В задаче функции выпуклые и сепарабельные. В частности, возьмем f1 (x1 ) = 2(x1 − 1)2 , f2 (x2 ) = (x2 − 2)2 , g1 (x1 ) = g11 (x1 ) = x12 , g2 (x2 ) = g12 (x2 ) = x2 . Из системы ограничений следует, что x1 ∈ [0; 2], x2 ∈ [0; 4]. В качестве точек сетки значений переменных возьмем целочисленные и найдем значения функций f1 , f2 , g1 , g2 в точках сетки: x1 x10 x11 x12 x1 0 1 2 g1 0 1 4 f1 2 2 y Выпуклое программирование x2 x20 x21 x22 x23 x24 x2 0 1 2 3 4 g2 0 1 2 3 4 f2 4 1 1 4 Стр. 110 из 136 JI JIxy y × y Оглавление 6.2 Аппроксимация задачи выпуклого программирования кусочно-линейным. . . 6.2.1 y II JJ Выразим переменные x1 и x2 как взвешанные суммы узлов сетки x1k и x2k с весами w1k и w2k : x1 = 2 X w1k x1k = 0w10 + 1w11 + 2w12 , k=0 x2 = 4 X w2k x2k = 0w20 + 1w21 + 2w22 + 3w23 + 4w24 , k=0 g1 = 2 X w1k g1k = 0w10 + 1w11 + 4w12 , k=0 g2 = 4 X w2k g2k = 0w20 + 1w21 + 2w22 + 3w23 + 4w24 , k=0 f1 = 2 X w1k f1 = 2w10 + 0w11 + 2w12 , k=0 f2 = 4 X w2k f2 = 4w20 + 1w21 + 0w22 + 1w23 + 4w24 . k=0 Таким образом, приближенная задача для данной задачи выпуклого программирования имеет вид: Найти минимум функции Z = 2w10 + 0w11 + 2w12 + 4w20 + 1w21 + 0w22 + 1w23 + 4w24 y при ограничениях:  0w + 1w11 + 4w12 + 0w20 + 1w21 + 2w22 + 3w23 + 4w24 6 4,   10 w10 + w11 + w12 = 1,  w20 + w21 + w22 + w23 + w24 = 1, все wij > 0. Выпуклое программирование Стр. 111 из 136 JI JIxy y × y Оглавление 6.2 Аппроксимация задачи выпуклого программирования кусочно-линейным. . . 6.2.1 y II JJ Это задача линейного программирования с 8 переменными wij . Для ее решения симплекс методом необходимо ввести еще одну дополнительную переменную w для построения канонической системы ограничений: 0w10 + 1w11 + 4w12 + 0w20 + 1w21 + 2w22 + 3w23 + 4w24 + w = 4. Для получения первого допустимого решения выберем 3 основные переменные. Заметим, что среди весов wi и wk не соседних точек сетки делений (например, x1 ) один обязательно будет нулевым. Поэтому в качестве базисных весов нужно выбирать не более двух соседних весов сетки x1 . В данной задаче в качестве основных переменных можно взять w10 , w20 и w — они встречаются по одному разу в различных уравнениях. Но реализовывать симплексный алгоритм пока нельзя, так как коэффициенты целевой функции при w10 и w20 не равны нулю, т. е. не выражены через неосновные переменные. Рассмотрим решение данной проблемы двумя способами. y Выпуклое программирование Стр. 112 из 136 JI JIxy y × y Оглавление 6.2 Аппроксимация задачи выпуклого программирования кусочно-линейным. . . 6.2.1 y II JJ Способ 1 (метод подстановки). Выразим из ограничений w10 и w20 : w10 = 1 − w11 − w12 , w20 = 1 − w21 − w22 − w23 − w24 и подставим целевую функцию: Z = 2(1 − w11 − w12 ) + 2w12 + + 4(1 − w21 − w22 − w23 − w24 ) + 1w21 + 1w23 + 4w24 = = 6 − 2w11 − 3w21 − 4w22 − 3w23 . Теперь может быть реализован симплексный алгоритм с базисными (основными) переменными w10 , w20 и w. y Выпуклое программирование Стр. 113 из 136 JI JIxy y × y Оглавление 6.2 Аппроксимация задачи выпуклого программирования кусочно-линейным. . . 6.2.1 Заменим задачу на минимум задачей на максимум: F = −Z = −6 + 2w11 + 3w21 + 4w22 + 3w23 → max . Представим целевую функцию в канонической форме: F − 2w11 − 3w21 − 4w22 − 3w23 = −6 → max . y II JJ Тогда первая симплексная таблица с базисными (основными) переменными w10 , w20 и w имеет вид: Базис w w10 w20 F w10 1 Таблица 6.1. Первая симплексная таблица w11 w12 w20 w21 w22 w23 w24 1 4 1 2 3 4 1 1 1 1 1 1 1 -2 -3 -4 -3 w 1 bi 4 1 1 -6 Далее идет реализация обычного симплексного алгоритма с целевой функцией на максимум. В частности, по критерию оптимальности на максимум среди коэффициентов имеются отрицательные. Поэтому значение целевой функции может быть улучшено. В качестве разрешающего выбирают столбец, содержащий максимальный по модулю отрицательный коэффициент целевой функции. В нашем случае это означает, что на следующем шаге в базис нужно вводить переменную w22 . y Выпуклое программирование Стр. 114 из 136 JI JIxy y × y Оглавление 6.2 Аппроксимация задачи выпуклого программирования кусочно-линейным. . . 6.2.1 y II JJ В данном случае задача линейного программирования была получена из задачи выпуклого программирования методом средневзвешанных. Поэтому на симплексный алгоритм накладываются дополнительные требования. В данной задаче в базис можно вводить переменную с неположительным коэффициентом в целевой функции, если в базисе оказывается не более двух соседних базисных переменных вида w1i и не более двух соседних базисных переменных вида w2i . С учетом этого требования переменную w22 вводить нельзя, поэтому можно вводить переменную w21 (соседнюю с w20 ) и выводить из базиса w20 . Дальнейшее решение с помощью симплексного алгоритма представлено в таблице 6.2. Таблица 6.2. Реализация симплексного алгоритма Базис w10 w11 w12 w20 w21 w22 w23 w24 w bi w 1 4 -1 1 2 3 1 3 w10 1 1 1 1 w21 1 1 1 1 1 1 F0 -2 3 -1 3 -3 bi /aij 3 1 ∞ Базис w10 w -1 w11 1 w21 F0 2 w11 1 w12 3 1 2 w20 -1 1 3 w21 1 w22 1 1 -1 w23 2 1 w24 3 1 3 w 1 bi 2 1 1 -1 bi /aij 2 ∞ 1 Базис w10 w -1 w11 1 w22 F0 2 w11 1 w12 3 1 2 w20 -2 1 4 w21 -1 1 1 w22 1 w23 1 1 1 w24 2 1 4 w 1 bi 1 1 1 bi /aij y y Таким образом, W ∗ (0, 1, 0, 0, 0, 1, 0, 0, 1) и получаем приближенное решение x1∗ = 1 · 1 = 1, x2∗ = 2 · 1 = 2 и Z(1, 2) = 0. Выпуклое программирование Стр. 115 из 136 JI JIxy × y Оглавление 6.2 Аппроксимация задачи выпуклого программирования кусочно-линейным. . . 6.2.1 y II JJ Способ 2 (метод искусственных переменных). Переменные w10 и w20 нельзя брать в качестве основных (базисных) потому, что целевая функция выражается через эти переменные. Поэтому во второе и третье ограничения введем искусственные переменные y1 и y2 : w10 + w11 + w12 + y1 = 1, w20 + w21 + w22 + w23 + w24 + y2 = 1 и добавим функцию штрафа в целевую функцию (коэффициенты штрафа должны превышать по модулю остальные коэффициенты целевой функции и функция штрафа должна ухудшать значение целевой функции при ненулевых значениях искусственных переменных): Z 0 = 2w10 +2w12 +4w20 +1w21 +1w23 +4w24 +10y1 +10y2 → min . Заменим задачу на минимум эквивалентной задачей на максимум и запишем в каноническом виде: F 0 +2w10 +2w12 +4w20 +1w21 +1w23 +4w24 +10y1 +10y2 = 0 → max . Теперь реализуем метод больших штрафов симплексным методом. Составим исходную симплексную таблицу: y Базис w10 w 1 F0 2 Таблица 6.3. Исходная симплексная таблица (метод больших штрафов) w11 w12 w20 w21 w22 w23 w24 w y1 y2 1 4 1 2 3 4 1 1 1 1 1 1 1 1 1 1 1 2 4 1 1 4 0 10 10 Выпуклое программирование Стр. 116 из 136 bi 4 1 1 bi /aij ∞ 1 ∞ JI JIxy y × y Оглавление 6.2 Аппроксимация задачи выпуклого программирования кусочно-линейным. . . 6.2.1 y II JJ Введем в базис сначала искусственную переменную y1 , а потом y2 . В результате значение целевой функции ухудшится. Потом будем вводить в базис переменные, улучшающие значение целевой функции (с отрицательными коэффициентами в целевой функции). Дополнительно будем отслеживать, чтобы в базисе оказалось не более двух соседних базисных переменных вида w1i и не более двух соседних базисных переменных вида w2i . Результаты реализации этого алгоритма представлены в таблице 6.4. y Выпуклое программирование Стр. 117 из 136 JI JIxy y × y Оглавление 6.2 Аппроксимация задачи выпуклого программирования кусочно-линейным. . . 6.2.1 Таблица 6.4. Реализация симплексного алгоритма с использованием метода больших штрафов Базис w10 w11 w12 w20 w21 w22 w23 w24 w y1 y2 bi bi /aij w 1 4 1 2 3 4 1 4 ∞ 1 1 1 1 1 1 1 1 1 1 1 1 1 ∞ F0 2 2 4 1 1 4 0 10 10 0 Базис w10 w11 w12 w20 w21 w22 w23 w24 w w 1 4 1 2 3 4 1 y1 1 1 1 1 1 1 1 1 F0 -8 -10 -8 4 1 1 4 y1 1 y2 bi bi /aij 4 ∞ 1 ∞ 1 1 1 10 -10 Базис w10 w11 w12 w20 w21 w22 w23 w24 w w 1 4 1 2 3 4 1 y1 1 1 1 y2 1 1 1 1 1 F0 -8 -10 -8 -6 -9 -10 -9 -6 0 y1 1 y2 bi bi /aij 4 4 1 1 1 1 ∞ 0 -20 Базис w10 w11 w12 w20 w21 w22 w23 w24 w w -1 0 3 1 2 3 4 1 w11 1 1 1 y2 1 1 1 1 1 F0 2 2 -6 -9 -10 -9 -6 0 y1 -1 1 10 y2 bi bi /aij 3 1,5 1 ∞ 1 1 1 0 -10 Базис w10 w11 w12 w20 w21 w22 w23 w24 w w -1 0 3 -2 -1 0 1 2 1 w11 1 1 1 w22 1 1 1 1 1 F 2 2 4 1 1 4 y1 -1 1 10 y2 -2 1 10 y bi 1 1 1 y II JJ bi /aij y Заметим, что на последнем шаге получился результат, совпадающий с результатами последнего шага таблицы 6.2 (если не учитывать искусственные переменные). Выпуклое программирование Стр. 118 из 136 JI JIxy × y Оглавление 6.2 Аппроксимация задачи выпуклого программирования кусочно-линейным. . . 6.2.2 6.2.2 Аппроксимации функции путём увеличения числа неотрицательных, ограниченных сверху переменных (метод коэффициентов роста) y II JJ Пусть [x(0) , x(p) ] — область изменений переменной x функции f (x). Будем ее аппроксимировать функцией, представляющейся зависимостью (0) F (y1 , y2 , . . . yp−1 ) = f (x ) + p−1 X f (k) yk , k=1 где x = y1 + y2 + . . . + yp−1 и x(k+1) − x(k) > yk > 0, k = 1, 2, . . . , p−1 и f (k)

f x(k+1) − f x(k) = tg ϕ = x(k+1) − x(k) (рис. 6.1). f (x(1)) f (x(0)) y  x(0) x(1) y4 y3 y2 y1 (2) x (3) x (4) x Рис. 6.1. Аппроксимация функции методом коэффициентов роста y В этой формуле f (k) — коэффициент роста — характеризу ет среднюю скорость роста функции f на отрезке x(k) ; x(k+1) . Выпуклое программирование Стр. 119 из 136 JI JIxy × y Оглавление 6.2 Аппроксимация задачи выпуклого программирования кусочно-линейным. . . 6.2.2 y II JJ При использовании метода коэффициентов роста увеличивается число неотрицательных, ограниченных сверху переменных (yk ). Если все ограничения линейны, то можно воспользоваться симплексным методом. В результате исходная задача выпуклого программирования (при учете сепарабельности всех функций) F (x1 , . . . , xn ) → max  g1 (x1 , . . . , xn ) 6 b1 ; при ограничениях g2 (x1 , . . . , xn ) 6 b2 ; · · · ··· ··· заменяется (аппроксимируется) кусочно-линейной функцией F (y10 , y10 , . . . , y20 , y21 , . . .) = p2 −1 p1 −1  X (k)  X (k)   f2 y2k + . . . → max = f1 (x1(0) ) + f1 y1k + f2 (x2(0) ) + k=0 k=0 В ограничениях происходит замена функций на аппроксимирующие функции:  G1 (y10 , y10 , . . . , y20 , y21 , . . .) =        pP pP 1 −1 2 −1  (0) (k) (0) (k)   = g (x ) + g y + g (x ) + g y + . . . 6 b1 ; 11 1k 12 1k  1 11 2 12   k=0 k=0   G2 (y10 , y10 , . . . , y20 , y21 , . . .) =        pP pP 1 −1 2 −1 (k) (k) = g21 (x1(0) ) + g21 y2k + g22 (x2(0) ) + g22 y2k + . . . 6 b2 ;  k=0 k=0    ... ... ... ... ... ...      0 6 y10 6 x1(1) − x1(0) , 0 6 y11 6 x1(2) − x1(1) , . . . ,    (1) (0) (2) (1)   0 6 y20 6 x2 − x2 , 0 6 y11 6 x2 − x2 , . . . , ... ... ... ... ... ... y Выпуклое программирование Стр. 120 из 136 JI JIxy y × y Оглавление 6.2 Аппроксимация задачи выпуклого программирования кусочно-линейным. . . 6.2.2 y II JJ При решении нужно иметь в виду, что yk+1 может принимать положительные значения только в том случае, если значение yk равно его верхнему пределу x(k+1) − x(k) (соответствует правому концу отрезка x(k) ; x(k+1) . Таким образом, на любой итерации переменная yk+1 может быть введена в базис только в том случае, если переменная yk уже вошла в базис со своим максимально допустимым значением. Если x = y1 + y2 + y3 + y4 + . . . , то для того, чтобы получить значение x в интервале x(2) < x < x(3) , нужно, чтобы y1 = x(2) − x(1) . y Выпуклое программирование Стр. 121 из 136 JI JIxy y × y Оглавление 6.2 Аппроксимация задачи выпуклого программирования кусочно-линейным. . . Пример 6.2. 6.2.2 Найти минимум функции Z = 2(x1 − 1)2 + (x2 − 2)2 если x12 + x2 6 4, x1 > 0, x2 > 0 методом коэффициентов роста. y II JJ Решение. В задаче функции выпуклые и сепарабельные. В частности, возьмем f1 (x1 ) = 2(x1 − 1)2 , f2 (x2 ) = (x2 − 2)2 , g1 (x1 ) = g11 (x1 ) = x12 , g2 (x2 ) = g12 (x2 ) = x2 . Из системы ограничений следует, что x1 ∈ [0; 2], x2 ∈ [0; 4]. В качестве точек сетки значений переменных возьмем для x1 — 0, 1, 2 и для x2 — 0, 1,5, 4. Найдем значения функций f1(k) , f2(k) , g1(k) , g2(k) в точках сетки: x1 x10 x11 x12 x1 1 2 g1 1 4 (k) g1 1 3 f1 2 2 (k) f1 −2 2 x2 x20 x21 x22 x23 x2 1 2,5 4 g2 1 2,5 4 (k) g2 1 1 1 f2 4 1 0,25 4 f2(k) −3 −0,5 2,5 Таким образом, приближенная линейная задача для данной задачи выпуклого программирования имеет вид: Найти

Z = 2+(−2y10 +2y11 ) + 4+(−3y20 −1y21 +1y22 +4y23 ) → min y при ограничениях:

  0 + (1y10 + 3y11 ) + 0 + (1y20 + 1y21 + 1y22 + 1y23 ) 6 4, 0 6 y10 6 (1 − 0), 0 6 y11 6 (2 − 1),  0 6 y20 6 (1 − 0), 0 6 y21 6 (2,5 − 1), 0 6 y22 6 (4 − 2,5). Выпуклое программирование Стр. 122 из 136 JI JIxy y × y Оглавление 6.2 Аппроксимация задачи выпуклого программирования кусочно-линейным. . . 6.2.2 y II JJ Полученная задача линейного программирования имеет 6 переменных и 6 ограничений в форме неравенств. После приведения к каноническому виду системы ограничений с помощью дополнительных переменных получается 12 переменных и 6 ограничений в форме уравнений. Для поиска первоначального решения в качестве основных переменных можно выбрать дополнительные переменные, используемые для балансирования неравенств. В базис можно вводить переменные по-порядку, начиная с y10 или y20 . Напомним, что на любой итерации переменная yk+1 может быть введена в базис только в том случае, если переменная yk уже вошла в базис со своим максимально допустимым значением. Реализация метода кусочно-линейного программирования приведена в таблице 6.5. Таким образом, y10 = 1, y11 = 0, y20 = 1, y21 = 1,5, y22 = 0. Поэтому x1 = 1 + 0 = 1, x2 = 1 + 1,5 + 0 = 2,5 и Z = 2(1 − 1)2 + (2,5 − 2)2 = 0,25. Данный ответ немного отличается от решения, полученного методом средневзвешанных в примере 8, так как оба метода являются приближенными. Для повышения точности необходимо сделать более мелкое разбиение области изменения x1 и x2 , например, добавив к имеющимся дополнительные точки деления. Точным является решение X ∗ (1, 2) и Z(X ∗ ) = 0, так как сумма квадратов (неотрицательных чисел) минимальна тогда, когда она обращается в нуль. y Квадратичное программирование Стр. 123 из 136 JI JIxy y × y Оглавление 6.2 Аппроксимация задачи выпуклого программирования кусочно-линейным. . . 6.2.2 Таблица 6.5. Реализация кусочно-линейной аппроксимации (метод коэффициентов роста) Базис y10 y11 y20 y21 y22 y y1 y2 y3 y4 y5 bi bi /aij y 1 3 1 1 1 1 4 4 y1 1 1 1 ∞ y2 1 1 1 ∞ y3 1 1 1 1 y4 1 1 1,5 ∞ y5 1 1 1,5 ∞ F0 -2 2 -3 -0,5 2,5 0 0 0 0 0 0 -6 Базис y10 y11 y20 y21 y22 y 1 3 1 1 y1 1 y2 1 y20 1 y4 1 y5 1 F0 -2 2 0 -0,5 2,5 y 1 y1 1 y2 1 y3 -1 1 3 y4 1 y5 bi bi /aij 0 3 3 1 1 1 ∞ 1 ∞ 0 1,5 ∞ 1 1,5 ∞ 0 -3 Базис y10 y11 y20 y21 y22 y 3 1 1 y10 1 y2 1 y20 1 y4 1 y5 1 F0 2 0 -0,5 2,5 y 1 y1 -1 1 2 y2 1 y3 -1 1 3 y4 1 y5 bi bi /aij 0 2 2 1 ∞ 1 ∞ 1 ∞ 0 1,5 1,5 1 1,5 ∞ 0 -1 Базис y10 y11 y20 y21 y22 y 3 1 y10 1 y2 1 y20 1 y21 1 y5 1 F0 2 0 2,5 y 1 y1 -1 1 2 y2 1 y3 y4 y5 bi -1 -1 0 0,5 0 0 0 1 0 0 0 1 1 0 0 1 1 0 1,5 0 0 1 1,5 3 0,5 0 -0,25 y Квадратичное программирование Стр. 124 из 136 JI JIxy y II JJ y × y Оглавление В.М. Караулов Глава 7 Квадратичное программирование y II JJ В задаче нелинейного программирования условия КунаТаккера не позволяют построить алгоритм нахождения экстремума, но при некоторых условиях это возможно, в частности, в случае задачи квадратичного программирования. Задачей квадратичного программирования называется задача нелинейного программирования, в которой целевая функция квадратичная и вогнутая, а все ограничения — линейные. y Квадратичное программирование Стр. 125 из 136 JI JIxy y × y Оглавление 7.1 Задача квадратичного программирования 7.1 Задача квадратичного программирования y II JJ В матричном виде задача квадратичного программирования записывается так: максимизировать 1 2 F (X) = BT X + XT CX = n X bj xj + j=1 n m 1 XX cij xi xj 2 j=1 i=1 при ограничениях AX 6 A0 , n X X > 0, aj xj 6 ai0 , xj > 0, j=1 где  c11  .. C= . cn1 ... .. . ...  c1n ..  .  cnn — симметричная, отрицательно определенная матрица,    b1 a11  ..   .. B =  . ; A =  . bn am1 y ... .. . ...      a1n a10 x1 .. ; A =  .. ; X =  .. .  .   .  .  amn am0 xn y Заметим, что если C — отрицательно определенная матрица, то квадратичная форма XT CX вогнута (выпукла вверх). Следовательно, задача квадратичного программирования является задачей выпуклого программирования. Квадратичное программирование Стр. 126 из 136 JI JIxy × y Оглавление 7.2 Сведение задачи квадратичного программирования к задаче линейного . . . 7.2 Сведение задачи квадратичного программирования к задаче линейного программирования y II JJ Запишем функцию Лагранжа и условия Куна-Таккера. Заметим, что в силу квадратичности целевой функции и линейности ограничений условия Куна-Таккера являются линейными неравенствами за исключением условий дополняющей нежесткости. Систему ограничений представим в каноническом виде. Обозначим дополнительные переменные vj = −Lxj и wi = Lλi для j = 1, . . . , n и i = 1, . . . , m. Тогда ограничения в оптимизационной модели можно записать в еще одном виде: vj + Lxj ± zj = −Lj0 , wi − Lλi ± yi = Li0 , j = 1, . . . , n; i = 1, . . . , m, где Lj0 — свободный член в выражении частной производной Lxj функции Лагранжа по переменной xj ; Li0 = ai — свободный член в выражении частной производной Lλi функции Лагранжа по переменной λi — свободный член в i-ом ограничении. Знак при zj и yi определяется в соответствии со знаком свободного члена частной производной функции Лагранжа. В этих обозначениях на переменные накладываются также условия неотрицательности переменных и дополняющей n m P P нежесткости: vj > 0, wi > 0, vj xj = 0 и wi λi = 0. y j=1 i=1 y Первое базисное решение линейной системы обычно получается недопустимым. Поэтому необходимо ввести искусственные переменные и функцию штрафа. Далее может быть использован обычный симплексный алгоритм, но при переходе к очередному базису нужно проверять выполнимость условия дополняющей нежесткости. Квадратичное программирование Стр. 127 из 136 JI JIxy × y Оглавление 7.2 Сведение задачи квадратичного программирования к задаче линейного . . . Пример 7.1. рования: y II JJ Решить задачу квадратичного программи- F = 32x1 + 120x2 − 4x12 − 15x22 → max при ограничениях  2x1 + 5x2 6 20, 2x1 − x2 6 8, x > 0, x > 0. 1 2 Решение. Составим функцию Лагранжа: L(x1 , x2 , λ1 , λ2 ) = 32x1 + 120x2 − 4x12 − 15x22 + + λ1 (20 − 2x1 − 5x2 ) + λ2 (8 − 2x1 + x2 ). Условия Куна-Таккера имеют следующий вид: L0x1 = 32 − 8x1 − 2λ1 − 2λ2 6 0, L0x2 = 120 − 30x2 − 5λ1 + 2λ2 6 0, L0λ1 = 20 − 2x1 − 5x2 > 0, L0λ2 = 8 − 2x1 + x2 > 0, L0x1 x1 + L0x2 x2 = 0, L0λ1 λ1 + L0λ2 λ2 = 0, y x1 > 0, x2 > 0, λ1 > 0, Квадратичное программирование Стр. 128 из 136 λ2 > 0. JI JIxy y × y Оглавление 7.2 Сведение задачи квадратичного программирования к задаче линейного . . . y II JJ Согласно обозначениям, определенным выше, v1 = −L0x1 , v2 = −L0x2 , w1 = L0λ1 и w2 = L0λ2 . Для представления системы первых четырех ограничений Куна-Таккера в каноническом виде (перенесем свободные члены в правую часть, остальные — в левую) и введем искусственные переменные z1 > 0, z2 > 0 (чтобы знак перед переменной совпадал со знаком свободного члена): 8x1 + 2λ1 + 2λ2 − v1 + y1 = 32, 30x2 + 5λ1 − λ2 − v2 + y2 = 120, 2x1 + 5x2 + w1 = 20, 2x1 − x2 + w2 = 8, −v1 x1 − v2 x2 = 0, w1 λ1 + w2 λ2 = 0, x1 > 0, x2 > 0, λ1 > 0, λ2 > 0; v1 > 0, v2 > 0, w1 > 0, w2 > 0; y1 > 0, y2 > 0. Искусственные переменные должны быть выведены из системы, поэтому Z(y1 , y2 ) = −y1 − y2 → max . Получаем задачу линейного программирования, в которой оптимальное решение должно содержать базисные переменные, удовлетворяющие условию дополняющей нежесткости: −v1 x1 − v2 x2 = 0 и w1 λ1 + w2 λ2 = 0. Это означает, например, что при переходе к новому базисному решению не должно быть в базисе одновременно переменных x1 и v1 , x2 и v2 , λ1 и w1 , λ2 и w2 . y Квадратичное программирование Стр. 129 из 136 JI JIxy y × y Оглавление 7.2 Сведение задачи квадратичного программирования к задаче линейного . . . y II JJ На начальном (нулевом шаге) в качестве базисных переменных, как обычно, используются дополнительные переменные (если они входят в систему с тем же знаком, что и свободный член) и искусственные переменные. В нашем случае, это будут переменные y1 , y2 и w1 , w2 . Поэтому целевая функция должна быть представлена через небазисные (неосновные, или свободные) переменные. Выразим из первых двух уравнений (условий Куна-Таккера) переменные y1 , y2 : y1 = 32 − 8x1 − 2λ1 − 2λ2 + v1 , y2 = 120 − 30x2 − 5λ1 + λ2 + v2 . Подставим эти выражения в целевую функцию: Z = −152 + 8x1 + 30x2 + 7λ1 + 1λ1 − v1 − v2 . Дальнейшую реализацию данной задачи представим с помощью симплекс-таблиц 7.1–7.4. Таблица 7.1. Результаты квадратичного программирования. Шаг 0 y1 y2 w1 w2 Z y x1 x2 8 0 30 2 5 2 -1 -8 -30 λ1 2 5 -7 v1 λ2 2 -1 -1 v2 -1 1 w1 -1 1 1 w2 1 y1 y2 1 1 bi bi /aij 32 ∞ 120 4 20 4 8 -8 -152 y В таблице 7.1 фоном выделен столбец («разрешающий столбец»), содержащий переменную, которая будет вводиться в базис на следующем шаге. Также фоном выделена строка («разрешающая строка»), указывающая на переменную, которая будет выводятся из базиса на следующем шаге. Квадратичное программирование Стр. 130 из 136 JI JIxy × y y y y Оглавление 7.2 Сведение задачи квадратичного программирования к задаче линейного . . . II JJ Напоминаем, что • выбор разрешающего столбца определяется максимальным по модулю и отрицательным по значению коэффициентом целевой функции (в последней строке этот элемент выделен жирным шрифтом); • выбор разрешающей строки определяется минимальным неотрицательным отношением свободного члена (bi ) к соответствующему коэффициенту разрешающего столбца (в последнем столбце выделено жирным шрифтом); • на следующем шаге все коэффициенты симплекс-таблицы пересчитываются: элементы разрешающей строки делятся на разрешающий элемент (он находится на пересечении разрешающей строки и разрешающего столбца); остальные — пересчитываются по правилу прямоугольника. Данные расчеты удобно осуществлять в электронной таблице MS Excel. Например, на следующем шаге 1 при заполнении симплекс-таблицы 7.2 первый коэффициент целевой функции (−8) (он находится в левом нижнем углу таблицы 7.2) получается из соответствующих коэффициентов таблицы 7.1 по формуле −8 = −8 · 30 −300 · (−30) . Ввод формул нужно осуществлять через ссылки на соответствующие ячейки таблицы 7.1. Если при этом ячейка находится на разрешающей строке или на разрешающем столбце, необходимо делать ссылку абсолютной (фиксировать соответствующую строку или столбец, например, с помощью знака $). В частности, при ссылке на разрешающий элемент нужно фиксировать и номер строки, и номер столбца. После этого полученная формула может копироваться на все остальные ячейки таблицы 7.2, за исключением строки, которая была разрешающей на предыдущем шаге. Коэффициенты этой строки пересчитываются отдельно. Данные шаги повторяются до тех пор, пока среди коэффициентов целевой функции не останутся только нулевые и положительные (таблицы 7.2–7.4). Квадратичное программирование Стр. 131 из 136 JI JIxy × y Таблица 7.2. Результаты квадратичного программирования. Шаг 1 y1 x2 w1 w2 Z x1 x2 λ1 λ2 8 2 2 1 1/6 -1/30 2 0 -5/6 1/6 2 0 1/6 -1/30 -8 -2 -2 v1 v2 -1 0 -1/30 0 1/6 0 -1/30 1 w1 1 w2 1 y1 y2 1 0 1/30 0 -1/6 0 1/30 1 y II JJ Оглавление 7.2 Сведение задачи квадратичного программирования к задаче линейного . . . bi bi /aij 32 4 4 ∞ 0 +0 12 6 -32 Таблица 7.3. Результаты квадратичного программирования. Шаг 2 y1 x2 x1 w2 Z x1 x2 λ1 λ2 0 16/3 4/3 1 1/6 -1/30 1 0 -5/12 1/12 1 -1/5 0 -16/3 -4/3 v1 v2 w1 w2 -1 -2/3 -4 0 -1/30 0 1/12 1/2 0 -1/5 -1 1 1 2/3 4 y1 y2 bi bi /aij 1 2/3 32 6 0 1/30 4 24 0 -1/12 -0 0 1/5 12 12 0 1/3 -32 Таблица 7.4. Результаты квадратичного программирования. Шаг 3 x1 λ1 x2 x1 w2 Z y x2 1 λ1 1 λ2 v1 v2 w1 w2 y1 y2 bi 1 1/4 -3/16 -1/8 -3/4 0 3/16 1/8 6 0 -3/40 1/32 -1/80 1/8 0 -1/32 1/80 3 0 3/16 -5/64 1/32 3/16 0 5/64 -1/32 5/2 0 -9/20 3/16 -3/40 -1/4 1 -3/16 3/40 6 1 1 y В таблице 7.2 разрешающее отношение (в последнем столбце) равно +0. Знак «+» означает, что данное отношение нужно учитывать (учитываются только неотрицательные отношения). Так как отношение равно 0, то при вводе в базис соответствующей переменной (x1 ) значение целевой функции не меняется. Это видно по значениям свободных членов последних строк таблиц 7.2 и 7.3. Квадратичное программирование Стр. 132 из 136 JI JIxy × y Оглавление 7.2 Сведение задачи квадратичного программирования к задаче линейного . . . y II JJ В последней строке таблице 7.4 все коэффициенты (целевой функции) неотрицательные. Следовательно, полученное значение целевой функции Z = 0 улучшить нельзя и полученное базисное решение является оптимальным: λ∗1 = 6, x2∗ = 3, x1∗ = 2,5, w2∗ = 6, а остальные переменные обращаются в нуль. Тогда максимальное значение исходной целевой функции составляет: F (X ∗ ) = 32 · 2,5 + 120 · 3 − 4 · 2,52 − 15 · 32 = 280. Полученные результаты согласуются с результатами, которые можно получить, используя решения задачи нелинейного программирования надстройку «Поиск решения» MS Excel. При этом реализация квадратичного симплексного программирования позволяет получить всю информацию, выводимые в отчетах по результатам (рис. 7.1) и по устойчивости (рис. 7.1): • оптимальные значения первоначальных переменных x1∗ = 2,5 и x2∗ = 3 представлены в отчете по результатам в таблице «Ячейки переменных» (столбец «Окончательное значение»); • оптимальные значения дополнительных (для xj ) переменных v1∗ = 0 и v2∗ = 0 представлены в отчете по результатам в таблице «Ограничения» (столбец «Допуск»); • оптимальные значения множителей Лагранжа λ∗1 = 6 и λ∗2 = 0 представлены в отчете по устойчивости в таблице «Ограничения» (столбец «Лагранжа Множитель»); • оптимальные значения дополнительных (для λi ) переменных w1∗ = 0 и w2∗ = 6 представлены в отчете по устойчивости в таблице «Ячейки переменных» (столбец «Приведенн. Градиент»); • оптимальное (максимальное) значение целевой функции F (X ∗ ) = 280 представлено в отчете по результатам в таблице «Ячейка целевой функции (Максимум)» (столбец «Окончательное значение»). y Квадратичное программирование Стр. 133 из 136 JI JIxy y × y y II JJ Оглавление 7.2 Оглавление Microsoft Excel 15.0 Отчет о результатах Лист: [Книга1]Лист1 Отчет создан: 15.05.2017 14:03:09 Результат: Решение найдено. Все ограничения и условия оптимальности выполнены. Модуль поиска решения Модуль: Поиск решения нелинейных задач методом ОПГ Время решения: 0,094 секунд. Число итераций: 3 Число подзадач: 0 Параметры поиска решения Максимальное время Без пределов, Число итераций Без пределов, Precision 0,000001, Использовать авт Сходимость 0,0001, Размер совокупности 100, Случайное начальное значение 0, Правые производные, О Максимальное число подзадач Без пределов, Максимальное число целочисленных решений Без предел Ячейка целевой функции (Максимум) Ячейка Имя Исходное значение $F$2 Окончательное значение 280 Ячейки переменных Ячейка Имя Исходное значение $B$1 $C$1 Окончательное значение Целочисленное 2,500000008 Продолжить 2,999999997 Продолжить Ограничения Ячейка Имя $D$3 $D$4 Значение ячейки Формула 20 $D$3<=$E$3 2,000000019 $D$4<=$E$4 Состояние Привязка Без привязки Допуск 5,999999981 Рис. 7.1. Отчет по результатам «Поиска решений» MS Excel Microsoft Excel 15.0 Отчет об устойчивости Лист: [Книга1]Лист1 Отчет создан: 15.05.2017 14:03:09 y Ячейки переменных Окончательное Приведенн. Ячейка Имя Значение Градиент $B$1 2,500000008 $C$1 2,999999997 Ограничения Ячейка Имя $D$3 $D$4 Окончательное Лагранжа Значение Множитель 20 5,999988174 2,000000019 Рис. 7.2. Отчет по устойчивости «Поиска решений» MS Excel Квадратичное программирование Стр. 134 из 136 JI JIxy y × y y II JJ Оглавление 7.2 Оглавление Оглавление 1 Введение 2 3 4 2 Модели линейного программирования 5 2.1 Общая постановка задачи линейного программирования 6 Пример 2.1. 8 2.2 Графический метод решения задачи линейного . . . 11 Основные выводы из графического решения задачи . . . 16 2.3 Симплексный метод решения задачи линейного . . . 17 Пример 2.2. 18 2.4 Метод больших штрафов (М-метод) 25 Пример 2.3. 27 2.5 Решение задачи оптимизации с помощью «Поиска решения» 33 Пример 2.4. 34 3 Двойственность 38 3.1 Экономическая интерпретация прямой и двойственной . . . 39 Представление прямой и двойственной задач линейного . . . 42 3.1.1 Первая теорема двойственности 43 Первая (основная) теорема двойственности. 44 3.1.2 Вторая теорема двойственности 45 Вторая теорема двойственности. 47 Замечание. 49 3.2 Анализ моделей на чувствительность 50 3.2.1 Объективно обусловленные оценки и их смысл 51 Третья теорема двойственности. 52 3.2.2 Анализ устойчивости 53 Малые изменения коэффициентов целевой функции 56 3.3 Анализ дополнительно закупаемых ресурсов 57 Пример 3.1. 58 1.1 Основные понятия исследования операций Примеры управленческих задач, для которых . . . y Квадратичное программирование Стр. 135 из 136 JI JIxy y × y 3.4 Отчеты «Поиска решения» Excel 4 Модели сетевого планирования и управления 4.1 Сетевая модель и ее основные элементы 4.2 Построение сетевых графиков 4.2.1 Правила построения сетевых графиков 4.2.2 Упорядочение сетевого графика Пример 4.1. Временной сетевой график. 4.2.3 Критический путь Линейная диаграмма проекта. 4.3 Временные параметры сетевых графиков Временные параметры событий. Временные параметры работ. Резерв времени пути. Пример 4.2. 4.4 Оптимизация сетевого графика Коэффициент напряженности работы. Оптимизация сетевого графика 5 Классические методы оптимизации 5.0.1 Метод множителей Лагранжа Алгоритм нахождения условного экстремума 5.0.2 Неотрицательность переменных 5.0.3 Условия Куна-Таккера Алгоритм выделения условий Куна-Таккера 6 Выпуклое программирование 6.1 Задача выпуклого программирования 6.2 Аппроксимация задачи выпуклого программирования . . . 6.2.1 Метод средневзвешенных Пример 6.1. Способ 1 (метод подстановки). Способ 2 (метод искусственных переменных). 6.2.2 Аппроксимации функции путём увеличения числа . . . Пример 6.2. y 7 Квадратичное программирование 7.1 Задача квадратичного программирования 7.2 Сведение задачи квадратичного программирования к . . . Пример 7.1. Квадратичное программирование Стр. 136 из 136 y II JJ 66 Оглавление 7.2 Оглавление JI JIxy 69 70 72 73 74 75 78 80 81 82 83 85 88 89 93 94 95 96 97 98 99 100 102 105 106 108 109 110 113 116 119 122 125 126 127 128 y ×