Конспект лекций по курсу «Математическое программирование»

внедрение результата решения в практику.

Под экономико-математической моделью понимается система математических соотношений, описывающих экономический процесс.

Построим экономико-математическую модель задачи об использовании оборудования.

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

 max

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

 

 

2.2. Задача  об использовании сырья.

 

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

Предприятие выпускает  продукцию n видов  , на изготовление которой расходуется сырье m видов , запасы которого на предприятии равны соответственно . Известны расходы сырья S_i на производство единицы продукции (i = ; j = ). Стоимость единицы продукции равна (j = ). Требуется составить такой план выпуска продукции, при котором выручка от реализации продукции была бы наибольшей.

Составим математическую модель задачи.

Пусть - количество единиц продукции (j = ).

Математическая модель имеет  вид:

f =

→  max

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

                                         ( 2.0)

 

2.3. Задача  составления рациона (задача о диете).

 

Для откорма  животного используется n видов кормов, содержащих m видов питательных веществ. Пусть - содержание i- го питательного вещества в одном килограмме j - го вида корма - стоимость одного килограмма j-ro вида корма Минимальная суточная потребность животного в  i-ом питательном веществе равна . Необходимо составить наиболее дешевый рацион нужной питательности.

Обозначим через  x_j количество килограммов корма j-го вида.

 Очевидно, математическая  модель задачи такова.

f =

→  min

 

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

2.4. Общая  постановка задачи линейного программирования

 

Линейным  ограничением, наложенным на переменные , называется соотношение одного из следующих трех типов: 

где - действительные числа.

Например, соотношения  2х - ≤ 1  или ≥ 0 являются

линейными, а   соотношения    ≥ 3  или sin x₁ ≤ не являются линейными.                                                                                             

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

 

Дана некоторая  линейная функция

f =

n                                                             (2.1)

и некоторая  система линейных ограничений, наложенных на переменные :

                                                       (2.2)

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

удовлетворяли бы ограничениям (2.2) и при этом условии  обращали бы в оптимум (max и min) функцию (2.1).

Функция (2.1) называется целевой. Каждый набор значений переменных, при которых удовлетворяются ограничения (2.2), называется допустимым решением или допустимым планом ЗЛП. Совокупность  всех  допустимых  решений называется  областью допустимых решений (ОДР).

Приведенные  в  параграфах  2.1,   2.2,   2.3  задачи являются, очевидно, задачами линейного программирования.

Допустимое решение, обращающее целевую функцию в оптимум, называется оптимальным решением или оптимальным планом.

Говорят, что ЗЛП разрешима, если она имеет оптимальный план. В противном случае задача называется неразрешимой.

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

а)  ОДР пуста;

б)  ОДР непуста, но целевая функция  не ограничена на ОДР сверху, если в  ЗЛП ищется ее максимум, или - не ограничена снизу, если в ЗЛП ищется минимум  целевой функции.        

Например, задача: f = min

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

                                

неразрешима из-за пустоты ОДР.

Задача же  f = max  при ограничениях

 неразрешима из-за того, что  целевая функция не ограничена  сверху на ОДР. (Чтобы убедиться в этом, рассмотрите такие допустимые решения : и т.д.).

 

2.5. Геометрический  метод решения ЗЛП.

 

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

          Пример 1

  f = max

