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

Введение

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

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

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

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

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

 

 

 

 

 

 

 

 

 

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

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

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

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

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

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

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

     Начало линейному программированию было положено в 1939 г. советским математиком-экономистом Л. В. Канторовичем в работе «Математические методы организации и планирования производства». Появление этой работы открыло новый этап в применении математики в экономике. Спустя десять лет американский математик Дж. Данциг разработал эффективный метод решения данного класса задач — симплекс-метод. Общая идея симплексного метода (метода последовательного улучшения плана) для решения ЗЛП состоит в следующем:

     1) умение находить начальный опорный план;

     2) наличие признака оптимальности опорного плана;

     3) умение переходить к нехудшему опорному плану.

1.1 Постановка задачи линейного программирования  и свойства ее решений

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

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

     Формы записи задачи линейного программирования. Общей задачей линейного программирования называют задачу

       (2.1)

при ограничениях

     (2.2)

    (2.3)

       (2.4)

                   (2.5)

• - произвольные   (2.6)

Где заданные действительные числа; (2.1) – целевая функция; (2.1) – (2.6) –ограничения; - план задачи.

     Пусть ЗЛП представлена в следующей записи:

                          (2.7)

     (2.8)

            (2.9)

Чтобы задача (2.7) – (2.8) имела решение, системе её ограничений (2.8) должна быть совместной. Это возможно, если  r этой системы не больше числа неизвестных n. Случай r>n вообще невозможен. При r=n система имеет единственное решение, которое будет при оптимальным.

В этом случае проблема выбора оптимального решения теряет смысл. Выясним структуру координат  угловой точки многогранных решений. Пусть r<n. В этом случае система  векторов содержит базис — максимальную линейно независимую подсистему векторов, через которую любой вектор системы может быть выражен как ее линейная комбинация. Базисов, вообще говоря, может быть несколько, но не более Каждый из них состоит точно из r векторов. Переменные ЗЛП, соответствующие r векторам базиса, называют, как известно, базисными и обозначают БП. Остальные n – r переменных будут свободными, их обозначают СП. Не ограничивая общности, будем считать, что базис составляют первые m векторов .Этому базису соответствуют базисные переменные а свободными будут переменные .

Если свободные переменные приравнять нулю, а базисные переменные при этом примут неотрицательные значения, то полученное частное решение системы (8) называют опорным решением (планом).

     Теорема. Если система векторов содержит m линейно независимых векторов то допустимый план

                     (2. 10)

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

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

    Графический способ решения ЗЛП    

 Геометрическая интерпретация экономических задач дает возможность наглядно представить, их структуру, выявить особенности и открывает пути исследования более сложных свойств. ЗЛП с двумя переменными всегда можно решить графически. Однако уже в трехмерном пространстве такое решение усложняется, а в пространствах, размерность которых больше трех, графическое решение, вообще говоря, невозможно. Случай двух переменных не имеет особого практического значения, однако его рассмотрение проясняет свойства ОЗЛП, приводит к идее ее решения, делает геометрически наглядными способы решения и пути их практической реализации. 
     Пусть дана задача 
                                          (2.11) 
                                         (2.12) 
                                                (2.13) 
     Дадим геометрическую интерпретацию элементов этой задачи. Каждое из ограничений (2.12), (2.13) задает на плоскости  некоторую полуплоскость. Полуплоскость — выпуклое множество. Но пересечение любого числа выпуклых множеств является выпуклым множеством. Отсюда следует, что область допустимых решений задачи (2.11) — (2.13)  есть выпуклое множество. 
     Перейдем к геометрической интерпретации целевой функции. Пусть область допустимых решений ЗЛП — непустое множество, например многоугольник  . 
       
      Выберем произвольное значение целевой функции  . Получим  . Это уравнение прямой  линии. В точках прямой NМ целевая функция сохраняет одно и то же постоянное значение  . Считая в равенстве (2.11)   параметром, получим уравнение семейства параллельных прямых, называемых линиями уровня целевой функции (линиями постоянного значения). 
     Найдём частные производные целевой функции по   и  : 
      ,                                                (2.14) 
      .                                               (2.15) 
     Частная производная (2.14)  (так же как и (2.15)) функции показывает скорость ее возрастания вдоль данной оси. Следовательно,   и   — скорости возрастания   соответственно вдоль осей   и  . Вектор   называется градиентом функции. Он показывает направление наискорейшего возрастания целевой функции: 
       
     Вектор   указывает направление наискорейшего убывания целевой функции. Его называют антиградиентом. 
     Вектор   перпендикулярен к прямым   семейства   . 
     Из геометрической интерпретации элементов ЗЛП вытекает следующий порядок ее графического решения. 
     1. С учетом системы ограничений строим область допустимых решений  . 
     2. Строим вектор   наискорейшего возрастания целевой функции — вектор градиентного направления. 
     3. Проводим произвольную линию уровня   .  
     4. При решении задачи на максимум перемещаем линию уровня   в направлении вектора   так, чтобы она касалась области допустимых решений в ее крайнем положении (крайней точке). В случае решения задачи на минимум линию уровня   перемещают в антиградиентном направлении.  
     5. Определяем оптимальный план   и экстремальное значение целевой функции  .

