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

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

Построим математическую модель следующей экономической ситуации.

Модель в общем виде   Предприятие выпускает n видов продукции, которая реализуется по ценам cj, . Продукция выпускается из m видов ресурсов, которые имеются в наличии в количествах bi, .	Пример   Кондитерская фабрика при производстве двух видов карамели (n = 2) - «Снежинка» и «Яблочная» - использует три вида основного сырья (m = 3): сахарный песок, патоку и фруктовое пюре. Запасы сырья составляют соответственно 800 т, 600 т и 120 т (b1 = 800, b2 = 600, b3 = 1200). Прибыль от реализации 1 т «Снежинки» составляет 108 руб., а «Яблочной» - 140 руб. (c1 = 108, c2 = 140).
Заданы нормы затрат ресурсов - аij - количество i-го вида ресурса, расходуемого на производство единицы j-го вида продукции.	На выпуск 1 т «Снежинки» расходуется 0,8 т сахара, 0,2 т патоки и 0,01 т фруктового пюре, а на выпуск 1 т «Яблочной» - соответственно по 0,5 т, 0,4 т и 0,1 т этих видов сырья (a11 = 0,8; a12 = 0,5; …; a32 = 0,1)*.

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

Необходимо найти план производства карамели, максимизирующий прибыль.

Описанная ситуация представляет собой задачу производственного планирования (или задачу об использовании ресурсов). Чтобы построить математическую модель данной ситуации, прежде всего введем переменные, значения которых определяют принимаемое решение. В самом деле, что в данном случае означает «план производства»? Очевидно, следует найти, сколько именно нужно выпускать продукции каждого вида.

Обозначим хj - выпуск j-го вида продукции.

Обозначим х1 - производство карамели «Снежинка», т; х2 - производство карамели «Яблочная», т.

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

Если от одной единицы j–го вида продукции выручка составит cj, и предприятие выпускает хj этого вида продукции, то прибыль от всей такой продукции составит cjxj.	Общая прибыль от производства карамели «Снежинка» составит 108х1 руб. В самом деле, если выпустить 10 т этой карамели (х1=10), то прибыль от нее составит 108*10 = 1080 (руб.), если выпустить 2 т, то 108*2 = 216 (руб.); если вообще не выпускать эту карамель, то и прибыли от нее не будет – 108*0 = 0, и т.д. Аналогично прибыль от «Яблочной» составит 140х2 руб.
Если просуммировать эти произведения по всем видам продукции, будет получена общая выручка . Именно ее следует максимизировать.	Общая прибыль представляет собой сумму прибыли от двух видов карамели. Необходимо максимизировать прибыль от всей карамели, т.е. 108х1 + 140х2.

Очевидно, что если бы значения переменных могли быть любыми, выручка (или прибыль) могла бы возрасти до бесконечности. Однако это не так, на выпуск продукции наложены некоторые ограничения. Прежде всего, они связаны с ограниченными запасами ресурсов.

Если на одну единицу j–го вида продукции затрачивается аij ресурса i-го вида, и предприятие выпускает хj этого вида продукции то на всю такую продукцию пойдет аijхj ресурса i-го вида. Просуммировав эти величины по всем видам продукции, можно получить совокупные затраты i-го ресурса - аijхj, которые не должны превышать его запас: аijхj £ bi.	На 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. Таким образом, построено три ограничения.
Кроме того, очевидно, что выпуск продукции не может быть отрицательной величиной: хj ³ 0, j=1,n.	По смыслу задачи обе переменные неотрицательны: х1 ³ 0, х2 ³ 0.

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

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

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

Основные понятия линейного программирования

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

где ;

x_j – переменные;

a_ij, b_i, c_j - константы;

n – число переменных;

m – число ограничений.

Распространенным является случай, когда на все переменные накладываются ограничения неотрицательности, т.е. x_j ³ 0, . При этом, говоря о размерности задачи (числе переменных и ограничений), ограничения на знак переменных обычно не считают.

Выражение (1) представляет собой целевую функцию задачи линейного программирования (или функцию цели), которую необходимо максимизировать или минимизировать. Например, для задачи из раздела 1.1 целевой функцией является выражение (108х₁ + 140х₂) – именно оно отражает цель операции. Выражения (2) представляют собой систему ограничений, которая может состоять из уравнений и нестрогих неравенств. В задаче производственного планирования из раздела 1.1 такая система состояла только из неравенств: трех ограничений по запасам ресурсов и двух ограничений неотрицательности переменных.

