Исследование операций

(1.1)

 Кроме того очевидно, что все переменные  неотрицательны, т.е. ... (1.2) Пусть стоимость единицы веса i-го продукта равна .<Тогда весь наш рацион будет стоить (1.3) <

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

(1.4)

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

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

Для понимания всего дальнейшего  полезно знать и представлять себе геометрическую интерпретацию  задач линейного программирования, которую можно дать для случаев  n =2 и n =3.

Наиболее наглядна эта  интерпретация для случая n =2, т.е. для случая двух переменных и . Пусть нам задана  задача линейного программирования в стандартной форме  

(1.19)

Возьмём на плоскости декартову  систему координат и каждой паре чисел  поставим в соответствие точку на этой плоскости.

Обратим прежде всего внимание на ограничения и . Они из всей плоскости вырезают лишь её первую четверть (см. рис. 1). Рассмотрим теперь, какие области соответствуют неравенствам вида .

 Пусть  . Если взять , то получится . Если взять , то получится . Таким образом, на прямой лежат две точки и . Дальше через эти две точки можно по линейке провести прямую линию (рисунок 2).

Если же b=0, то на прямой лежит точка (0,0). Чтобы найти другую точку, можно взять любое отличное от нуля значение и вычислить соответствующее ему значение  .

Эта построенная прямая разбивает  всю плоскость на две полуплоскости. В одной её части  , а в другой наоборот . Узнать, в какой полуплоскости какой знак имеет место проще всего посмотрев, какому неравенству удовлетворяет какая-то точка плоскости, например, начало координат, т.е. точка (0,0).

Глава 2. Симплекс-метод

2.1. Выпуклые множества  и многогранники 

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

Рассмотрим n - мерное евклидово пространство  и пусть - точка в этом пространстве.

