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

     Содержание

     Введение

     Термин линейное программирование появился в Америке в середине 40-х годов (первая американская работа по частной задаче линейного программирования опубликована в 1941 г.). В Советском Союзе исследования в этой области начались ранее. В конце 30-х годов целый ряд существенных результатов по линейному программированию был установлен Л.В. Канторовичем.

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

     Задачи  линейного программирования являются самыми простыми и лучше изученными задачами. Для них характерно: показатель эффективности (целевая функция) выражается линейной зависимостью; ограничения  на решения – линейные равенства  или неравенства.

     Трудности решения задач линейного программирования зависят от: вида зависимости, связывающей  целевую функцию с элементами решения; размерности задачи, то есть от количества элементов решения  х1, х2,…, xn; вида и количества ограничений  на элементы решений. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

     1. Параметрическое программирование

     ПАРАМЕТРИЧЕСКОЕ ПРОГРАММИРОВАНИЕ [parametrical programming] — раздел математического программирования, изучающий задачи, отличие которых от других задач состоит в следующем. Коэффициенты их целевой функции, или числовые характеристики ограничений, или и те и другие, предполагаются не постоянными величинами (как, напр., в линейном программировании), а функциями, зависящими от некоторыхпараметров. Причем чаще всего эта зависимость носит линейный характер.

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

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

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

     2. ТРАНСПОРТНАЯ ЗАДАЧА

     - один из наиболее важных частных  случаев общей задачи линейного программирования. Содержательно транспортная задача формулируется следующим образом.  
Пусть в пунктах A1, А2, . . ., А т производится некоторый однородный продукт, причем объем производства лого продукта в пункте Аi составляет а i единиц, i=1, . . ., т. Произведенный в пунктах производства продукт должен быть доставлен в пункты потребления B1, В2, . . ., В n, причем объем потребления в пункте В j составляет bj единиц продукта. Предполагается, что транспортировка готовой продукции возможна из любого пункта производства в любой пункт потребления и транспортные издержки, приходящиеся на перевозку единицы продукта из пункта Ai в пункт Bj, составляют cij денежных единиц. Задача состоит в организации такого плана перевозок, при к-ром суммарные транспортные издержки были бы минимальными.  
Формально задача ставится следующим образом. Пусть xij - количество продукта, перевозимого из пункта Ai в пункт Bj.Требуется определить совокупность из тп величин х ij, удовлетворяющих условиям

     

     и обращающих в минимум линейную форму

     

     Группа  ограничений (1) связана с тем обстоятельством, что объем вывезенного из каждого  пункта производства продукта в точности равен объему произведенного в этом пункте продукта, а объем ввезенного в пункт потребления продукта в точности соответствует его  потребности. При этих ограничениях необходимым и достаточным условием для разрешимости является выполнение условия баланса

     

     Специфическими  для транспортной задачи являются следующие два обстоятельства: а) каждое из переменных xij входит в два уравнения системы (1); б) все коэффициенты при переменных xij принимают лишь два значения 0 или 1. Условия а) и б) позволили разработать для решения транспортной задачи алгоритмы, существенно более простые, чем симплексный метод, который является одним из основных методов решения задач линейного программирования.  
