Линейное программирование. 2

ЛИНЕЙНОЕ  ПРОГРАММИРОВАНИЕ.

ОБЩАЯ  ПОСТАНОВКА  ЗАДАЧИ.

      Процессы  принятия решений лежат в основе любой целенаправленной деятельности. В экономике они предшествуют созданию производственных и хозяйственных  организаций, обеспечивают их оптимальное  функционирование и взаимодействие”. В научных исследованиях –  позволяют выделить важнейшие научные  проблемы, найти способы их изучения, предопределяют развитие экспериментальной  базы и теоретического аппарата. При  создании новой техники – составляют важный этап в проектировании машин, устройств, приборов, комплексов, зданий, в разработке технологии их построения и эксплуатации; в социальной сфере  – используются для организации  функционирования и развития социальных процессов, их координации с хозяйственными и экономическими процессами. Оптимальные (эффективные) решения позволяют  достигать цели при минимальных  затратах трудовых, материальных и  сырьевых ресурсов.

      В классической математике методы поиска оптимальных решений рассматривают  в разделах классической математики, связанных с изучением экстремумов  функций, в математическом программировании.

      Математическое  программирование является одним из разделов исследования операций –  прикладного направления кибернетики, используемого для решения практических организационных задач. Задачи математического  программирования находят применение в различных областях человеческой деятельности, где необходим выбор  одного из возможных образов действий (программ действий).

      Значительное  число задач, возникающих в обществе, связано с управляемыми явлениями, т. е. с явлениями, регулируемыми  на основе сознательно принимаемых  решений. При том ограниченном объеме информации, который был доступен на ранних этапах развития общества, принималось  оптимальное в некотором смысле решение на основании интуиции и  опыта, а затем, с возрастанием объема информации об изучаемом явлении, –  с помощью ряда прямых расчетов. Так происходило, например, создание календарных планов работы промышленных предприятий.

      Совершенно  иная картина возникает на современном  промышленном предприятии с многосерийным  и многономеклатурным производством, когда объем входной информации столь велик, что его обработка с целью принятия определенного решения невозможна без применения современных электронных вычислительных машин. Еще большие трудности возникают в связи с задачей о принятии наилучшего решения.

      Под принятием решений в исследовании операций понимают сложный процесс, в котором можно выделить следующие  основные этапы:

      1-й  этап. Построение качественной модели  рассматриваемой проблемы, т. е.  выделение факторов, которые представляются  наиболее важными, и установление  закономерностей, которым они  подчиняются. Обычно этот этап  выходит за пределы математики.

      2-й  этап. Построение математической  модели рассматриваемой проблемы, т. е. запись в математических  терминах качественной модели. Таким  образом, математическая модель  – это записанная в математических  символах абстракция реального  явления, так конструируемая, чтобы  анализ ее давал возможность  проникнуть в сущность явления.  Математическая модель устанавливает  соотношения между совокупностью  переменных – параметрами управления  явлением. Этот этап включает  также построение целевой функции  переменных, т. е. такой числовой  характеристики, большему (или меньшему) значению которой соответствует  лучшая ситуация с точки зрения  принимающего решения.

      Итак, в результате этих двух этапов формируется  соответствующая математическая задача. Причем, второй этап уже требует  привлечения математических знаний.

      3-й  этап. Исследование влияния переменных  на значение целевой функции.  Этот этап предусматривает владение  математическим аппаратом для  решения математических, задач, возникающих  на втором этапе процесса принятия, решения.

      Широкий класс задач управления составляют такие экстремальные задачи, в  математических моделях которых  условия на переменные задаются равенствами  и неравенствами. Теория и методы решения этих задач как раз  и составляют содержание математического  программирования. На третьем этапе, пользуясь математическим аппаратом, находят решение соответствующих  экстремальных задач. Обратим внимание на то, что задачи математического  программирования, связанные с решением практических вопросов, как правило, имеют большое число переменных и ограничений. Объем вычислительных работ для нахождения соответствующих  решений столь велик, что весь процесс не мыслится без применения современных электронных вычислительных машин (ЭВМ), а значит, требует либо создания программ для ЭВМ, реализующих  те или иные алгоритмы, либо использования  уже имеющихся стандартных программ.

      4-й  этап. Сопоставление результатов  вычислений, полученных на 3-м этапе,  с моделируемым объектом, т. е.  экспертная проверка результатов  (критерий практики). Таким образом,  на этом этапе устанавливается  степень адекватности модели  и моделируемого объекта в  пределах точности исходной информации. Здесь возможны два случая:

          * 1-й случай. Если результаты сопоставления  неудовлетворительны (обычная ситуация  на начальной стадии процесса  моделирования), то переходят ко  второму циклу процесса. При этом  уточняется входная информация  о моделируемом объекте и в  случае необходимости уточняется  постановка задачи (1-й этап), уточняется  или строится заново математическая  модель (2-й этап), решается соответствующая  математическая задача (3-й этап) и, наконец, снова проводится  сопоставление (4-й этап).

    * 2-й случай. Если результаты сопоставления  удовлетворительны, то модель  принимается. Когда речь идет  о неоднократном использовании  на практике результатов вычислений, возникает задача подготовки  модели к эксплуатации. Предположим,  например, что целью моделирования  является создание календарных  планов производственной деятельности  предприятия. Тогда эксплуатация  модели включает в себя сбор  и обработку информации, ввод  обработанной информации в ЭВМ,  расчеты на основе разработанных  программ календарных планов  и, наконец, выдачу результатов  вычислений (в удобном для пользователей виде) для их использования в сфере производственной деятельности.

      В математическом программировании можно  выделить два направления.

      К первому, уже вполне сложившемуся направлению  – собственно математическому программированию – относятся детерминированные  задачи, предполагающие, что вся  исходная информация является полностью  определенной.

      Ко  второму направлению – так  называемому стохастическому программированию – относятся задачи, в которых  исходная информация содержит элементы неопределенности, либо когда некоторые  параметры задачи носят случайный  характер с известными вероятностными характеристиками. Так, планирование производственной деятельности зачастую производится в  условиях неполной информации о реальной ситуации, в которой будет выполняться  план. Или, скажем, когда экстремальная  задача моделирует работу автоматических устройств, которая сопровождается случайными помехами. Заметим, что одна из главных трудностей стохастического  программирования состоит в самой  постановке задач, главным образом  из-за сложности анализа исходной информации.

      Традиционно в математическом программировании выделяют следующие основные разделы.

      Линейное  программирование – целевая функция  линейна, а множество, на котором  ищется экстремум целевой функции, задается системой линейных равенств и неравенств. В свою очередь в  линейном программировании существуют классы задач, структура которых  позволяет создать специальные  методы их решения, выгодно отличающиеся от методов решения задач общего характера. Так, в линейном программировании появился раздел транспортных задач.

      Нелинейное  программирование – целевая функция  и ограничения нелинейны. Нелинейное программирование принято подразделять следующим образом:

      Выпуклое  программирование – целевая функция  выпукла (если рассматривается задача ее минимизации) и выпукло множество, на котором решается экстремальная  задача.,

      Квадратичное  программирование – целевая функция  квадратична, а ограничениями являются линейные равенства и неравенства.

      Многоэкстремальные  задачи. Здесь обычно выделяют специализированные классы задач, часто встречающихся  в приложениях, например, задачи о  минимизации на выпуклом множестве  вогнутых функций.

      Важным  разделом математического программирования является целочисленное программирование, когда на переменные накладываются  условия целочисленности.

      Целью математического программирования является создание, где это возможно, аналитических методов определения  решения, а при отсутствии таких  методов – создание эффективных  вычислительных способов получения  приближенного решения.

