Математическое программирование

     а) Если одна из пары двух задач (1)-(3) или (4)-(6) имеет оптимальный план, то и другая имеет оптимальный план. Причем .

     б) Если целевая функция одной из двойственных задач не ограничена (для  задач (1)-(3) сверху, а для задач (4)-(6) снизу), то другая задача не имеет планов. 

     Теорема (Вторая теорема двойственности).

     а) Если оптимальный план Х⁰ задачи L₁ обращает i-е ограничение системы S₁ (2) в строгое неравенство, то соответствующая ему переменная у_i в оптимальном плане У двойственной задачи L₁⁺ обращается в 0.

     б) Если в оптимальном плане Х⁰ задачи L₁ переменная х_i>0 (положительна), то соответствующее ей ограничение задачи  на ее оптимальном плане У⁰ обращается в верное равенство. 

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

 

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

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

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

     Задача. В цехе решено установить дополнительное оборудование, для которого выделено 19/3 кв.м площади. На приобретение оборудования двух типов предприятие может выделить 10 тысяч рублей.

     Комплект  оборудования 1-го типа стоит 1000 рублей, 2-го типа – 3000 рублей.

     Приобретение  одного комплекта оборудования 1-го типа позволит увеличить выпуск продукции  на 2 единицы в смену, 2-го типа –  на 4 единицы в смену.

     Для установки оборудования 1-го типа необходимо 2 кв.м площади, 2-го типа – 1 кв.м площади.

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

     Решение. Составим математическую модель задачи. Пусть предприятие приобретет Х₁ комплектов оборудования 1-го типа, Х₂ – 2-го типа.

     Тогда                  (1)

                                    (2) общее увеличение выпуска продукции

                                     (3) экономическое содержание переменных

      - целые,                             (4) 

     Математическая  постановка задачи: найти максимальное значение функции (2) при выполнении условий (1), (3), (4). Т.к. х₁, х₂ могут быть только целыми, то это задача целочисленного программирования.

     Решим задачу геометрическим способом:

                                                                                                                                                    

     Многоугольник ОАВС – многоугольник решений, т.к. координаты всех его точек удовлетворяют условиям (1), (3). А условию целочисленности удовлетворяют только 12 точек.

     Многоугольник OKEMNF – координаты всех его точек удовлетворяют условиям (4) целочисленности х₁, х₂. Максимальное значение функции цели F_max(1;3)=2*1+4*3=14/

     Координаты  точки Е определяют оптимальный  план задачи. Таким образом, предприятию следует дополнительно приобрести 1 комплект оборудования 1-го типа, и 3 комплекта оборудования 2-го типа, что обеспечит при ограниченных производственных площадях и денежных средствах максимальное увеличение выпуска продукции, равное 14 единиц в смену. 
 
 

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

     В общем виде задачу можно записать следующим образом:

     Найти максимум функции

                                          (6)

     при условиях

                     (7)

                               (8)

      - целые                                       (9) 

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

     Задача.

     Найти максимальное значение функции  (1)

     При условиях           (2)

                                         (3)

                                  (4) 

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

     Решение. Сначала найдем оптимальный план задачи (1)-(3) без (4) симплекс-методом. х₃, х₄, х₅ – базисные переменные. 

 

     Найден  оптимальный план X(19/2, 7/2, 0, 0, 34) задачи (1)-(3), но он не является оптимальным планом целочисленного программирования (1)-(4), т.к. переменные х₁ и х₂ – не являются целыми значениями. Дробные части их равны, поэтому для одной из них составляется дополнительное ограничение. Составим ограничение для переменной х₂.

     Из  последней таблицы

     

     Откуда  следует дополнительное условие

     

     где f – положительные дробные части чисел после отбрасывания целой части ½

                              (5)

     Найдем  максимальное значение функции (1) при  условиях (2), (3), (5). 

 

     Выбирается  наименьшее по абсолютной величине отношение  элементов строки F к элементам разрешающей строки.

     X⁰(9;4;0;1;32)

     F⁰_max=35

     Решим задачу геометрически 

     

     X_c(19/2,7/2,0,0,34)

     Многоугльник  ОАВСД – многоугольник решений  задачи (1)-(3). Максимум достигается в  точке С(19/2, 7/2). Для задач (1)-(4) вводится дополнительное ограничение  .

     Найдем  x₃ из первого ограничения

     Из  второго ограничения найдем х₄:

     

     X_E(9, 4, 0, 1, 32) 

     Таким образом область допустимых решений  – многоугольник OABEFD. В точке Е(9;4) этого многоугольника целевая функция достигает максимального значения. Т.к. координаты точки Е целые и неизвестные x₃, x₄, x₅ принимают целочисленные значения при подстановке в систему (2), х₁=9, х₂=4.

     Таким образом Х⁰(9;4;0;1;32) является оптимальным планом задачи (1)-(4).

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

1. Используя симплекс-метод, находят решения задачи (6)-(8) без учета требования целочисленности переменных.
2. Составляют дополнительные ограничения для переменной, которая в оптимальном плане задач (6)-(8) имеет максимальную дробную часть числа, а в оптимальном плане задач (6)-(9) эта переменная должна быть целочисленной.
3. Используя двойственный симплекс-метод, находим решение задачи, получающейся из задач (6)-(8) в результате присоединения дополнительного ограничения.
4. В случае необходимости составляют еще одно дополнительное ограничение и продолжают итерационны процесс до получения оптимального плана задачи (6)-(9) или установления ее неразрешимости.

 

7. Транспортная задача. 

7.1 Общая постановка задачи. 

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