Наиболее известными из этих алгоритмов являются метод потенциалов и т. н. венгерский метод. Метод потенциалов - это метод последовательного улучшения плана (перевозок) с использованием второй теоремы двойственности для проверки оптимальности [1]. Венгерский метод - это метод последовательного построения допустимого плана, к-рый автоматически оказывается оптимальным. В основе венгерского алгоритма лежит метод чередующихся цепей [2].  
Известны следующие два обобщения классической транспортной задачи, являющиеся отражением встречающихся на практике ситуаций. Открытая модель Т. э.- это транспортная задача с нарушенным условием баланса (2), что означает либо превышение объема производства над объемом потребления, либо наоборот. Такая задача сводится к классическим транспортным задачам путем введения фиктивного пункта производства (или потребления) с мощностью производства (или потребления), равной разности объемов производства и потребления.  
Много индексные транспортные задачи при сохранении общей проблемы минимизации транспортных издержек учитывают неоднородность груза (продуктов производства) и неоднородность транспортных средств.  
За рубежом транспортная задача иногда называется проблемой Хичкока. 

     3. Целочисленное программирование.

     1.1.Основные понятия.           

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

     Целочисленным (иногда его называют также дискретным) программированием

     называется  раздел математического программирования, изучающий экстремальные

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

     целочисленности, а область допустимых решений  конечна. Огромное количество

     экономических задач носит дискретный, чаще всего  целочисленный характер, что

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

     например, нельзя построить два с половиной  завода, купить полтора автомобиля

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

     симплексным методом, с последующим округлением  до целых чисел. Однако такой

     подход  оправдан, когда отдельная единица  составляет очень малую часть  всего

     объема (например, товарных запасов); в противном  случае он может внести

     значительные  искажения в действительно оптимальное  решение. Поэтому

     разработаны специальные методы решения целочисленных  задач.

     Рекомендации  по формулировке и решению ЦП

         

