Общая задача линейного программирования

2. ОБЩАЯ ЗАДАЧА ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ Цель раздела: формирование представления о математической формализации задачи линейного программирования, методе её решения и практическом применении 2.1. Постановка общей задачи линейного программирования. Математическая формализация (стандартная, смешанная, каноническая) Само название модели говорит о том, эта задача линейного характера, т.е.параметры управления, посредством которых, записаны и ограничения и целевая функция, в первой степени. Что же означает слово «общая»? Общей её делает возможность описывать всё многообразие условий протекания детерминированных процессов, если они подчинены линейным зависимостям. А таких задач в практической деятельности множество. Поэтому модель общей задачи линейного программирования (ОЗЛП) нашла широкое применение в хозяйствовании и в том числе в транспортной сфере. Например. Судоходная компания предполагает использовать 3 типа судов для организации перевозок на 4-х направлениях. Объёмы перевозок на всех направлениях заданы и обязательны к освоению. По каждому судну известны: бюджет времени, продолжительность рейсов, загрузка и эксплуатационные затраты за один рейс на каждом направлении. Требуется так организовать работу судов, т.е. так распределить их бюджет времени, чтобы при полном выполнении плановых обязательств суммарные эксплуатационные затраты на перевозки были минимальны. В условиях этой достаточно простой задачи помимо ресурсов (бюджет времени судов), потребностей (плановое количество перевозимого груза) и ценовых показателей заданы ещё продолжительность рейсов и загрузка судна. Это обстоятельство, насыщающее данную модель дополнительной входной информацией, отличает её от транспортной задачи, делает общей задачей линейного программирования (ОЗЛП) относительно частного случая, каковым и является модель «Транспортная задача» (ТЗ). Математическая формализация ⩝i: 1, 2, 3,………,n: ⪖0 + + ………+ ⪕ + +……… + ⪕ ………………………………….. + +……… + ⪕ Z =∑ ⇒ max Как видно из сравнения вида моделей ТЗ и ОЗЛП, общим для них помимо подчинённости линейным зависимостям является то, что число переменных не совпадает с числом линейно независимых уравнений (m с ) хотя бы за единицу производственного реквизита , то вывод напрашивается сам собой. Базис Б1 неудачен, его требуется изменить путём введения в него вектора Aj. Если при проверке всех векторов, не вошедших в первый базис, обнаружится несколько претендентов на включение в новый базис, то для изменения базиса, а значит, для улучшения решения. выбирается вектор с наихудшим результатом проверки. Под наихудшим результатом понимается наибольшая по модулю отрицательная величина j= - . ЗАМЕЧАНИЕ. Следует особо отметить, что введённое понятие «косвенный» эффект общем смысле может трактоваться двояко в зависимости от этапа процесса. На стадии процедуры последовательного решения, т.е. на стадии очередной проверки на оптимальность полученного на настоящий момент решения, косвенный эффект по некоторому небазисному вектору естественно связать с его невключением в данный базис, и значит, в решение, имеющееся на этом конкретном шаге алгоритма. После получения окончательного результата - оптимального решения- может последовать процедура (желательная, но не обязательная) анализа данного оптимального решения на чувствительность к изменениям входной информации (по ценовым, технологическим коэффициентам, ресурсам и по дополнительным управляющим воздействиям). По существу этой процедуры косвенный эффект трактуется как возможно предстоящее включение небазисного вектора в новый план при возможном изменении входной информации. В обоих случаях косвенный эффект влечёт появление оценочных показателей эффективности решения. Следующий этап решения - улучшение в случае необходимости. В чём оно соcтоит? В том, чтобы прежде всего выяснить какой вектор следует вывести из базиса Б1 для замены его другим вектором, «избранным» для улучшения на предыдущем этапе. Для этого почленно делят элементы вектора B на элементы избранного для улучшения вектора Аj, имеющие смысл «технологических» ( см.п.2.1) коэффициентов задачи ( например, производительность и т.п. ). В данной задаче будут получены 3 отношения. Тот базисный вектор, для которого это отношение является наименьшим среди всех базисных векторов, выводится из базиса. Такой подход можно трактовать , как «технологическую» выбраковку базисных векторов. Рассчитанные отношения отражают «степень участия» базисных векторов в рассматриваемой модели с точки зрения описываемой ею задачи того или иного производственного процесса. Если у какого-либо из векторов « степень участия» меньше, чем у других, он подлежит выводу из базиса. На его место встанет отобранный на предыдущем этапе по «ценовому» принципу вектор Аj. Таким образом, в новом базисе процесс продолжается по вышеописанной процедуре, начиная с разложения всех векторов по векторам базиса до получения оптимального решения, т.е. такого, при котором отсутствуют отрицательные оценки эффективности по всем векторам. ЗАМЕЧАНИЕ. Отсутствие отрицательных оценок косвенного эффекта касается только задач с целевой функцией, стремящейся к максимуму. Для задач с целевой функцией, устремлённой к минимуму, критерий оптимальности решения имеет противоположную направленность – отсутствие положительных оценок косвенного эффекта. Сущность алгоритм симплекс-метода для обоих типов задач едина. Алгоритм симплекс- метода удобнее всего осуществлять в табличной форме. cj ci 1 2 А1 Аj А2 Б1 B А3 А4 =4 = 3 =1 А3 = А4 =1 8 А5 =0 1 =0 А5 =5 Zj j= = zj - cj 1 z1 = 0 z2 = Δ = -1 Δ = 1 z3 = z4 = z5 = Δ = Δ = Δ = В таблице в строке zj записываются значения целевой функции z ( в столбце B) и косвенные эффекты применительно к каждому вектору Аj, рассчитанные по формуле = ∑ Б . В столбце, соответствующем вектору ограничений B, расположены базисные переменных, все небазисные переменные равны 0. Обычно в таблице записываются только численные значения переменных. Здесь приведены их обозначения для лучшего понимания. Студентам предлагается продолжить решение. 2.3. Метод Жордановых исключений для реализации симплекс-метода Содержание симплекс –метода с его понятийными и теоретическими положениями изложено в предыдущем параграфе. В текущем параграфе приводится упрощённая схема вычислительной процедуры, называемая Жордановыми исключениями. Иными словами для понимания сущности процесса более приемлем материал п.2.2. Для его численной реализации удобно воспользоваться рекомендациями п.2.3. Воспользуемся уже известным примером, переименовав переменные. Основные: x и y назовём , , ; дополнительные - , , . x ⪕ 4; y ⪕ 3; x + 2y ⪕ 5; z = x + 2y ⇒ max; тогда ⇩⇩⇩ + = 4; + = 3; (7) +2 + = 5; Z= + 2 +0 +0 + 0 ⇒ max. Выразим уравнения относительно дополнительных переменных: =+ 4; =+3; (8) = - 2 +5. Z= + 2 +0 +0 + 0 ⇒ max. Решение осуществляется в табличной форме. ТаблицаБ1 ТаблицаБ2 ** − ** Z 1 4 1* 4 1 3 -0,5 0,5 1 2* 5 0,5 0,5 0,5 2,5 -1 -2 1 5 X1 = (0; 0; 4; 3; 5;) Z = 0; решение опорное. Z X2 = (0; 2,5; 4; 0,5; 0) Z = 5; решение оптимальное. 9 Форма таблицы компактнее, чем в классическом методе. В первых 3-х строках обозначены не векторы базиса, а базисные переменные. В последней строке таблицы Б1 помещены коэффициенты при переменных в целевой функции (см.уравнения (8)). В столбцах - небазисные переменные. Численные значения в столбцах - коэффициенты при обозначенных переменных из системы уравнений (8). В столбце ** размещены свободные члены уравнений (вектор ограничений B). Таким образом, таблица Б1 представляет собой исходные данные задачи. Алгоритм решения заключается в последовательности однотипных шагов при соблюдении определённых правил чисто визуального характера и потому называющимися признаками. Прежде всего условимся называть внутреннюю часть таблицы (исключая строку Z и столбец**) основным блоком. Признак опорности решения (теорема). Если на каком-то шаге Жордановых исключений оказалось, что все элементы заключительного столбца ** неотрицательны , а левом столбце имеется полный набор базисных элементов, то, полагая верхние переменные равными 0, а боковые переменные равными соответствующим элементам заключительного столбца **, получим некоторое опорное решение. В данном случае такое решение X1 присутствует в таблице Б1. При этом решении значение целевой функции равно 0, что и записано в правой угловой клетке. Замечание. При реализации метода Жордановых исключений на первом шагу решения значение целевой функции для всех типов задач равно 0. Признак оптимальности решения (теорема). Если на каком-то шаге Жордановых исключений выполнен признак опорности и при этом все элементы заключительной строки Z неотрицательны, то это значит, что достигнут максимум целевой функции. Если на каком-то шаге Жордановых исключений выполнен признак опорности и при этом все элементы заключительной строки Z неположительны, то это значит, что достигнут минимум целевой функции. Признак неограниченности решения (теорема). Если на каком-то шаге Жордановых исключений в столбце над отрицательным элементом заключительной строки все элементы оказались неположительными, то целевая функция может принимать сколь угодно большие значения (max Z = ∞). Признак противоречивости.1). Если в строке заключительный элемент отрицательный и в ней нет ни одного отрицательного элемента, то задача несовместна. 2). Если в 0-строке в основном блоке нет ни одного положительного элемента, то система несовместна. Примечание: Пояснение к п. 2 будет приведено позже в отдельном подразделе этой темы. Проанализируем решение, представленное в таблице Б1. По признаку опорности оно является опорным, но не удовлетворяет признаку оптимальности. Также оно не соответствует признакам противоречивости и несовместности системы. Итак, опорное решение X1 нуждается в улучшении. Правило улучшения опорного решения Очевидно, что улучшение будет состоять в изменении состава базисных элементов ( в соответствии с принципами симплекс- метода, изложенными в п.2.2). Последовательность действий следующая: - прежде всего ищем в заключительной строке таблицы Б1 наихудшую (большую по модулю) «ценовую» характеристику записанного в таблице решения. В данном случае это значение «-2», соответствующее небазисной переменной . Значит, эта переменная должна быть введена в базис, т.е. стать базисной. Назовём избранный для улучшения столбец ведущим; - для отбора базисной переменной, подлежащей выводу из базиса Б1 делим каждый элемент заключительного столбца ** на соответствующий положительный элемент 10 столбца . В данном случае получим отношения: = 3 и = 2,5. Меньшему отношению соответствует строка базисной переменной . Она, называемая ведущей строкой, подлежит выводу из базиса Б1. На пересечении ведущего столбца и ведущей строки обозначаем ведущий элемент знаком *; - дальнейшее преобразование таблицы Б1 в таблицу Б2 осуществляется посредством установленного ведущего элемента. Преобразование : - строится таблица Б2 такого же формата, как и таблица Б1, обозначаются базисные и небазисные переменные. Состав переменных изменяется в соответствии с ведущим элементом: на месте переменной в базисе появляется переменная , а её место среди небазисных переменных занимает . Ведущая строка и ведущий столбец первой таблицы становятся ведущим столбцом и ведущей строкой второй таблицы. Остальные переменные остаются на своих местах; далее следует заполнить новую таблицу Б2 численными значениями; - заполнение начинается с ведущего элемента. Ведущий элемент новой таблицы на пересечении ведущих столбца и строки принимает значение, обратное величине ведущего элемента таблицы Б1,т.е. равное 1/ , где - значение ведущего элемента таблицы Б1; - остальные элементы ведущей строки делятся на ведущий элемент ; - остальные элементы ведущего столбца делятся на ведущий элемент и меняют знак; - все прочие элементы таблицы рассчитываются по рекуррентной формуле: = , где - преобразуемый элемент предыдущей таблицы. Эта формула называется правилом прямоугольника. В таблице намечается прямоугольник, у которого на диагонали преобразуемый элемент и ведущий, вторая диагональ соединяет 2 сомножителя формулы. Прямоугольник предоставляет удобство расчётной процедуре. Доказано, что вычисление по формуле адекватно разложению по векторам базиса (п.2.2) . ……. …. . . . . …… ⫶ ⤢ ⫶ ⫶ ⤡ ⫶ …….. ……… ……….. Таким образом заполняется таблица Б2.Записанное в ней решение соответствует признакам опорности и оптимальности решения. Это решение определяет вершину многоугольника А (см. п.2.2). Анализируя решение, можно понять, что имеет место возможность альтернативного решения поскольку в заключительной строке присутствует оценка, равная 0. Приняв столбец в качестве ведущего, и продолжив процедуру расчёта, не составит труда найти решение, находящееся в вершине многоугольника B. ЗАМЕЧАНИЕ (теорема). При переходе от таблицы к таблице по правилу улучшения опорность решения не нарушается. Из этого замечания однозначно следует, что если в процессе вычислений после уже полученного опорного решения на каком-то следующем этапе появилось решение не опорное, то вы совершили ошибку. После всего изложенного выше остаётся ещё один вопрос - как быть, если в задаче кроме неравенств имеются отдельные ограничения- равенства или вообще одни только равенства? Ответ один – общность теоретических положений не нарушается. Точно так же, как в неравенство вводится дополнительная неотрицательная переменная, например, в третье неравенство системы (7), в случае, если бы это ограничение было равенством, в него бы добавилась дополнительная переменная, равная 0 (вместо ): +2 + 0= 5; 0 = - 2 +5. Так ограничение-равенство становится 0-строкой в таблице.( 0-строки уже упоминались при описании признака противоречивости решения). Последовательность действий при наличии ограничений равенств: 11 1. Просматривается 0- строка на наличие признака противоречивости, а именно, если среди элементов строки в основном блоке нет ни одного положительного, то система несовместна. В случае совместности системы уравнений ход рассуждений следующий: наличие 0-строки указывает на неполный состав базисных элементов в таблице и поэтому никакое записанное в ней решение не может быть опорным. Значит, следует устранить 0-строку, чтобы иметь возможность получить опорное решение . Для этого: 2. Берём в качестве ведущего какой-нибудь столбец с положительным элементом в просматриваемой строке и отмечаем в этом столбце все положительные элементы. 3. Делим на эти элементы соответствующие элементы столбца свободных членов (**), находим наименьшее из отношений, элемент, соответствующий наименьшему отношению, становится ведущим, по которому и осуществляется пересчёт таблицы, как это было показано выше. Не всегда удаётся сразу за 1 шаг удалить 0строку, это не должно останавливать процесс решения, оно должно быть продолжено по той же схеме до достижения желаемого результата – устранения 0строки. С удалением 0-строки в следующей таблице число столбцов уменьшится, так как 0 не перейдёт в новую таблицу в качестве столбца. После избавления от 0 строк следует искать опорное решение. Поиск опорного решения начинается с проверки записанного в таблице решения по признаку опорности. Если выясняется, что решение не опорное, т.е. в столбце свободных членов есть хотя бы один отрицательный элемент, то задача проверяется по признаку противоречивости - если в строке, содержащей этот элемент, нет ни одного отрицательного элемента, то система несовместна. Если система совместна (есть один или несколько отрицательных элементов),то столбец с каким-нибудь из отрицательных элементов выбирается в качестве ведущего. Составляются неотрицательные отношения свободных членов к элементам этого столбца. Строка, в которой отношение наименьшее, выбирается в качестве ведущей. На пересечении ведущих строки и столбца находится ведущий элемент, по которому и призводится пересчёт таблицы, и т. д. до получения опорного плана. Таким образом, алгоритм решения представляет собой ряд однотипных простых операций, имеющих целью отыскание оптимального решения. Студентам предлагается для усвоения материала самостоятельно проделать работу: 1. закончить задачу, представленную в таблицах Б1 и Б2 - найти альтернативное решение для вершины В. 2. решить задачи: а). z = 3x1 + 4x2 + 3x3 + x4 ⇒ max 2x1 + 4x2 + 8x4 ⪕ 12 7x1 + 2x2 + 2x3 + 6x4 ⪕ 8 5x1 + 8x2 + 4x3 + 3x4 ⪕ 48 б). z = x1 + 2x2 - x3 + x4 ⇒ max x1 + x2 - 2x3 + 3x4 = 1 2x1 - x2 - x3 + 3x4 = 2 2.4. Проблема двойственности в задачах линейного программирования. Принцип двойственности заключается в том, что с каждой задачей линейного программирования (ЛП) связывается другая задача ЛП, решение которой определяет также оптимальный план исходной задачи. Рассмотрим основные положения принципа двойственности для случая стандартной формы на примере задачи производственного планирования. Предприятие выпускает однородную продукцию n технологическими способами (обозначим j = 1,2,3,….,n). Располагает m ресурсами (обозначим I = 1,2,3,….1,m). Доход 12 от выпуска одного изделия, выполненного по способу j обозначим Сj. Примем в качестве параметра управления количество изделий, выпускаемых j-ым способом Xj. Тогда общий доход Z = C1 X1 + C2 X2 +………..+Cn Xn . Естественно целью планирования производства поставить max Z. Расходы ресурса I для выпуска изделия по способу j обозначим aij. ….. . ……. . ……. . - матрица технологических коэффициентов. Пусть запас i-ого ресурса составляет bi единиц. В таком случае мы должны подчинить план следующим ограничениям: ⩝j = 1,2,……, n; Xj ⪖ 0; a11X1 +a12X2 + …… + a1n Xn ⪕ b1; a21X1 +a22X2 + …… + a2n Xn ⪕ b2 ……………………………………………… am1X1 +am2X2 + …… + amn Xn ⪕ bm; Z = C1 X1 + C2 X2 +………..+Cn Xn ⇒ max. Для построения двойственно-сопряжённой задачи представим следующую ситуацию. Пусть некоторая организация предлагает предприятию продать весь запас ресурсов i: 1,2,…, m. Какие цены следует установить за единицу каждого из этих ресурсов? Обозначим эти цены: Y1, Y2,…….,Ym. Тогда набор ресурсов, затрачиваемых при выпуске изделия по способу j, будет оценен: a1j Y1 + a2j Y2 +…………+amjYm ⪖ Cj и так по каждому способу j; 1,2,…,n, а именно: a11 Y1 + a21 Y2 +…………+am1Ym ⪖ C1; a12 Y1 + a22 Y2 +…………+am2Ym ⪖ C2; …………………………………………………………… a1n Y1 + a2n Y2 +…………+amnYm ⪖ Cn. Y1 ⪖ 0; Y2 ⪖ 0; …………, Ym ⪖ 0. Чтобы соблюсти такие неравенства, можно просто назначить высокие цены, но с этим покупатель не согласится. Поэтому: Z′ = b1Y1 + b2Y2 + …+ bmYm ⇒ min Соответствия между задачами: 1). Исходная задача устремлена к максимуму, сопряжённая – к минимуму. 2). Направленность ограничений исходной задачи ⪕, сопряжённой задачи ⪖. 3). Коэффициенты при переменных в целевой функции исходной задачи являются правыми частями ограничений сопряжённой задачи. Правые части ограничений исходной задачи являются коэффициентами при переменных в целевой функции сопряжённой задачи. 4). Матрица технологических коэффициентов сопряжённой задачи транспонирована относительно матрицы коэффициентов исходной задачи. Задачи двойственной пары равноправны в том смысле, что исходной может служить любая из них. Иными словами, двойственная задача к двойственной есть исходная. Примеры. a). Z =5x1 + x2 ⇒ min x1 - x2 ⪕ 2 x1 - 3x2 ⪕ 3 - исходная задача допустима. x1 ⪖ 0; x2 ⪖ 0 б). Z′ = 2y1 + 3y2 ⇒ max y1 + y2 ⪖5 -y1 - 3y2 ⪖ 1 - двойственная задача недопустима 13 y1 ⪖ 0; y2 ⪖ 0 Приведенный пример доказывает, что записать двойственную задачу можно всегда, но не всегда она имеет аналитическое решение, так же, как и наоборот – исходная задача может быть недопустима, а двойственная допустима. Каков практический смысл рассмотрения двойственно-сопряжённой пары задач? Ответ на этот вопрос дают теоретические исследования, сформулированные в теоремах двойственности. Лемма. Если обе задачи двойственно-сопряжённой пары допустимы, то для любого плана исходной задачи значение целевой функции (т.е. максимизируемой ) не превосходит значения целевой функции (минимизируемой ) сопряжённой задачи для любого из планов последней. Экономический смысл . Каков бы ни был производственный план и каков бы ни был план оценок производственных ресурсов, общая стоимость последних не будет оценена ниже, чем доход от продукции, который можно получить по любому из производственных планов. (Именно такой позиции будет придерживаться предприятие, если ему предложат оценить свой запас производственных ресурсов). Теорема 1. а). Если обе задачи двойственно-сопряжённой пары допустимы, то обе они также и разрешимы (т.е. обе имеют оптимальные планы ), и притом оптимальные значения целевых функций этих задач совпадают: Zmax = Z′min. б). Если одна из задач двойственно-сопряжённой пары недопустима, то другая задача либо также недопустима, либо её целевая функция не ограничена. Экономический смысл. Оптимальным планом оценок производственных ресурсов может быть только такой план, при котором общая стоимость их запасов равна доходу от той продукции, которую можно получить при оптимальном производственном плане. Совпадение значений целевых функций для каких-то планов исходной и сопряжённой задач свидетельствует об их оптимальности ( что вытекает из леммы ). Теорема 2. Для того, чтобы два плана двойственной пары задач были оптимальными, необходимо и достаточно, чтобы для этих планов никакие два соответствующие ограничения не обращались одновременно в строгие неравенства, т.е. чтобы при обращении одного из ограничений в строгое неравенство соответствующее ему ограничение обращалось в равенство. Поясним это, анализируя системы ограничений двойственно-сопряжённой пары задач. Исходная задача Двойственная задача 1. 2. ⫶ m. 1. 2. n. а11X1 + a12X2 +… + a11Xn ⪕ b1 a21X1 + a22X2 + … + a2nXn ⪕ b2 1. a11 Y1 + a21 Y2 +…+ am1Ym ⪖ C1 2. a12 Y1 + a22 Y2 +....+ am2Ym ⪖ C2 ………………………………….. ⫶ ……………………………………………… am1X1 + am2X2 + …+ amnXn ⪕bm n. a1n Y1 + a2n Y2 +…+ amnYm ⪖ Cn X1 ⪖ 0 1. Y1 ⪖ 0 X2 ⪖ 0 2. Y2 ⪖0 …………………….. Xn ⪖ 0 m. ……………………… Ym ⪖ 0 Как понимать значение словосочетания «соответствующие ограничения»? Глядя на форму модели исходной задачи, видим ровно m ограничений , включающих технологические коэффициенты. Столько же, а именно, m ограничений, отражающих неотрицательность переменных, в двойственной задаче. Эти 2 группы ограничений, каждая из которых содержит m неравенств, и называются «соответствующими». Аналогично «соответствующими» являются 2 группы ограничений в составе n неравенств. Исходя из этих понятий, рассмотрим экономический смысл теоремы. 14 Пусть для какого –то оптимального плана X* исходной задачи «к»-ое ограничение первой группы обращается в строгое неравенство: ак1X1* + aк2X2* +… + aknXn* < bк . Это означает, что «к» -ый производственный ресурс имеется в избытке в сравнении с потребностью в нём при реализации оптимального плана X*. На основании 2-ой теоремы двойственности «к»-ое ограничение второй группы в сопряжённой задаче должно обратиться в равенство для оптимального плана Y*, т.е. Yк*=0, а это значит, что «к» -ый производственный ресурс получает нулевую оценку. В этом отражается избыточность запаса «к» - ого ресурса для осуществления оптимального производственного плана, некоторое уменьшение запаса «к» ого ресурса не сорвёт реализации оптимального плана. Пусть теперь «s»-ое ограничение первой группы сопряжённой задачи для её оптимального плана Y* обращается в строгое неравенство: a1s Y1* + a2s Y2 * +… + amsYm* > Cs. Это означает, что оценка набора производственных ресурсов, необходимых для выпуска одного изделия по «s» -ому технологическому способу, больше, чем доход от получаемого по этому способу изделия. Значит, «s» -ый технологический способ не выгоден, и его включать в оптимальный производственный план не следует, т.е. должно быть Xs*=0 в точном соответствии со 2-ой теоремой двойственности. Всё изложенное выше относилось к случаю исходной задачи в стандартной форме. Необходимое дополнение для случая нестандартной формы исходной задачи: от двойственных переменных, соответствующих ограничениям-равенствам, не требуется неотрицательность (они могут иметь любой знак). Следствием теорем 1 и 2 является двойственный алгоритм. Сущность его состоит в возможности, решив одну из задач двойственно-сопряжённой пары, записать оптимальное решение другой задачи, не решая её. Убедимся в этом на примере. Исходная задача: z = 3x1 + 4x2 + 3x3 + x4 ⇒ max 2x1 + 4x2 + 8x4 ⪕ 12 7x1 + 2x2 + 2x3 + 6x4 ⪕ 8 5x1 + 8x2 + 4x3 + 3x4 ⪕ 48 x1, x2, x3, x4 ⪖ 0 Т1 - x1 - x2 - x3 - x4 ** y1 2 4 * 0 8 12 y2 7 2 2 6 8 y3 5 8 4 3 48 z -3 -4 -3 -1 0 y1 = -2x1 -4x2 -0x3 -8x4 +12 y2 = -7x1 -2x2 -2x3 -6x4 + 8 y3 = -5x1 -8x2 -4x3 -3x4 + 48 Т2 ЗА ПО ЛН ИТ Ь** Т3 -x1 x2 ½ x3 3 y3 -11 z 8 Xопт = (0; -y1 -y2 -x4 ** 1/4 0 2 3 -1/4 1/2 1 1 -1 -2 -17 20 1/4 3/2 10 15 3; 1; 0; 0; 0; 20); z = 15 15 │ │ │ │ │ │ │ x1 x2 x3 x4 y1 y2 y3 Сопряжённая задача: z′ = 12u1 + 8u2 + 48u3 ⇒ min 2u1 +7u2 +5u3 ⪖ 3 v1 = 2u1 +7u2 + 5u3 - 3 4u1 +2u2 +8u3 ⪖ 4 v2 = 4u1 +2u2 +8u3 - 4 0u1 +2u2 +4u3 ⪖ 3 v3 = 0u1 +2u2 +4u3 - 3 8u1 +6u2 +3u3 ⪖ 1 v4 = 8u1 +6u2 +3u3 - 1 u1, u2, u3 ⪖ 0 Соответствие переменных исходной и сопряжённой задач: Исходная задача Основные переменные Дополнительные переменные x1 x2 x3 x4 y1 y2 y3 ↕ ↕ ↕ ↕ ↕ ↕ ↕ Сопряжённая задача v1 v2 v3 v4 u1 u2 u3 Дополнительные переменные Основные переменные По теореме 2: при x1 = 0, соответствующая переменная v1 > 0 и в силу транспонированности матрицы технологических коэффициентов сопряжённой задачи v1= 8; при x2 = 3, соответствующая переменная v2 = 0, и.т.д. Таблица с оптимальным решением сопряжённой задачи будет такой: ТДС - v2 - v3 - u3 ** v1 -1/2 -3 11 8 u1 -1/4 ¼ 1 1/4 u2 -1/2 2 3/2 v4 -2 -3 17 10 z -3 -1 -20 15 По теореме 1 значение целевой функции сопряжённой задачи равно значению целевой функции исходной задачи, в данном случае z = 15. Реализация принципа двойственности помогает не только более глубоко и всесторонне исследовать тот или иной производственный процесс, но и может способствовать быстро реагировать на запросы оперативной обстановки посредством создания системы двусторонних оценок решения на отдельных его этапах с учётом сближения значений целевых функций отдельных задач (теорема1). Кроме того двойственные переменные используются при анализе моделей линейного программирования на чувствительность к влиянию изменения входной информации. 2.5. Анализ моделей линейного программирования на чувствительность. Модели линейного программирования в большей своей части отражают аспект планирования человеческой деятельности на достаточно отдалённую временную перспективу. Естественно, что входные данные могут изменяться в реальной производственной практике и сиюминутно, и тем более за время продолжительного периода времени. В такой случае модель при изменении входной информации должна быть подвергнута пересчёту. Однако в оперативном режиме это не всегда возможно. Например, надо срочно ответить на внезапно возникший производственный вопрос по телефону или во время внутрипроизводственного совещания или переговоров любого уровня. Представляется целесообразным иметь некоторую заготовку для подобных ситуаций. Такую возможность предоставляет анализ оптимального решения модели на чувствительность к внешним воздействиям. Это означает, что можно установить, в какой степени влияет то или иное воздействие на «стратегию» и «тактику» функционирования 16 модели. Что понимать под термином «стратегия» применительно к модели? Для разных моделей, которые могут отличаться в деталях, общим является одно - стратегию отражает состав базисных переменных (т.е. ненулевых переменных и, следовательно, реально включённых в план работы). Так, оптимальным планом установлена необходимость задействования продукции определённых типов (судов или чего-то другого).Это необходимость выражается в присутствии соответствующих переменных в совокупности базисных переменных ( в левом крайнем столбце Жордановой таблицы) . Это и есть «стратегия», т.е. решение использовать для успешной деятельности конкретные поименованные реквизиты производства, что можно расценивать как «качественную» сторону вопроса. «Количественный» аспект составляет «тактику», отвечая на вопрос о том, сколько надо использовать отобранных стратегией реквизитов судов , оборудования, материалов и т.п. Очевидно, что в ходе пересчёта модели (из-за изменения входных параметров) результат изменится. Но как? Изменит ли он стратегию или только тактику? Если стратегия остаётся, то можно сразу не принимать скороспелых решений об отмене тех или иных действий или о срочных дополнительных мерах. Можно на какой-то срок оставить процесс без корректировки, а затем осуществить новый расчёт модели. В том же случае, если стратегия в корне меняется, требуется незамедлительное вмешательство. Ответы на эти и подобные вопросы и составляют содержание «шпаргалки» для руководителя. Рассмотрим содержание процедуры анализа моделей на чувствительность на конкретном примере задачи п.2.4. z = 3x1 + 4x2 + 3x3 + x4 ⇒ max 2x1 + 4x2 + 8x4 ⪕ 12 7x1 + 2x2 + 2x3 + 6x4 ⪕ 8 5x1 + 8x2 + 4x3 + 3x4 ⪕ 48 В таблице приводится оптимальное решение задачи (см. Т3 п.2.4). Кроме того таблица дополнена значениями коэффициентов целевой функции при базисных переменных (cj) и при небазисных переменных (cj′) и строками zj и j. zj - величина косвенного эффекта ( см. п. 2. 2); строка j содержит значения чистого эффекта от предполагаемого включения в план небазисных переменных. Все значения имеют знак минус. Это указывает на то, что при их введении в уже созданный оптимальный план (с единичной эффективностью) целевая функция «ухудшится». Таблица АЧ cj′ 3 1 cj ** -x1 -y1 -y2 -x4 4 1/2 x2 1/4 2 3 x3 3 3 -1/4 1/2 1 1 y3 -11 -1 -2 -17 20 Z 8 1/4 3/2 10 15 Zj 11 1/4 3/2 11 j=c′j-zj -8 -1/4 -3/2 -10 Анализ модели на чувствительность начинается с выявления наличия альтернативных планов. Если в строке j нет значений, равных 0, то альтернативных планов нет. Проанализируем, в каких пределах изменение входных параметров не повлечёт изменение стратегии поведения системы, т.е. в каких пределах гарантируется «устойчивость» оптимального плана. 1). Изменение коэффициентов целевой функции при небазисных (верхних) переменных 17 не повлияет на состав базисных переменных, т.е. на стратегию, если это изменение удовлетворяет формуле: -∞ ⪕ c′j ⪕ -( c′j-zj). Вопрос. Каково должно быть увеличение ценового коэффициента c′1 за единицу производственного реквизита x1 (небазисной переменной), чтобы её включение в план стало выгодным? Ответ. При выходе c′1 за пределы устойчивости оптимального плана, т.е. при увеличении c′1 более , чем на 8 условных ценовых единиц (у.ц.е.). Иными словами реквизит x1 станет выгодным для включения в план, если его «ценальность» станет более 11у.ц.е. 2) Изменение коэффициентов целевой функции при базисных (боковых) переменных не повлияет на состав базиса, т.е. на стратегию плана в пределах: c′j−zj ⪕ c′j−zj cj⪕ . Вопрос. Какова чувствительность оптимального плана к изменению ценового коэффициента с3? Ответ. max ⪕ c3 ⪕ 1; ; / / ; = ; min / / = 1. ⪕ с3 ⪕ 4. При выходе с3 за эти границы произойдет изменение 3). Изменение величины свободных членов bi можно рассматривать как равноценное изменение дополнительной переменной yi, соответствующей этому свободному члену. Это изменение не повлияет на состав базисных переменных, т.е. на стратегию плана, если изменение bi находится в пределах: x x ⪕ bi ⪕ . Вопрос. В каком интервале изменения свободного члена b2 действует оптимальный план? Ответ: max / = -2; min = 10; -2 ⪕ b2 ⪕ 10; 6 ⪕ b2 ⪕ 18. При выходе b2 за эти границы план изменится. ЗАМЕЧАНИЕ. Пи изменении свободного члена bi на величину bi целевая функция изменится на величину bi⦁ui, где ui - двойственная оценка дополнительной переменной yi. Пусть b2 = 10; u2 = (cм. п.2.4, таблица ТДС) .Тогда z = 10⦁ u2 = 10⦁ = 15; zновое =z + z, где z = 15 (см. п.2.5, таблица АЧ); zновое = 15 + 15 = 30. Анализ модели линейного программирования на чувствительность позволяет установить границы влияния изменения всех входных параметров модели, включая полный набор матрицы технологических коэффициентов, на результаты решения. Реализация анализа затрагивает не только стратегический аспект, предполагающий устойчивость базисного состава, но и тактический. Это выражается в возможности корректировать численные значения базисных переменных после изменения входных параметров в оперативном режиме посредством простых арифметических формул, не прибегая к пересчёту по процедуре симплекс-метода. В условиях типовых производственных процессов особенно в быстро меняющихся обстоятельствах заведомо составленная расчётная заготовка может оказаться весьма полезной. 18 КОНТРОЛЬНЫЕ ВОПРОСЫ 1.Что предопределяет множественность допустимых решений задачи линейного программирования. 2. Что означает понятие «альтернативное» решение. 3. В чём связь понятий опорный план и опорное решение. 4. Геометрическая сущность симплекс-метода. 5. Алгебраическая характеристика вершины симплекса. 6. В какой форме осуществляется аналитическое решение задачи линейного программирования. 19