Каждое допустимое решение ЗЛП будем изображать точкой координатной плоскости. Построим ОДР (рис. 2.1). Рассмотрим первое линейное ограничение . Совокупность точек плоскости, удовлетворяющих этому ограничению, представляет собой полуплоскость, ограниченную прямой . Сначала построим эту граничную прямую (ее можно построить по двум точкам: (0,6) и (9,0). Эта прямая разобьет плоскость на две полуплоскости. Чтобы решить вопрос о том, какую из этих двух полуплоскостей определяет неравенство , возьмем в одной из полуплоскостей какую-либо точку, не лежащую на граничной прямой, и подставим ее координаты в неравенство. Например, в качестве такой точки возьмем начало координат - точку (0,0). Поскольку , то полуплоскость, определяемая неравенством , содержит точку (0,0). Аналогично находим полуплоскости, определяемые остальными ограничениями. Далее определим ОДР как общую часть полученных полуплоскостей. Получим выпуклый многоугольник

 

рис.2.1.

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

f = ,то каждая линия уровня имеет вид . Видим, что при различных значениях параметра С получаются параллельные прямые. Построим, например, две линии уровня, положив С = 4 и С = 8. Отметим стрелкой направление, в котором перемещается линия уровня при увеличении С. Передвигая линию уровня в указанном направлении, найдем точку ОДР, в которой С имеет наибольшее значение. Это будет точка А. Она является результатом пересечения двух прямых: и

Для нахождения координат  точки А решим систему

Получим  оптимальное  решение

 

Пример 2.  f = min

 

       

рис. 2.2.

 

В этом примере полуплоскости, определяемые линейными ограничениями, не имеют общих точек. Поэтому  ЗЛП неразрешима из-за пустоты ОДР.

Пример 3. f =

В данном примере   (рис.2.3) ОДР - выпуклая неограниченная многоугольная область.

 

рис. 2.3.

 

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

 

 

 

Пример 4.  f =

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

Например,

Пример 5.  Решим геометрически задачу об использовании

оборудования,  которая рассматривалась в параграфе 2.1. Ее математическая модель

  f =

Построим ОДР (рис 2.4).  Затем проведем линию  уровня . Укажем стрелкой направление, в котором перемещается линия уровня с ростом C. Максимум целевой функции на ОДР достигается в точке А. Для отыскания координат точки А решим систему:

 

 

рис.2.4.

 

Отсюда 

Ответ. Оптимальный  план таков: изделий А нужно производить 7,5 единиц, изделий В -5 единиц; при  этом прибыль будет равна 80 денежным единицам.

Геометрический метод  можно использовать для решения  ЗЛП с числом переменных n = 3. При  большем числе переменных ЗЛП не допускает наглядного геометрического решения. Вместе с тем для произвольного числа переменных справедливы утверждения:

1)  область  допустимых решений представляет  собой выпуклый  многогранник;

2) если ЗЛП разрешима,  то оптимальное решение достигается в одной из вершин выпуклого многогранника.

 

2.6. Канонический  вид ЗЛП.

 

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

Для единообразия записи ЗЛП вводится так называемая каноническая форма записи.

Говорят, что ЗЛП записана в канонической форме, если она имеет  следующий вид:

                                        (2.3)

                                  

Отметим следующие особенности  канонического вида:

     1)   требуется минимизировать целевую  функцию;

     2)    все   линейные   ограничения,  кроме   требований неотрицательности переменных, имеют вид равенств;

3. на все переменные наложены требования неотрицательности.

Покажем, что  любую ЗЛП можно привести к  каноническому виду.

1) Если в ЗЛП  требуется максимизировать целевую  функцию f, то положим g = - f и потребуем минимизировать функцию g. Получится новая ЗЛП, которая эквивалентна исходной в том смысле, что каждое оптимальное решение исходной задачи будет оптимальным решением новой задачи и наоборот.

2)  Предположим,  что в ЗЛП есть линейное  ограничение вида

. Заменим такое ограничение  следующими двумя ограничениями:

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

Аналогично, ограничение  вида заменяется двумя ограничениями:

3) Предположим,  что в ЗЛП не ко всем переменным  предъявлено требование неотрицательности. Тогда каждую, переменную , на которую не наложено требование неотрицательности, представим в виде разности двух неотрицательных переменных:

                                               (2.6)

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

Указанными приемами любая ЗЛП  приводится к каноническому виду.

 

Пример. Привести к каноническому виду

Проделаем описанные действия.

Теперь получим ЗЛП  в каноническом виде:

 

 

2.7. Понятие опорного плана ЗЛП.

 

Пусть ВЛП задана в  каноническом виде (2.3 - 2.5). Предположим, что система уравнений (2.4) приведена  к жордановой форме с неотрицательными правыми частями:

                (2.6)

где .

Приравняв к  нулю свободные переменные, получим  базисное решение системы (2.4)

                         (2.7)

В силу условия  набор значений переменных (2.7) удовлетворяет и ограничениям (2.5). Поэтому (2.6) является допустимым решением ЗЛП.

Допустимое  решение (2.7) называется базисным допустимым решением или опорным планом ЗЛП.  При этом говорят, что переменные образуют допустимый базис.

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

Если ЗЛП  разрешима, то существует оптимальный  опорный план.

 

3. СИМПЛЕКСНЫЙ  МЕТОД РЕШЕНИЯ ЗЛП

 

3.1. Общая  характеристика и основные этапы  симплекс – метода

 

Основоположниками симплекс-метода являются советский  математик Л.В. Канторович и американский математик Дж. Данциг.

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