1. Количество целочисленных переменных уменьшать насколько возможно.
2. Например, целочисленные переменные, значения которых должно быть не менее 20, можно рассматривать как непрерывные.
3. В отличие от общих задач ЛП,добавление новых ограничений особенно включающих целочисленные переменные,обычно уменьшают время решения задач ЦП.  
4. Если нет острой необходимости в нахождении точного оптимального целочисленного решения, отличающегося от непрерывного решения, например, 3%. Тогда реализацию метода ветвей и границ для задачи максимизации можно заканчивать, если отношение разницы      между верхней и нижней границ к верхней границы меньше 0,03.

      

     Метод ветвей и границ можно применять  для решения задач нелинейного

     программирования.

      

      1.2.Метод Гомори                              

     Задача  целочисленного программирования может  быть сформулирована следующим

     образом: найти максимум или минимум функции

                                           (7.1)                                     

     при условиях

     (7.2)

          _Xj > 0,    j = 1, 2, ..., n,  а также при дополнительном условии

         

 

          х_j — целые числа.

     В некоторых случаях условие (7.4) распространяется только на часть переменных,

     такие задачи называются частично целочисленными.

     Для решения задач целочисленного программирования разработаны специальные

     методы. К ним относятся метод отсечений (метод Гомори) и метод ветвей и

     границ.

     В основе метода Гомори заложена идея, состоящая  в том, что сначала решается

     задача  линейного программирования (7.1)—(7.3) без учета условий

     целочисленности. Если полученное таким образом решение целочисленное, то оно

     принимается за оптимальный план задачи (7.I)—(7.4). Если решение

     нецелочисленное, то система ограничений дополняется  условием, которое

     отсекает  от множества планов задачи нецелочисленный  оптимальный план, но при

     этом  сохраняет целочисленные вершины множества планов. Затем решается задача

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

     образом решение целочисленное, то оно оптимально и для задачи (7.1)—(7.4).

     Если  же и после этого не для всех переменных выполняется условие

     целочисленности, то вводится новое условие-отсечение. Условия-отсечения

     выбираются  таким образом, чтобы за конечное число шагов прийти к

     целочисленному  решению, если оно у данной задачи существует. Один из

     алгоритмов  построения таких условий-отсечений  был предложен Гомори.

     Рассмотрим  указанный алгоритм. Пусть получено решение задачи (7.1)-(7.3) без

     учета целочисленности и пусть в  строке r симплексной таблицы с  оптимальным

     решением  содержится нецелочисленная компонента опорного плана х_r0. 

     В этом случае к условиям (7.1)—(7.3) добавляют условие, порожденное строкой г.

     Для составления этого условия-отсечения  используем г-е уравнение из последней

     симплексной таблицы, содержащей оптимальное решение,

     (7.5)

     Далее введем понятие целой и дробной  частей чисел а_r0 и а

     _rj, для чего запишем эти числа в виде:

     Здесь [а_r0] и [a_rj] - целые части, a q_t, q_r] - дробные части чисел а_rj и a_rj.

     Например,  ³⁷/₃ =12 +1/3,  так как [³⁷

     /₃] = 12, a   -^s/, = -3 + 1/3„ так как [-8/3] = -3.

     Из  уравнения (7.5) найдем х_r

          x_r=а_r0-  

     Теперь  числа а_ю и а_rj  заменим суммами целых и дробных частей:

     x_r =

     Предположим, что все x_j - целые числа. Тогда разность

     является  целым числом.

     Чтобы оказалось целым числом и х_r, необходима целочисленность разности

     Но  О<q_г<1,     0<g_rj<1,     a

     (7.6)

     Если  допустить, что разность (7.6) больше нуля, то

     Однако  в этом случае разность (7.6) не может  быть целым числом.

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

     неравенством

                                                                                (7.7)

     Условие (7.7) и является добавочным ограничением в задаче линейного

     программирования. Для использования его в симплексном  методе требуется ввести

     дополнительную  переменную х_п+≥0 , после чего неравенство

     превращается  в уравнение

     Обычно  это ограничение записывают в  следующем виде:

     (7.8)

     Последовательно добавляя новые ограничения к  решению очередных задач,

     получаем  целочисленные координаты оптимального плана задачи (7.1)—(7.4), если

     только  не выясняется в какой-либо момент, что текущая задача не имеет

     решения. Это означало бы отсутствие целочисленного решения задачи

     (7.1)—(7.4).

     Пример 1. Найти оптимальный целочисленный  план задачи Z(X) = х₁ - Зх

     ₂ + 5х₃ + 2х₄ -max

     при условия

     x₁+x₂+x₃     =15

     2x₁+   3x₃+x₄=8,

     х_j, > 0,     х_j — целые числа,  j = 1, 2, 3, 4.

     Решение. Пошаговое решение задачи приведено  в табл. 7.1

     Таблица 7.1

         

 

         

 

     Оптимальный    план    задачи    без    условия    целочисленности

     X = (0, 37/3, 8/3, 0)- для дальнейшего решения  задачи к таблице оптимального

     плана добавлено условие

     -2/3x₁-1/3x₄≤-2/3.

     Номер индекса г выбран из условия большей  дробной части компоненты а_i0

     . Имеем г = 2; j = 0: [8/3] = 2,     2 – 8/3 = -²/₃; j=1:

     [²/₃1 = О,     О - ²/₃ ⁼

     -²/₃;     j = 2:    [0] = 0, 0 - 0 = 0; j = 3:    [0]= 0,

     0 - 0 = 0; j ⁼ 4:    [1/₃] = 0, 0 — 1/₃ = -1/

     ₃. Сделав один шаг (в общем случае для получения целочисленного решения

     одной итерации, конечно, недостаточно) метода последовательного уточнения

     оценок,  получили оптимальный план целочисленной  задачи Х*= (О, 13, 2, 2)

     Трудоемкость  решения целочисленной задачи обусловлена  вводом новых добавочных

     ограничений и новых переменных. В связи  с этим необходимо придерживаться

     следующего  правила, позволяющего при определенных условиях сокращать текущие

     таблицы. Дополнительная переменная х_п+1 вводится в процессе решения

     с добавочным ограничением как базисная переменная очередного псевдоплана  и

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

     дальнейших итерациях, согласно правилу преобразования таблицы, переменная х

     _п+1 снова окажется базисной, ее значение станет несущественным для

     основных  переменных задачи, так что строка и столбец текущей таблицы,

     отвечающие  х_п+_] вычеркиваются. Правило сокращения таблиц

     ограничивает их размеры: не более n строк и не более (2n -m) столбцов.

     Рассматриваемый алгоритм целочисленного программирования сводится к методу

     последовательного уточнения оценок с дополнительными  правилами расширения и

     сокращения  текущей таблицы решения задачи.

     Пример 2. Получить целочисленный оптимальный  план задачи

     Z(X) = x₁— 4х₂ — 2х₃ + Зх₄ —> max при условиях

     3x₁+x₂+8x₃+x₄=35

     x₁        +x₃+x₄≤6

     x_j≥ 0,     х_j — целые числа,    j = 1, 2, 3, 4.

     Решение. Пошаговое решение задачи приведено  в табл. 7.2.

     Таблица 7.2

         

 

     На  шаге 2 решения задачи без ограничения  целочисленности получаем

     оптимальный нецелочисленный план

     X = (0, 0, 29/7, 13/7).

     Поскольку обе базисные координаты X нецелочисленны, выбираем любую — первую

     или вторую — строку таблицы на шаге 2, а именно вторую, и строим добавочное

     ограничение

     -5/7x₁-6/7x₂-1/7x₅+x₆=-6/7.

     Вводя ограничение добавочной строкой  на шаге 2, находим направляющий элемент

     в этой строке:

     Осуществляя преобразование табл. 7.2 с направляющим элементом (-5/7),

     получаем  на шаге 3 оптимальный план новой  задачи, снова нецелочисленный. На

     шаге 3 добавляем очередное условие, получаем четыре строки ограничений.

     Поскольку на шаге 3                         достигается

     в столбце А₆, то х₆ становится базисной переменной на шаге

     4. В соответствии с правилом сокращения таблицы на шаге 4 вычеркиваем строку

     и столбец, соответствующие х₆, добавляем новую строку, а на шаге 5

     получаем  псевдоплан X = (4, 0, 3, -1). Методом последовательного уточнения

     оценок  на шаге 6 получаем план, но нецелочисленный. Оптимальный целочисленный

     план  получаем лишь на шаге 7:               X* = (О, 1, 4, 2), max Z(X) = -6.

                           

     1.3. Метод ветвей и границ                         

     Одним из широко распространенных методов  решения целочисленных задач

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

     линейного программирования, так и для задач, не сводимых к задачам линейного

     программирования. Рассмотрим идею метода ветвей и границ на примере общей

     задачи  дискретного программирования

     f(X) -> max,

     (7.9)

     Х€D

     (7.10)

     где D — конечное множество.

     Сначала найдем оценку £(D) (границу) функции f(X), X е D:    f(X) ≤

     £(D) для V X е D. Если для некоторого плана  Х° задачи (7.9)-(7.10)

     справедливо равенствоf(X⁰) = £(D), то Х° = X^*

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

     разбиение (ветвление) множества D на конечное число  непересекающихся

     подмножеств D¹_i:  ỤD¹_i. = D,

     ∩D¹_i = Ө, и вычисление оценки £(D¹

     _i) (границ), 1≤i≤m (рис 7.1)

         

     Рис. 7.1

         

 

     Если  для некоторого плана X¹_i е Di¹,   1

     ≤ / ≤ m выполняется условие f(X_k^l)= £(D

     ¹_k)≥ £(D¹_i),

     1≤i≤m  то X_k¹=X^* является

     оптимальным планом (решением) задачи (7.9)-(7.10).

     Если  такого плана нет, то выбирается подмножество D_k^l с

     наибольшей оценкой £(D¹_i):

     и разбивается на конечное число непересекающихся подмножеств

     D²_kj: UD²_kj=D¹_k, 

     ∩D²_kj=Ө. Для каждого подмножества находится

     оценка  £(D²_kj), 1≤j≤n  (рис 7.2)

     (рис. 7.2).

         

     Если  при этом найдется план X²_j е D²_kJ

     , 1 ≤j ≤n, такой, что f(X²_r)= £(D²

     _kr)≥ £(D²_kj), 1≤j≤n, то X

     ²_r= X* является решением задачи (7.9)-(7.10). Если такого плана

     нет, то процедуру ветвления осуществляют для множества D²_kj

     с наибольшей оценкой £(D²_kj) , 1≤j≤n .

     Способ  ветвления определяется спецификой конкретной задачи.

     Рассмотрим  задачу, которую можно свести к  задаче целочисленного линейного

     программирования.

     Пример.

     Контейнер объемом 5 м³ помещен на контейнеровоз грузоподъемностью 12

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

     m_j (в тоннах), объем единицы груза V_j (в м³),

     стоимости Cj (в условных денежных единицах) приведены  в табл. 7.3.

     Таблица 7.3

         

 

     Требуется загрузить контейнер таким образом, чтобы стоимость перевозимого

     груза была максимальной.