Шпаргалка по "Математическим методам"

1. ЗЛП

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

ФОРМЫ ЗАПИСИ ЗЛП, ИХ ЭКВИВАЛЕНТНОСТЬ  И СПОСОБЫ ПРЕОБРАЗОВАНИЯ 

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

      при условиях

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

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

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

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

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

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

Таким образом является оптимальным планом задачи (7)-(10), если выполняется неравенство:

   

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

Чтобы перейти  от одной формы записи ЗЛП к  другой, нужно в общем случае уметь:

1. сводить задачу  минимизации функции к задаче  максимизации;

2. переходить  от ограничений-неравенств к ограничениям-равенствам  и наоборот;

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

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

Ограничение-неравенство  исходной ЗЛН, имеющее вид «меньше  или равно», можно преобразовать  в ограничение-равенство добавлением к его левой части дополнительной  переменной, а ограничение-неравенство вида «больше или равно» - в ограничение-равенство вычитанием из его левой части дополнительной неотрицательной переменной. Таким образом, ограничение-неравенство преобразуется в ограничение-равенство

,      (11)

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

        (12)

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

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

       (13)

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

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

Если переменная x_k не подчинена условию неотрицательности, то ее следует заменить двумя неотрицательными переменными u_k и v_k, приняв x_k=u_k-v_k.

      Выпуклой линейной комбинацией  точек х₁,х₂,…, х_n называется сумма , где - произвольные неотрицательные числа, сумма которых равна единице

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

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

       Теорема 1. Множество планов основной ЗЛП является выпуклым (если оно не пусто)

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

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

НАХОЖДЕНИЕ  РЕШЕНИЯ ЗЛП 

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

1. СИМПЛЕКСНЫЙ МЕТОД

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

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

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

        Пусть требуется найти максимальное значение функции

при условиях

Здесь a_ij, b_i и c_j - заданные постоянные  числа .

       Векторная форма данной задачи имеет следующий вид: найти максимум функции

               (17)

при условиях

где 

 

Так как   то опорный план согласно признаку оптимальности будет иметь вид: X=(b₁;b₂;…;b_m;0;…;0)

В опорном плане  присутствует (n-m)- нулей. Этот план  определяется системой  единичных векторов  P₁, P₂,…,P_m, которые образуют базис m-мерного пространства, следовательно, некоторые из векторов P_j могут быть представлены в виде линейной комбинацией векторов данного базиса. Пусть

.

Определим оценку .

Так как векторы  P₁, P₂,…,P_m являются единичными векторами, то можно записать        x_ij=a_ij  ,

,

.

Th3. (признак оптимальности опорного плана) Опорный план задачи (17)-(19) является оптимальным, если для любого j .

Th 4. (признак неограниченности целевой функции) Если для некоторого j=k и среди чисел нет положительных , то целевая функция (17) задачи (17)-(19) не ограничена на множестве ее планов.

Th 5. (признак существования нового опорного плана) Если опорный план Х задачи (17)-(19) не вырожден  и , но среди чисел есть положительные (не все ), то существует опорный план Х`   такой, что .

       Сформулированные теоремы позволяют проверить, является ли найденный опорный план оптимальным, и выявить целесообразность перехода к новому опорному плану. опорного плана. Этот план находят методом северо-западного угла, методом минимального элемента. Сущность методов состоит в том, что опорный план  находят последовательно за n+m-1 шагов, на каждом из которых в таблице условий задачи заполняют одну клетку, которую называют занятой. Заполнение одной из клеток обеспечивают полностью либо удовлетворение потребности в грузе одного из пунктов назначения.

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

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

          После того как проделаны  m+n-2 описанных выше шагов, получают задачу с одним пунктом отправления и одним пунктом назначения. При этом останется свободной только одна клетка, а запасы оставшегося пункта отправления будут равны потребностям оставшегося пункта назначения. Заполнив эту клетку, тем самым делают (n+m-1)-й шаг и получают искомый опорный план. Следует заметить, что на некотором шаге может оказаться, что потребности очередного пункта назначения равны запасам очередного пункта отправления. В этом случае также временно исключают из рассмотрения либо столбец, либо строку. Т.о. либо запасы данного пункта отправления, либо потребности данного пункта назначения считают равными нулю. Этот ноль записывают в очередную заполняемую клетку. Указанные выше условия гарантируют получение n+m-1 занятых клеток, в которых стоят компоненты опорного плана, что является исходным условием для проверки последнего на оптимальность и нахождения оптимального плана.

Метод северо-западного  угла(СЗУ). При нахождений опорного плана транспортной задачи методом СЗУ на каждом шаге рассматривают 1-ый из оставшихся пунктов отправления и 1-ый из оставшихся пунктов назначения. Заполнение клеток таблицы условий начинается с левой верхней клетки для неизвестного и заканчивается клеткой для неизвестного  т.е. идет как бы по диагонали таблицы.

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

3.Определение  опорного плана  транспортной задачи.

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

        Метод потенциалов.

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

         Для определения опорного плана транспортной задачи будем пользоваться одним из методов. Эти  методы гарантируют получение занятых в исходном плане n+m-1 клеток, причем в некоторых из них могут стоять нули. Полученный план следует проверить на оптимальность.

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

 что

и    

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

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

          Сформулированная теорема позволяет построить алгоритм нахождения решения транспортной задачи. Он состоит в следующем. Пусть одним из рассмотренных выше методов найден опорный план транспортной задачи. Для каждого из пунктов отправления и назначения определяют потенциалы  . Эти числа находят из системы уравнений