Любой набор значений переменных, т.е. вектор чисел Х = (x₁, x₂,... x_n), называется планом задачи линейного программирования. Например, для то же задачи любые два числа будут представлять собой план. План (10; 20) означает, что х₁=10, а х₂=20, т.е. выпуск карамели «Снежинка» составит 10 т, а выпуск карамели «Яблочная» - 20 т. План (2000; 1000) означает, что выпуск карамели «Снежинка» составит 2000 т, а выпуск карамели «Яблочная» - 1000 т. План (0; 0) означает, что карамель не будет выпускаться вообще. План (0; -10) означает, что карамель «Снежинка» не выпускается, а выпуск карамели «Яблочная» составит -10 т. Последнее, вообще говоря, очевидно бессмысленно. И т.д. Если в задаче 5 переменных, то любые 5 чисел будут представлять собой план, если 10 переменных, - то любые 10 чисел; и т.д.

План, удовлетворяющий системе ограничений, называется допустимым. Чтобы проверить, является план допустимым или нет, необходимо подставить его в систему ограничений. Если при этом все ограничение и неравенства истинны, то план допустимый. Если хотя бы одно ложно, то план – недопустимый.

Проверим на допустимость план (10; 20):

0,8х₁ + 0,5х₂ = 0,8*10 + 0,5*20 = 18 £ 800

0,2х₁ + 0,4х₂ = 0,2*10 + 0,4*20 =10 £ 600

0,01х₁+0,1х₂ = 0,01*10 + 0,1*20 = 2,1 £120

х₁ = 10 ³ 0

х₂ = 20 ³ 0

Следовательно, этот план допустимый. Действительно, кондитерская фабрика может выпускать карамель таким образом. При этом будет затрачено всего 18 т сахарного песка, 10 т патоки и 2,1 т фруктового пюре, а в запасе имеется значительно больше.

Если проверить на допустимость план (0; 0), в результате будет получена система неравенств:

0 £ 800

0 £ 600

0 £120

0 ³ 0

0 ³ 0

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

Проверим на допустимость план (2000; 1000):

0,8х₁ + 0,5х₂ = 0,8*2000 + 0,5*1000 = 2100 £ 800

0,2х₁ + 0,4х₂ = 0,2*2000 + 0,4*1000 = 800 £ 600

0,01х₁+0,1х₂ = 0,01*2000 + 0,1*1000 = 120 £120

х₁ = 2000 ³ 0

х₂ = 1000 ³ 0

Первые два утверждения – ложные. На самом деле, 2100>120, а 800>600. Следовательно, этот план недопустимый (вообще говоря, убедившись, что первое неравенство – ложное, можно было выполнение остальных и не проверять). Итак, мы убедились, что фабрика не может выпускать карамель таким образом, так как ей не хватит для этого сахарного песка и патоки.

Если подставить в систему ограничений план (0; -10), то все они выполнятся, кроме последнего ограничения: -10<0. Следовательно, раз хотя бы одно ограничение не выполняется, и этот план недопустимый (выпустить -10 т карамели невозможно).

Вся совокупность допустимых планов представляет собой область допустимых планов (ОДП) задачи.

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

Для задачи из раздела 1.1 оптимальным планом будет такой допустимый план производства карамели, который позволит получить наибольшую прибыль. Сама эта величина прибыли – самая высокая, какую только можно получить, - будет представлять собой оптимум.

Следует отметить, что оптимальных планов в задаче может быть более одного, но значение целевой функции на них должно быть одинаковым, т.е. оптимум всегда один. Например, в задаче производственного планирования иногда можно найти разные способы произвести продукцию таким образом, чтобы прибыль (или выручка) были максимальными. Но все они дадут одну и ту же – максимальную – величину прибыли.

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

Можно доказать, что если оптимальный план существует, то он либо единственный, либо их бесконечно много*; любая смесь (взвешенная сумма) оптимальных планов является оптимальным планом.

Решить задачу линейного программирования означает найти все ее оптимальные планы и оптимум, хотя часто ограничиваются нахождением одного из возможных решений. Если задача линейного программирования не имеет решений, необходимо установить причину ее неразрешимости. Это может быть одна из двух причин:

- ее ОДП пуста (т.е. система ограничений несовместна),

- целевая функция неограничена на ОДП (т.е. ее значение можно увеличивать или уменьшать до бесконечности).