Наконец, заметим, что наименование предмета – “математическое программирование”  – связано с тем, что целью  решения задач является выбор  программы действий. Рассмотрим более  подробно задачу линейного программирования.

ОБЩАЯ  И ОСНОВНАЯ  ЗЛП.

  В  задачах линейного программирования требуется найти максимум или минимум линейной функции при условии, что ее переменные принимают неотрицательные значения и удовлетворяют некоторой системе линейных уравнений или линейных неравенств либо системе, содержащей как линейные неравенства, так и линейные уравнения. Каждая из этих задач является частным случаем общей задачи линейного программирования.

      Определение 1.

      Общей задачей линейного программирования называется задача, которая состоит  в определении максимального (минимального) значения функции

(8)

при условиях

(9)

(10)

(11)

где - заданные постоянные величины и .

Определение 2.

Функция (8) называется целевой функцией (или линейной формой) задачи (8) – (11), а условия (9) – (11) – ограничениями данной задачи.

Определение 3.

      Стандартной (или симметричной} задачей линейного программирования называется задача, которая состоит в определении максимального значения функции (8) при выполнении условий (9) и (11), где k = m и l = n.

Определение 4.

      Канонической (или основной) задачей линейного программирования называется задача, которая состоит в определении максимального значения функции (8) при выполнении условий (10) и (11), где k = 0 и l = п.

Определение 5.

      Совокупность  чисел  , удовлетворяющих ограничениям задачи (9) – (11), называется допустимым решением (или планом).