Пример решения  задачи линейного программирования:

Найти максимум и минимум  функции  при условиях

Решение. Построим многоугольник решений. Для этого в неравенствах системы ограничений и условияхнеотрицательности переменных знаки неравенств заменим на знаки точных равенств:

Построив полученные прямые, найдем соответствующие полуплоскости  и их пересечение (рис. 6).

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

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

Решив эту систему  уравнений, получим  Таким образом, максимальное значение функции 

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

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

Теория двойственности     

 Понятие двойственности  рассмотрим на примере задачи  оптимального использования сырья. Пусть на предприятии решили рационально использовать отходы основного производства. В плановом периоде появились отходы сырья m видов в объемах  единиц  . Из этих отходов, учитывая специализацию предприятия, можно наладить выпуск n видов неосновной продукции. Обозначим через   норму расхода сырья i-го вида на единицу j-й   продукции,  - цена реализации единицы j-й продукции (реализация обеспечена). Неизвестные величины задачи:   — объемы выпуска j-й продукции, обеспечивающие предприятию максимум выручки.  
     Математическая модель задачи: 
                         (2.23) 
                           (2.24) 
                                         (2.25) 
     Предположим далее, что с самого начала при изучении вопроса об использовании отходов основного производства на предприятии появилась возможность реализации их некоторой организации. Необходимо установить прикидочные оценки (цены) на эти отходы. Обозначим их  .  
     Оценки должны быть установлены исходя из следующих требований, отражающих несовпадающие интересы предприятия и организации: 
     1) общую стоимость отходов сырья покупающая организация стремится минимизировать;  
     2) предприятие согласно уступить отходы только по таким ценам, при которых оно получит за них выручку, не меньшую той, что могло бы получить, организовав собственное производство. 
     Эти требования формализуются в виде следующей ЗЛП. 
     Требование 1 покупающей организации – минимизация покупки:  
                          (2.26) 
     Требование 2 предприятия, реализующего отходы сырья, можно сформулировать в виде системы ограничений. Предприятие откажется от выпуска каждой единицы продукции первого вида, если  , где левая часть означает выручку за сырьё идущее на единицу продукции первого вида; правая – её цену. 
     Аналогичные рассуждения логично провести в отношении выпуска продукции каждого вида. Поэтому требование предприятия, реализующего отходы сырья, можно формализовать в виде сл. системы ограничений: 
                            (2.27) 
     По смыслу задачи оценки не должны быть отрицательными: 
      .                          (2.28) 
     Переменные     называют двойственными оценками или объективно обусловленными оценками. 
     Задачи (2.23) - (2.25) и (2.26) - (2.28) называют парой взаимно двойственных ЗЛП. 
     Между прямой и двойственной задачами можно установить следующую взаимосвязь: 
     1. Если прямая задача на максимум, то двойственная к ней — на минимум, и наоборот. 
     2. Коэффициенты   целевой функции прямой задачи являются свободными членами ограничений двойственной задачи. 
     3. Свободные члены   ограничений прямой задачи являются коэффициентами целевой функции двойственной. 
     4. Матрицы ограничений прямой и двойственной задач являются транспонированными друг к другу. 
     5. Если прямая задача на максимум, то ее система ограничений представляется в виде неравенств типа  . Двойственная задача решается на минимум, и ее система ограничений имеет вид неравенств типа  . 
     6. Число ограничений прямой задачи равно числу переменных двойственной, а число ограничений двойственной — числу переменных прямой. 
     7. Все переменные в обеих задачах неотрицательны.