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

Постановка задачи линейного программирования. Постановка задачи производственного планирования Построим математическую модель следующей экономической ситуации. Кондитерская фабрика при производстве двух видов карамели «Снежинка» и «Яблочная» - использует три вида основного сырья: сахарный песок, патоку и фруктовое пюре. Запасы сырья составляют соответственно 800 т, 600 т и 120 т. Прибыль от реализации 1 т «Снежинки» составляет 108 ден.ед., а «Яблочной» - 140 ден.ед. На выпуск 1 т «Снежинки» расходуется 0,8 т сахара, 0,2 т патоки и 0,01 т фруктового пюре, а на выпуск 1 т «Яблочной» - соответственно по 0,5 т, 0,4 т и 0,1 т этих видов сырья. Необходимо найти план производства карамели, который даст наибольшую прибыль. Описанная ситуация представляет собой задачу производственного планирования (или задачу об использовании ресурсов). Чтобы построить математическую модель данной ситуации, прежде всего введем переменные, значения которых определяют принимаемое решение. В самом деле, что в данном случае означает «план производства»? Очевидно, следует найти, сколько именно нужно выпускать продукции каждого вида. Обозначим х1 - производство карамели «Снежинка», т; х2 производство карамели «Яблочная», т. Теперь задумаемся о цели данной операции. В данном случае целью является получение как можно более высокой общей выручки или прибыли. Каким образом можно вычислить ее через исходные данные задачи и введенные нами обозначения? Прибыль от производства карамели «Снежинка» составит 108х1 ден.ед. В самом деле, если выпустить 10 т этой карамели (х1=10), то прибыль от нее составит 108*10 = 1080 (ден.ед.), если выпустить 2 т, то 108*2 = 216 (ден.ед.); если вообще не выпускать эту карамель, то и прибыли от нее не будет – 108*0 = 0, и т.д. Аналогично прибыль от «Яблочной» составит 140х2 ден.ед. Общая прибыль представляет собой сумму прибыли от двух видов карамели. Необходимо максимизировать прибыль от всей карамели, т.е. 108х1 + 140х2. Очевидно, что если бы значения переменных могли быть любыми, выручка (или прибыль) могла бы возрасти до бесконечности. Однако это не так, на выпуск продукции наложены некоторые ограничения. Прежде всего, они связаны с ограниченными запасами ресурсов. На 1 т карамели «Снежинка» затрачивается 0,8 т сахарного песка. Следовательно, на х1 т этой карамели будет затрачено 0,8х1 т (т.е. 1,6 т, если выпускается 2 т такой карамели, 80 т, если выпускается 100 т такой карамели, и т.д.). Аналогично на производство карамели «Яблочная» будет затрачено 0,5х2 т сахарного песка. Таким образом, общие затраты сахарного песка составят 0,8х1 + 0,5х2 т. Поскольку его запас составляет 800 т, можно записать: 0,8х1 + 0,5х2 ≤ 800. Аналогично для патоки следует построить ограничение 0,2х1 + 0,4х2 ≤ 600, а для фруктового пюре 0,01х1 + 0,1х2 ≤ 120. Таким образом, построено три ограничения. По смыслу задачи обе переменные неотрицательны: х1 ≥ 0, х2 ≥ 0. Итак, математическую модель можно построить следующим образом: 2 max 108х1 + 140х2 0,8х1 + 0,5х2 ≤ 800 0,2х1 + 0,4х2 ≤ 600 0,01х1 + 0,1х2 ≤120 х1,2 ≥ 0 Все выражения, входящие в запись данной математической модели, представляют собой линейные функции. Построенная модель представляет собой задачу линейного программирования. Основные понятия линейного программирования Задача линейного программирования в общем виде может быть записана следующим образом: max    min  n  ∑ a ijx j  j=1 где Ri n ∑c x j=1 j bi , (1) j i = 1, m (2) R ∈ {≤; ≥; =}; i xj – переменные; aij, bi, cj - константы; n – число переменных; m – число ограничений. Распространенным является случай, когда на все переменные накладываются ограничения неотрицательности, т.е. xj ≥ 0, j = 1, n . При этом, 3 говоря о размерности задачи (числе переменных и ограничений), ограничения на знак переменных обычно не считают. Выражение (1) представляет собой целевую функцию задачи линейного программирования (или функцию цели), которую необходимо максимизировать или минимизировать. Например, для задачи, поставленной в предыдущем разделе, целевой функцией является выражение (108х1 + 140х2) – именно оно отражает цель операции. Выражения (2) представляют собой систему ограничений, которая может состоять из уравнений и нестрогих неравенств. планирования такая В система рассмотренной состояла задаче только производственного из неравенств: трех ограничений по запасам ресурсов и двух ограничений неотрицательности переменных. Любой набор значений переменных, т.е. вектор чисел Х = (x1, x2, . . . xn), называется планом задачи линейного программирования. Например, для той же задачи любые два числа будут представлять собой план. План (10; 20) означает, что х1=10, а х2=20, т.е. выпуск карамели «Снежинка» составит 10 т, а выпуск карамели «Яблочная» - 20 т. План (2000; 1000) означает, что выпуск карамели «Снежинка» составит 2000 т, а выпуск карамели «Яблочная» - 1000 т. План (0; 0) означает, что карамель не будет выпускаться вообще. План (0; -10) означает, что карамель «Снежинка» не выпускается, а выпуск карамели «Яблочная» составит -10 т. Последнее, вообще говоря, очевидно бессмысленно. И т.д. Если в задаче 5 переменных, то любые 5 чисел будут представлять собой план, если 10 переменных, - то любые 10 чисел; и т.д. План, удовлетворяющий системе ограничений, называется допустимым. Чтобы проверить, является план допустимым или нет, необходимо подставить его в систему ограничений. Если при этом все 4 уравнения и неравенства истинны, то план допустимый. Если хотя бы одно ложно, то план – недопустимый. Проверим на допустимость план (10; 20): 0,8х1 + 0,5х2 = 0,8*10 + 0,5*20 = 18 ≤ 800 0,2х1 + 0,4х2 = 0,2*10 + 0,4*20 =10 ≤ 600 0,01х1+0,1х2 = 0,01*10 + 0,1*20 = 2,1 ≤120 х1 = 10 ≥ 0 х2 = 20 ≥ 0 Следовательно, этот план допустимый. Действительно, кондитерская фабрика может выпускать карамель таким образом. При этом будет затрачено всего 18 т сахарного песка, 10 т патоки и 2,1 т фруктового пюре, а в запасе имеется значительно больше. Если проверить на допустимость план (0; 0), в результате будет получена система неравенств: 0 ≤ 800 0 ≤ 600 0 ≤120 0≥0 0≥0 Все эти неравенства истинны. Следовательно, и этот план допустимый. Впрочем, и без того очевидно, что кондитерская фабрика может не выпускать продукцию. Проверим на допустимость план (2000; 1000): 0,8х1 + 0,5х2 = 0,8*2000 + 0,5*1000 = 2100 ≤ 800 0,2х1 + 0,4х2 = 0,2*2000 + 0,4*1000 = 800 ≤ 600 0,01х1+0,1х2 = 0,01*2000 + 0,1*1000 = 120 ≤120 х1 = 2000 ≥ 0 х2 = 1000 ≥ 0 5 Первые два утверждения – ложные. На самом деле, 2100>120, а 800>600. Следовательно, этот план недопустимый (вообще говоря, убедившись, что первое неравенство – ложное, можно было выполнение остальных и не проверять). Итак, мы убедились, что фабрика не может выпускать карамель таким образом, так как ей не хватит для этого сахарного песка и патоки. Если подставить в систему ограничений план (0; -10), то все они выполнятся, кроме последнего ограничения: -10<0. Следовательно, раз хотя бы одно ограничение не выполняется, и этот план недопустимый (выпустить -10 т карамели невозможно). Вся совокупность допустимых планов представляет собой область допустимых планов (ОДП) задачи. Допустимый план, на котором достигается максимальное или минимальное значение целевой функции, называется оптимальным планом, а само это значение - оптимумом задачи. Для рассмотренной задачи оптимальным планом будет такой допустимый план производства карамели, который позволит получить наибольшую прибыль. Сама эта величина прибыли – самая высокая, какую только можно получить, - будет представлять собой оптимум. Следует отметить, что оптимальных планов в задаче может быть более одного, но значение целевой функции на них должно быть одинаковым, т.е. оптимум всегда один. Например, в задаче производственного планирования иногда можно найти разные способы произвести продукцию таким образом, чтобы прибыль (или выручка) были максимальными. Но все они дадут одну и ту же – максимальную – величину прибыли. 6 Таким образом, с точки зрения изучаемой дисциплины употребление таких словосочетаний, как «самый оптимальный» или «наиболее оптимальный», является неграмотным. Слово «оптимальный» не сочетается со словами «самый», «наиболее», «очень» и т.п., как любое прилагательное в превосходной степени (нельзя сказать «самый наилучший»). На самом деле, такое выражение просто бессмысленно – ведь если некоторый план действий – «самый оптимальный», значит, есть и другие оптимальные планы, «менее оптимальные», чем он. Но раз они чем-то хуже, значит, они оптимальными не являются. Можно доказать, что если оптимальный план существует, то он либо единственный, либо их бесконечно много*; любая смесь (взвешенная сумма) оптимальных планов является оптимальным планом. Решить задачу линейного программирования означает найти все ее оптимальные планы и оптимум, хотя часто ограничиваются нахождением одного из возможных решений. Если задача линейного программирования не имеет решений, необходимо установить причину ее неразрешимости. Это может быть одна из двух причин: − ее ОДП пуста (т.е. система ограничений несовместна), − целевая функция не ограничена на ОДП (т.е. ее значение можно увеличивать или уменьшать до бесконечности). Задачи линейного программирования, как экономико-математические модели, находят очень широкое применение. Рассмотренная выше задача производственного планирования представляет собой лишь одну из возможных экономических программирования, * наиболее интерпретаций задачи традиционную. Множество линейного других За исключением задач, в которых переменные могут принимать только целые значения. 7 экономических ситуаций может быть описано в тех же математических терминах, что делает возможным применение к их решению одного и того же математического аппарата. Для того чтобы построить математическую модель экономической ситуации в виде задачи линейного программирования, прежде всего необходимо ввести переменные задачи. Они должны быть введены таким образом, чтобы их значения определяли принимаемое решение (получив значения переменных, мы получаем ответ на поставленный вопрос). Затем определяют цель, критерий эффективности операции, ту величину, которую необходимо экстремизировать в задаче. Ее выражают через введенные переменные - получают линейное выражение для целевой функции. После этого необходимо установить, чем ограничивается рост или уменьшение целевой функции, т.е. определить ограничения задачи. Их нужно также выразить через переменные и записать в виде системы уравнений и неравенств. Кроме того, при построении модели полезно воспользоваться следующими рекомендациями. При определении переменных следует заранее обдумать, позволят ли они отразить в модели все условия задачи (если известно, что нет избыточных условий). В конкретной задаче указывают единицы измерения для переменных. Если в исходных данных задачи одна и та же величина измеряется в различных единицах (например, масса в граммах, килограммах, тоннах), то необходимо перевести эти данные в одни и те же единицы измерения. Выражая целевую функцию и ограничения через переменные, следует проверить, какими единицами будут измеряться полученные величины и не являются ли они бессмысленными с экономической точки зрения (например, не измеряются ли левая и правая части ограничений в разных единицах). Отдельно следует обдумать ограничения на знак переменных. 8 В некоторых задачах переменные могут принимать только целые значения. Этот факт также необходимо записать в виде ограничения: Х∈Z. Такое ограничение выводит поставленную задачу из класса задач линейного программирования в класс задач целочисленного линейного программирования. Однако, рассмотренных здесь понятий достаточно для того, чтобы построить математическую модель и для целочисленной задачи. Приведем некоторые примеры экономических задач, математические модели которых можно построить в виде задач линейного программирования. Следует отметить, что здесь будут рассмотрены далеко не все такие задачи; а кроме того, даже те, что рассмотрены, существуют в разнообразных модификациях, и классификация этих задач в большой мере условна, различается у разных авторов. Студентам предлагается самостоятельно изучить примеры постановки задачи о диете (о составлении рациона, о смеси), задачи о раскрое материалов, задачи о загрузке транспорта и др. Формы записи задачи линейного программирования Формулы (1) и (2) описывают задачу линейного программирования в смешанной форме. Кроме того, существует несколько специальных форм записи таких задач. Задачу с неотрицательными переменными, все остальные ограничения которой имеют форму уравнений, будем называть канонической формой записи задачи линейного программирования: Любая задача в смешанной форме может быть приведена к канонической. Это делается путем введения неотрицательных дополнительных переменных, которые прибавляются к левой части неравенства либо вычитаются из нее (после этого знак неравенства заменяют 9 на «равно»). Дополнительные переменные представляют собой разность между частями неравенства. Неотрицательности переменных добиваются заменой неограниченных по знаку переменных на разность двух неотрицательных. Подробнее этот материал рекомендуется изучить самостоятельно. Задачу с неотрицательными переменными, все остальные ограничения которой имеют форму неравенств одного знака (≤, если задача на максимум, и ≥, если на минимум), будем называть стандартной формой записи задачи линейного программирования. Любая задача в смешанной форме может быть приведена к любой из стандартных форм. Подробнее этот материал рекомендуется изучить самостоятельно. Если задача линейного программирования приведена к стандартной или канонической форме, ее удобно кратко записать в матричной форме. 10