Определение 6.

      План  , при котором целевая функция задачи (8) принимает свое максимальное (минимальное) значение, называется оптимальным.

      Значение  целевой функции (8) при плане  Х будем обозначать через . Следовательно, X^* – оптимальный план задачи, если для любого Х выполняется неравенство [соответственно ].

      Указанные выше три формы задачи линейного  программирования эквивалентны в том  смысле, что каждая из них с помощью  несложных преобразований может  быть переписана в форме другой задачи. Это означает, что если имеется  способ нахождения решения одной  из указанных задач, то тем самым  может быть определен оптимальный  план любой из трех задач.

      В том случае, когда требуется найти  минимум функции  , можно перейти к нахождению максимума функции , поскольку .

      Ограничение-неравенство  исходной задачи линейного программирования, имеющее вид “ ”, можно преобразовать в ограничение-равенство добавлением к его левой части дополнительной неотрицательной переменной, а ограничение-неравенство вида “ ” – в ограничение-равенство вычитанием из его левой части дополнительной неотрицательной переменной. Таким образом, ограничение-неравенство

преобразуется в ограничение-равенство

(12)

а ограничение-неравенство

– в ограничение-равенство

(13)

      В то же время каждое уравнение системы  ограничений

можно записать в виде неравенств:

(14)

      Число вводимых дополнительных неотрицательных  переменных при преобразовании ограничений-неравенств в ограничения-равенства равно  числу преобразуемых неравенств.

      Вводимые  дополнительные переменные имеют вполне определенный экономический смысл. Так, если в ограничениях исходной задачи линейного программирования отражается расход и наличие производственных ресурсов, то числовое значение дополнительной переменной в плане задачи, записанной в форме основной, равно объему неиспользуемого соответствующего ресурса.

      Отметим, наконец, что если переменная , не подчинена условию неотрицательности, то ее следует заменить двумя неотрицательными переменными и , приняв .

Пример 4.

      Записать  в форме основной задачи линейного  программирования следующую задачу: найти максимум функции  при условиях

      Решение. В данной задаче требуется найти максимум функции, а система ограничений содержит четыре неравенства. Следовательно, чтобы записать ее в форме основной задачи, нужно перейти от ограничений-неравенств к ограничениям-равенствам. Так как число неравенств, входящих в систему ограничений задачи, равно четырем, то этот переход может быть осуществлен введением четырех дополнительных неотрицательных переменных. При этом к левым частям каждого из неравенств вида“ “ соответствующая дополнительная переменная прибавляется, а из левых частей каждого из неравенств вида “ ” вычитается. В результате ограничения принимают вид уравнений:

      Следовательно, данная задача может быть записана в форме основной задачи таким  образом: максимизировать функцию  при условиях

Пример 5.

Записать  задачу, состоящую в минимизации  функции  при условиях

в форме основной задачи линейного  программирования.

      Решение. В данной задаче требуется найти минимум целевой функции, а система ограничений содержит три неравенства. Следовательно, чтобы записать ее в форме основной задачи, вместо нахождения минимума функции F нужно найти максимум функции F₁ = -F при ограничениях, получающихся из ограничений исходной задачи добавлением к левым частям каждого из ограничений-неравенств вида “ ” дополнительной неотрицательной переменной и вычитанием дополнительных переменных из левых частей каждого из ограничений-неравенств вида “ ”.

      Следовательно, исходная задача может быть записана в форме основной задачи линейного  программирования так: найти максимум функции  при условиях

Пример 6.

      Записать  в форме стандартной задачи линейного  программирования следующую задачу: найти максимум функции  при условиях

      Решение. Методом последовательного исключения неизвестных сведем данную задачу к следующей: найти максимум функции при условиях

      Последняя задача записана в форме основной для задачи, состоящей в нахождении максимального значения функции  при условиях

      Целевая функция задачи преобразована с  помощью подстановки вместо и их значений в соответствии с уравнениями системы ограничений задачи.

Свойства  основной задачи линейного  программирования. Геометрическое истолкование задачи линейного программирования

      Рассмотрим  основную задачу линейного программирования. Она состоит в определении  максимального значения функции  при условиях

      Перепишем эту задачу в векторной форме: найти максимум функции

F=CX (15)

при условиях

(16)

(17)

где , CX – скалярное произведение; и – m-мерные вектор-столбцы, составленные из коэффициентов при неизвестных и свободных членах системы уравнений задачи:

Определение 7.

      План  называется опорным планом, основной задачи линейного программирования, если система векторов , входящих в разложение (16) с положительными коэффициентами линейно независима.

      Так как векторы  являются m-мерными, то из определения опорного плана следует, что число его положительных компонент не может быть больше, чем т.

