Решение задач о планировании перевозок — страница 4

  • Просмотров 228
  • Скачиваний 7
  • Размер файла 58
    Кб

носит название целевой функции. Ставится задача: найти экстремум (максимум или минимум) целевой функции f(x) при условии, что переменные x принадлежат некоторой области G: В зависимости от вида функции f(x) и области G и различают разделы математического программирования: квадратичное программирование, выпуклое программирование, целочисленное программирование и т.д. Линейное программирование характеризуется тем, что а) функция f(x)

является линейной функцией переменных х1 , х2 , … хn б) область G определяется системой линейных равенств или неравенств. Математическая модель любой задачи линейного программирования включает в себя: максимум или минимум целевой функции (критерий оптимальности); систему ограничений в форме линейных уравнений и неравенств; требование неотрицательности переменных. Пример В других ситуациях могут возникать задачи с большим

количеством переменных, в систему ограничений которых, кроме неравенств, могут входить и равенства. Потому в наиболее общей форме задачу линейного программирования формулируют следующим образом: (2.4) (2.5) (2.6) Коэффициенты ai,j, bi, cj, j = 1, 2, ... , n, i =1, 2, ... , m – любые действительные числа (возможно 0). Итак, решения, удовлетворяющие системе ограничений (2.4) условий задачи и требованиям неотрицательности (2.5), называются допустимыми, а

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

максимум (минимум) некоторой линейной функции F, ее система ограничений состоит только из равенств (уравнений). При этом переменные задачи х1, х2, ..., хn являются неотрицательными: (2.7) (2.8) (2.9) К канонической форме можно преобразовать любую задачу линейного программирования. Правило приведения ЗЛП к каноническому виду: Если в исходной задаче некоторое ограничение (например, первое) было неравенством, то оно преобразуется в

равенство, введением в левую часть некоторой неотрицательной переменной, при чем в неравенства «≤» вводится дополнительная не отрицательная переменная со знаком «+»; в случаи неравенства «≥» - со знаком «-» (2.10) Вводим переменную . Тогда неравенство (2.10) запишется в виде: (2.11) В каждое из неравенств вводится своя “уравнивающая” переменная, после чего система ограничений становится системой уравнений. 2. Если в исходной задаче