Рассмотрим две точки  и , принадлежащие . Множество точек , которые могут быть представлены в виде (в координатах это записывается так:

,называется выпуклой комбинацией  точек  и , или отрезком, соединяющим точки и . Сами точки и   называются концами отрезка. В случаях n =2 и n =3 это - отрезок в обычном понимании этого слова на плоскости или в пространстве (см. рис. 12). Заметим, что при l =0 , а при l =1 , т.е. при l =0 и l =1 получаются концы отрезка.

 Пусть в  заданы k точек . Точка , где все и называется выпуклой комбинацией точек .

Пусть есть некоторая область в пространстве (другими словами, G есть некоторое множество точек из  ).

Определение. Множество (область) называется выпуклым, если из того, что и следует, что для l Î [0,1].  Другими словами, G - выпуклое множество, если оно, вместе с любыми двумя своими точками, содержит в себе отрезок, соединяющий эти точки.

На этих рисунках "а" и "б" - выпуклые множества, а "в" не является выпуклым множеством, так  как в нём есть такая пара точек, что соединяющий их отрезок не весь принадлежит этому множеству.

 

Теорема 1. Пусть G - выпуклое множество. Тогда любая выпуклая комбинация точек, принадлежащих этому множеству, также принадлежит этому множеству.

Доказательство Пусть  - точки, принадлежащие множеству G .

Докажем теорему методом  математической индукции. При k =2 теорема верна, так как она просто переходит в определение выпуклого множества.

Пусть теорема верна для  некоторого k. Возьмём точку и рассмотрим выпуклую комбинацию

,где все   и  .

Представим  в виде

Но коэффициенты  и ,

и, раз мы считаем, что  для k теорема верна, точка .

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

Теорема доказана.

 

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

Доказательство.

В стандартной форме в  матричных обозначениях допустимая область G определяется условием

Пусть  и .   принадлежат G , т.е. .

 Но тогда для   имеем

т.е. x принадлежит G и, следовательно, выпукло.

В канонической форме область  G определена условиями

Пусть  и   принадлежат G, т.е.

.Но тогда для   имеем

т.е. и, следовательно, G выпукло. Теорема доказана.

 Таким образом, допустимая  область в задаче линейного  программирования является выпуклым  множеством. По аналогии с двумерным  или трехмерным случаями, при  любом n эту область называют выпуклым многогранником в n - мерном пространстве  . 

Теорема 3. Множество оптимальных  планов задачи линейного программирования выпукло (если оно не пусто).

Доказательство

Если решение задачи линейного  программирования единственно, то оно  выпукло по определению - точка считается  выпуклым множеством Пусть теперь  и  два оптимальных плана задачи линейного  программирования. Тогда   и .

Рассмотрим  . В силу выпуклости области

допустимых значений, . Но для этого плана

т.е. есть также оптимальный план и, в силу этого, множество оптимальный планов выпукло. Теорема доказана.

Теорема 4. Для того, чтобы задача линейного программирования имела решение, необходимо и достаточно, чтобы целевая функция на допустимом множестве была ограничена сверху (при решении задачи на максимум) или снизу (при решении задачи на минимум).

 

Глава 3. Двойственные задачи

3.1. Постановка  двойственных задач

Симметричные двойственные задачи

Рассмотрим задачу линейного  программирования в стандартной  форме

   (1)

или, в матричной форме,  

(2)

Рассмотрим теперь следующую  задачу

  (3)

или, в матричной форме,  

(4)

Пара задач (1) и (3) (или, в  матричной форме, пара задач (2) и (4) ) называются двойственными друг другу задачами в симметричной форме.

Несимметричная двойственная задача

Исходная задача  имеет  вид:

  (5)

или, в матричной форме,  

(6)

Двойственная задача в  несимметричной форме имеет вид

(7)

или, в матричной форме,

 (8)

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

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

Экономическая интерпретация  двойственной задачи в симметричной форме

Исходная задача:

Обычно эта задача связывается  с задачей максимизации дохода при  производстве некоторой продукции  при наличии ограничений на ресурсы. Коэффициенты имеют смысл дохода от единицы продукции j-го ресурса, — количество единиц продукции j-го вида. Коэффициенты имеют смысл затрат i-го ресурса на производство продукции j-го типа. Что же представляет двойственная задача по своему смыслу?

Целевая функция двойственной задачи:,

а ограничения: , где (1) — затраты i-го ресурса на производство единицы продукции j-го типа, а (2) — доход от продажи единицы продукта i-го типа. Поэтому в целевой функции на месте (?)получаем смысл стоимости всех ресурсов, т. е. Задача приобретает смысл: , при ограничениях: , где

(3) — запасы i-го ресурса;

(4) — стоимость единицы i-го ресурса;

(5) — общая стоимость всех ресурсов;

(6) — запасы i-го ресурса на производство единицы продукции j-го типа;

(7) — цена единицы i-го ресурса;

(8) — доход от продажи единицы продукции i-го вида.

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

Исходная задача. Сколько  единиц продукции каждого вида надо выпустить при доходе от продукции единицы j-го типа при имеющихся запасах каждого из ресурсов  , чтобы получить максимальный доход?

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

Переменные  называется по-разному. Часто их называют учетными, неявными или фиктивными ценами.

 

Глава 4. Транспортная задача

4.1. Постановка  задачи 

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

Начнем с её содержательной формулировки.

Пусть имеется некоторый  однородный продукт, сосредоточенный  на m пунктах отправления (складах), так что на i-м складе находится единиц этого продукта.

Этот продукт необходимо доставить в n пунктов назначения (потребления), причем на j-й пункт необходимо доставить единиц продукта. Запасы и потребности сбалансированы, то есть

то есть наличие продукта равно потребности в нем.

Пусть стоимость перевозки  единицы продукта из i-го склада в j-й пункт назначения равна . Пусть есть то количество продукта, которое перевозится из i-го склада в j-й пункт потребления.

Тогда общие транспортные расходы составят величину

Из каждого склада весь продукт должен быть вывезен. Это  значит, что должно быть выполнено  условие

С другой стороны, потребности  j-го пункта назначения должны быть полностью удовлетворены. Это означает, что

Желание минимизировать транспортные расходы приводит нас к следующей  задаче:

 

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

Определение 3.1. Транспортная задача называется открытой транспортной задачей, если условие баланса нарушаются; в случае выполнения условия баланса  она называется сбалансированной транспортной задачей.

Однако у этой задачи есть одна очень существенная особенность: в ограничениях перед неизвестными всегда стоит 1. И именно это позволяет разработать гораздо более эффективные и простые алгоритмы решения транспортной задачи, чем симплекс-метод.

Сам же симплекс-метод был  бы не эффективен по двум причинам:

Большая размерность решаемой задачи. Общее число неизвестных  величин  равно mn , и даже при n =m = 10 размерность решаемой задачи уже будет равна 100. Даже ЭВМ будет решать такую задачу симплекс-методом достаточно долго.

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

Приведение открытой транспортной задачи к сбалансированной

Превышение запасов над  потребностями.

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