Определение 8.

      Опорный план называется невырожденным, если он содержит ровно т положительных компонент, в противном случае он называется вырожденным.

Свойства  основной задачи линейного программирования (15) – (17) тесным образом связаны со свойствами выпуклых множеств.

Определение 9.

      Пусть – произвольные точки евклидова пространства . Выпуклой линейной комбинацией этих точек называется сумма где – произвольные неотрицательные числа, сумма которых равна 1:

Определение 10.

      Множество называется выпуклым, если вместе с любыми двумя своими точками оно содержит и их произвольную выпуклую линейную комбинацию.

Определение 11.

      Точка Х выпуклого множества называется угловой, если она не может быть представлена в виде выпуклой линейной комбинации каких-нибудь двух других различных точек данного множества.

Теорема 1.

      Множество планов основной задачи линейного программирования является выпуклым (если оно не пусто).

Определение 12.

      Непустое  множество планов основной задачи линейного  программирования называется многогранником решений, а всякая угловая точка многогранника решений – вершиной.

Теорема 2.

      Если  основная задача линейного  программирования имеет  оптимальный план, то максимальное значение целевая функция  задачи принимает  в одной из вершин многогранника решений. Если максимальное значение целевая функция  задачи принимает  более чем в  одной вершине, то она принимает  его во всякой точке, являющейся выпуклой линейной комбинацией  этих вершин.

Теорема 3.

      Если  система векторов в разложении (16) линейно независима и такова, что

(18)

где все то точка является вершиной многогранника решений.

Теорема 4.

      Если  – вершина многогранника решений, то векторы , соответствующие положительным в разложении (16), линейно независимы.

      Сформулированные  теоремы позволяют сделать следующие  выводы.

      Непустое  множество планов основной задачи линейного  программирования образует выпуклый многогранник. Каждая вершина этого многогранника  определяет опорный план. В одной  из вершин многогранника решений (т. е. для одного из опорных планов) значение целевой функции является максимальным (при условии, что функция ограничена сверху на множестве планов). Если максимальное значение функция принимает более чем в одной вершине, то это же значение она принимает в любой точке, являющейся выпуклой линейной комбинацией данных вершин.

      Вершину многогранника решений, в которой целевая функция принимает максимальное значение, найти сравнительно просто, если задача, записанная в форме стандартной, содержит не более двух переменных или задача, записанная в форме основной, содержит не более двух свободных переменных, т. е. , где n – число переменных, r – ранг матрицы, составленной из коэффициентов в системе ограничений задачи.

      Найдем  решение задачи, состоящей в определении  максимального значения функции

(19)

при условиях

(20)

(21)

      Каждое  из неравенств (20), (21) системы ограничений  задачи геометрически определяет полуплоскость  соответственно с граничными прямыми и . В том случае, если система неравенств (20), (21) совместна, область ее решений есть множество точек, принадлежащих всем указанным полуплоскостям. Так как множество точек пересечения данных полуплоскостей – выпуклое, то областью допустимых решений задачи (19) – (21) является выпуклое множество, которое называется многоугольником решений (введенный ранее термин “многогранник решений” обычно употребляется, если ). Стороны этого многоугольника лежат на прямых, уравнения которых получаются из исходной системы ограничений заменой знаков неравенств на знаки точных равенств.

      Таким образом, исходная задача линейного  программирования состоит в нахождении такой точки многоугольника решений, в которой целевая функция  F принимает максимальное значение. Эта точка существует тогда, когда многоугольник решений не пуст и на нем целевая функция ограничена сверху. При указанных условиях в одной из вершин многоугольника решений целевая функция принимает максимальное значение. Для определения данной вершины построим линию уровня (где h – некоторая постоянная), проходящую через многоугольник решений, и будем передвигать ее в направлении вектора до тех пор, пока она не пройдет через ее последнюю общую точку с многоугольником решений. Координаты указанной точки и определяют оптимальный план данной задачи.

      Заканчивая  рассмотрение геометрической интерпретации  задачи (19) – (21), отметим, что при нахождении ее решения могут встретиться случаи, изображенные на рис. 1 - 4. Рис. 1 характеризует такой случай, когда целевая функция принимает максимальное значение в единственной точке А. Из рис. 2 видно, что максимальное значение целевая функция принимает в любой точке отрезка АВ. На рис. 3 изображен случай, когда целевая функция не ограничена сверху на множестве допустимых решений, а на рис. 4 – случай, когда система ограничений задачи несовместна.