86746

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

Лекция

Информатика, кибернетика и программирование

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

Русский

2015-04-10

976.5 KB

14 чел.

Лекция по линейному программированию

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

Математическое программирование- область математики, разрабатывающая теорию и численные методы решения экстремальных задач с ограничениями на область изменения переменных.

Математическое программирование возникло на стыке математики и экономики, то есть это-математические методы решения экстремальных задач, и в то же время- новый раздел математики.

Формулировка экономико- математической задачи включает:

а) формирование целевой функции (показателя эффективности или критерия оптимальности), то есть функции, экстремальное значение которой нужно найти в пределах экономических возможностей;

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

Все это составляет экономико-математическую модель (ЭММ) задачи.

ЭММ- это абстрактное отображение реального экономического процесса в виде математических формул, уравнений, неравенств, цифр и т.д.

Запись задачи математического программирования

Найти значение n переменных - n-мерный вектор (план), доставляющий экстремальное значение целевой функции

(1)

 

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

(2)

(3)

(последние неравенства вытекают из экономических или физических соображений)

Здесь для любого i   -известные заданные функции,  - область допустимых решений (или экономических возможностей), bi =const

План, удовлетворяющий системе ограничений задачи, называется допустимым ()

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

Экстремальное значение функции цели обозначается  

Классификация методов математического программирования

Даётся в зависимости от вида функций (1) и (2):

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

Линейное программирование

Основная задача линейного программирования (ЗЛП)

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

Общая форма записи ЗЛП в компактном виде:

(4)

-требование оптимизации;

(5)

(6)

(7)

- нетривиальная система ограничений;

(8)

- тривиальные неравенства (могут все отсутствовать).

Задача (4)-(8) называется основной задачей линейного программирования. Коэффициенты   - заданные действительные числа. Кроме того, в модель могут быть введены и другие ограничения.

Замечания.

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

Экономико-математические модели задач ЛП

ЭММ планирования производства (задача о наилучшем использовании ресурсов)

Дано:

  •  предприятие выпускает n  различных видов продукции (j=1,2,…,n);
  •  оно располагает для этого m видами ресурсов (i=1,2,…,m) (например, рабочая сила, площади, сырьё, энергия и пр.);
  •  ресурсы ограничены и составляют  условных единиц;
  •  цена реализации j-го продукта равна  , то есть задан вектор цен ;
  •  технологические коэффициенты aij : сколько единиц i- го ресурса расходуется для производства единицы j- го вида продукции.

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

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

Теперь составим баланс расхода по каждому ресурсу. Скажем, расход i- го ресурса складывается из затрат на производство 1-го изделия, то есть ai1x1, расхода на производство 2-го изделия ai2x2,…, расхода на производство n-го изделия ainxn. С другой стороны, этот суммарный расход не может превысить общего количества этого ресурса, то есть bi. Таким образом, запишем аналогичные ограничения для каждого из ресурсов, получим систему неравенств:

Чтобы план был реален, он должен состоять из неотрицательных компонент:

Запишем ЗЛП о наилучшем использовании ресурсов в компактном виде: найти  при ограничениях

;

.

Задача о смесях (выбор диеты, составление кормового рациона, приготовление различных смесей)

Рассмотрим на примере задачи о диете: получить кормовой рацион с заданными свойствами (содержанием питательных веществ) при наименьших затратах на исходные сырьевые материалы.

Дано:

  •  n видов исходных продуктов (сено, силос и пр. для животноводства);
  •  они содержат m видов питательных веществ (белки, жиры, углеводы, соли и т.д);
  •  для жизнедеятельности надо потреблять не менее bi единиц i-го питательного вещества;
  •  cj – стоимость единицы исходного продукта j – го вида;
  •  aij – содержание i-го питательного вещества в единице j-го вида корма.

Составим ЭММ задачи. Обозначим через xj количества кормов j-го вида. Тогда суммарная стоимость всего набора кормосмесей    равна  . Эта стоимость должна быть минимальной, то есть целевая функция задачи выглядит так:

.

Теперь составим баланс по каждому питательному веществу в кормовом рационе. Для i-го питательного вещества: содержание i-го питательного вещества в кормосмеси первого вида равно ai1x1, в кормосмеси второго вида равно ai2x2,…, в кормосмеси n-го вида равно ainxn. Общее количество i-го питательного вещества должно быть не меньше, чем bi. Это задаёт вид неравенства, и в результате запишем систему ограничений для всех питательных веществ:

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

Формы записи ЗЛП

Симметричная или стандартная форма записи ЗЛП. Она состоит в определении максимального значения функции (4) при выполнении условий (5) и (8) общей ЗЛП, где k=m  и  t=n.

Каноническая форма записи ЗЛП: это задача на максимум

,

все нетривиаальные ограничения заданы в виде равенств  

а тривиальные ограничения распространяются на все переменные  

Матричная форма. Введём обозначения:

матрица системы ограничений;

вектор-строка коэффициентов целевой функции;

вектор-столбец неизвестных (штрих, обозначающий транспонирование, позволяет нам столбцовый вектор записать как строку для удобства);

вектор-столбец свободных членов системы нетривиальных ограничений задачи.

Запишем каноническую форму в матричном виде:

Веторная форма. Рассмотрим только одну из векторных форм. Обозначим

,  .

Задача принимает вид:

  (здесь скалярное произведение векторов)

Однородная форма. Однородной называется такая модель ЗЛП, в которой все ограничения (нетривиальные и тривиальные) заданы в виде неравенств:

Эта форма удобна при графическом методе решения ЗЛП. Обратите внимание, что здесь переменные не обязательно неотрицательны.

Взаимосвязь однородной и канонической форм записи

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

Перевод общей ЗЛП в однородную форму. Основным отличием общей формы от однородной является наличие в составе ограничений некоторого количества уравнений вида (7); каждое такое уравнение

  эквивалентно системе из двух нестрогих неравенств  

Эквивалентные преобразования однородной модели в каноническую. 

  1.  Каждое исходное неравенство типа «меньше или равно» приводится к эквивалентной системе из уравнения и тривиального неравенства добавлением своей балансовой переменной:

(xn+1 балансовая переменная)

  1.  Каждое исходное неравенство типа «больше или равно» приводится к эквивалентной системе из уравнения и тривиального неравенства вычитанием своей балансовой переменной:

, (xn+2 – балансовая переменная)

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

  1.  Если на какую-нибудь переменную не наложено условие неотрицательности, её можно представить как разность двух неотрицательных переменных:

  1.  Если , то это требование эквивалентно требованию , то есть при необходимости задачу минимизации можно заменить задачей максимизации и наоборот.
  2.  Дополнительные балансовые переменные   вводятся в целевую функцию с коэффициентами, равными нулю:

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

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

Задача о смесях в канонической форме

Пример. Привести ЗЛП к канонической форме:

Обратите внимание, что переменная x3  может принимать произвольные значения.

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

Графический метод решения ЗЛП

Графический метод используется, с одной стороны, для обобщения на алгебраический метод с произвольным количеством переменных, с другой стороны, для наглядного представления решения ЗЛП с двумя переменными. При наличии только двух переменных область допустимых решений (ОДР) может быть легко изображена на плоскости .

Рассмотрим ЗЛП с двумя переменными в однородной форме записи:

(1)

(2)

(3)

Рассмотрим вектор , который называется градиентом функции Z. Его компонентами являются частные производные целевой функции по соответствующим координатам, которые по своему смыслу представляют собой скорости возрастания функции Z вдоль осей Ox1 и Ox2 соответственно. Этот вектор показывает направление наискорейшего возрастания целевой функции. Вектор  называется антиградиентом целевой функции, он показывает направление наискорейшего убывания целевой функции. Выберем произвольное значение целевой функции Z=Z0. Получим уравнение прямой Z0=c1x1+c2x2 в системе координат . Эту прямую также называют линией уровня целевой функции, то есть линией постоянного значения. Положим Z0=0, получаем линию уровня, проходящую через начало координат. При Z>Z0 линия уровня будет лежать параллельно первоначальной дальше от начала координат в направлении вектора . Очевидно, что все  линии уровня параллельны между собой и, соответственно, перпендикулярны векторам - планам задачи.

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

Рассмотрим вектор роста целевой функции на плоскости

Теперь рассмотрим нетривиальные ограничения (2) и запишем их в виде:

(4)

Множество решений (4) представляет собой полуплоскость, расположенную по одну из сторон прямой, уравнение которой:

(5)

Другими словами, эта прямая представляет собой границу полуплоскости. Если построить на плоскости все полуплоскости из системы (4), а затем учесть все тривиальные неравенства (3), которые локализуют допустимые решения ЗЛП в первом квадранте системы координат, то получим область, которая называется областью допустимых решений (ОДР) ЗЛП. Эта область на плоскости, если она является ограниченной, имеет вид выпуклого многоугольника. В общей теории линейного программирования доказывается, что ОДР представляет собой выпуклую область, то есть область, в которой любые две точки соединяются отрезком прямой, полностью лежащим в этой области. Важным следствием этого положения является тот факт, что оптимальное решение ЗЛП, если оно существует, обязательно будет находиться в угловой точке ОДР (в одной или в нескольких). Теперь, подводя итог всему сказанному, можно утверждать, что оптимальное решение ЗЛП находится в той угловой точке, из которой на направление вектора роста целевой функции опускается самый дальний от начала координат перпендикуляр. После нахождения оптимальной угловой точки надо найти её координаты как пересечение соответствующих границ, это будет оптимальный план. Далее определяем значение целевой функции в оптимальной точке, подставляя в эту функцию найденные координаты.

Пример. Решить графически следующую ЗЛП:

Построим, например, полуплоскость, отвечающую первому неравенству системы (1):

2x1 + 1x2 ≤ 400.

Эта полуплоскость делит координатную плоскость граничной линией, заданной уравнением:

2x1 + 1x2 = 400.

Линию, если она не проходит через начало координат, проще всего построить по двум точкам на осях координат. При х1= 0 получаем х2 = 400, а при х2 = 0 получаем х1 = 200. Соединяем эти две точки прямой линией, получаем две полуплоскости, выше и ниже этой прямой. Исходному неравенству отвечает только одна из этих полуплоскостей. Она  определяется подстановкой в неравенство пробной точки, не лежащей на граничной прямой. Например, такой точкой может быть начало координат  х1 = х2 = 0, т.е.  0 400.

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

Аналогично построим и две другие полуплоскости, получим ОДР:

Теперь надо найти угловую точку ОДР, в которой целевая функция достигает максимума. Для этого построим вектор роста целевой функции = ( 60 ; 40 ), который состоит из коэффициентов целевой функции при соответствующих переменных. Вектор роста указывает направление наискорейшего возрастания целевой функции. Надо найти в ОДР точку, наиболее удаленную от начала координат в этом направлении. Для этого на направление вектора  из всех угловых точек ОДР опускаем перпендикуляры. Оптимальному плану соответствует угловая точка, порождающая самый дальний от начала координат перпендикуляр. В нашем случае такая угловая точка образована пересечением границ 1-го и 2-го неравенств, поэтому эти неравенства запишутся как уравнения:

Решение этой системы даёт оптимальный план первоначальной задачи:

= 140;  = 120.

Этот план дает значение целевой функции, равное 13200:

Таким образом, решение исходной задачи получено.

Теперь рассмотрим другие частные случаи ОДР на плоскости.

  1.  ОДР представляет собой не ограниченную в направлении вектора роста целевой функции многоугольную область. В этом случае оптимального решения не существует, целевая функция стремится к бесконечности:
  2.  ОДР состоит из единственной точки. Этот случай встречается крайне редко, и тогда задача имеет единственное допустимое решение, которое является одновременно оптимальным
  3.  ОДР- пустое множество. В этом случае система ограничений задачи противоречива, и задача вообще не имеет допустимых, а следовательно, и оптимальных решений.
  4.  Задача имеет бесконечное множество оптимальных решений. Это происходит, когда две угловые точки ОДР являются оптимальными; следовательно, оптимальными являются и все точки, лежащие на участке границы между этими угловыми точками.

                                           

Замечание. Графическим методом можно решить ЗЛП и с большим числом неизвестных, если в её канонической записи число неизвестных n и число линейно независимых уравнений m связаны соотношением:

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

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

Преобразование канонической модели в симплексную. Основная идея симплекс-метода

Рассмотрим ЗЛП в канонической форме записи:

(1)

(2)

(3)

Для определенности будем считать, что число неизвестных больше числа уравнений, то есть . Это обычная ситуация для экономических задач, поскольку каноническая форма  получается из однородной преобразованием неравенств в уравнения, и при этом размерность задачи (определяемая числом переменных) возрастает и становится больше числа ограничений. Кроме этого, без потери общности будем считать все свободные члены нетривиальных ограничений (1) неотрицательными. В противном случае можно соответствующее уравнение умножить на (-1). Обратите также внимание на наличие свободного члена в целевой функции (3), который обычно появляется в ней в случае замены переменных.

Напомним некоторые сведения из теории систем линейных алгебраических уравнений. В системе (1) все переменные можно разделить на две группы: базисные (основные) и свободные (неосновные). Базисные переменные- это любые n переменных, определитель из коэффициентов которых в системе (1) не равен нулю. Остальные переменные в этой системе являются свободными. Естественно, выбор базиса в такой системе не является единственным. Решение системы (1) называется допустимым, если при этом выполняются ограничения (2), то есть все компоненты вектора решения неотрицательны. Решение системы (1) называется базисным, если в нем все свободные переменные равны нулю. Допустимое базисное решение называется опорным планом.

Эквивалентными Гауссовыми преобразованиями всякая каноническая форма приводится к симплексной форме, позволяющей получить исходное опорное решение:

(4)

В системе (4) переменные  являются базисными, а переменные - свободными. Из системы (4)  можно получить выражения всех базисных переменных через свободные. После подстановки этих выражений в целевую функцию (3) получим функцию, в которой отсутствуют базисные переменные:

(5)

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

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

Чтобы удовлетворить неравенствам (2) и получить допустимое решение, надо выполнить преобразования Гаусса так, чтобы все свободные члены остались неотрицательными. Поэтому алгоритм Гаусса требует некоторого уточнения, и для этого приведем некоторые дополнительные сведения.

Определение. Если в системе уравнений (1) все свободные члены неотрицательны, то допустимым отношением к выбранному k- му ключевому столбцу называется число

 если aik>0  

(6)

в противном случае  это отношение не существует или не является допустимым.

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

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

Очень важной для понимания смысла решения ЗЛП является следующее утверждение.

Теорема. Опорное решение задачи (1)-(3) и угловая точка ОДР этой задачи эквивалентны.

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

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

Теперь сформулируем главную идею симплекс-метода:

Найти исходное опорное решение ЗЛП (то есть угловую точку ОДР).

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

Алгоритм симплекс-метода

Этот алгоритм целесообразно рассмотреть на конкретном примере.

Пример. Решить симплекс-методом следующую ЗЛП:

(1)

(2)

(3)

Эта задача относится к задаче об использовании ресурсов. Здесь в качестве свободных членов в правой части нетривиальных ограничений стоят запасы сырья трех видов. Такая задача удобна тем, что каноническая форма совпадает с симплексной, и не нужно прибегать к специальным приемам для её получения. Исходная задача в каноническом виде выглядит так:

(4)

(5)

(6)

Систему отграничений-равенств можно записать в векторной форме

++++ = ,

где  =;   =;    = ;   = ;    =   ;    =.

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

Для решения задачи (4)-(6) симплекс - методом  необходимо иметь опорный план, т.е. допустимое базисное  решение системы (5). Для этого все векторы надо разделить на две группы – базисные и свободные. Сначала выбираем базисные. Поскольку нетривиальных ограничений всего три, то и базисных векторов будет тоже три. В качестве базисных выбирают вектора, имеющие предпочтительный вид, т.е. в данном случае , и. Им соответствуют базисные переменные х3, х4, х5 системы (5). Остальные переменные (х1 и  х2 ) будут свободными. При получении базисного решения все свободные переменные приравниваются к нулю. Подставив в (5)   х1= х2=0, легко получаем остальные компоненты опорного плана:

х3 = 400;    х4 = 900;   х5 = 600.

В векторном виде этот опорный план выглядит так:

= ( 0 ; 0 ; 400 ; 900 ; 600 ).

Подставив компоненты  в целевую функцию (4), получим значение целевой функции для этого плана:

Z ()=0.

Теперь составим первоначальную симплексную таблицу:

Сб

Б

0

60

40

0

0

0

0

400

 2  

1

 1 

0

0

=200

0

900

3

4

0

1

0

=300

0

600

 1  

3

 0 

0

1

=600

zj - cj

0

- 60 

- 40

0

0

0

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

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

Последний столбец рассмотрим позже.

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

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

Найдем эту пару векторов. Сначала определим вектор, который войдет в базис. Это должен быть один из свободных векторов, т.е.  или . Выбираем тот вектор, которому в индексной строке соответствует самое отрицательное число (-60, обведено пунктиром). Значит, вектор  становится базисным.

Теперь определим вектор, “покидающий” базис. Это делается с помощью симплексных отношений, обозначенных в последнем столбце симплекс–таблицы. Как видно из заголовка столбца, числителем симплексного отношения является свободный член ограничения, а знаменателем  – положительные коэффициенты ведущего столбца, т.е. столбца  (вектора, который теперь войдет в базис). Строка, в которой находится минимальное симплексное отношение, называется ведущей строкой. В той же строке находится вектор , покидающий наш первоначальный базис. Только при этом условии гарантируется неотрицательность свободных членов при пересчете таблицы. Отметим также, что при  симплексные отношения являются недопустимыми или не существуют; их не следует рассматривать при определении минимального отношения.

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

Теперь приступим к пересчету таблицы. Это делается в три этапа. Сначала ведущая строка делится на ведущий элемент: 

Сб

Б

0

60

40

0

0

0

60

200

1

0

0

0

0

zj - cj

Обратите внимание, что во втором столбце вместо  уже стоит новый базисный вектор с коэффициентом 60 в столбце Сб.

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


Сб

Б

0

60

40

0

0

0

60

200

1

0

0

0

0

1

0

0

0

0

1

zj - cj

0

0

0

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

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

Для любого элемента первоначальной таблицы можно определить прямоугольник

                         а*                           В

                         А                           а

Здесь - ведущий элемент, а - искомый элемент, А, В – элементы, находящиеся с ними на пересечении строк и столбцов.

Новое значение элемента а получается из формулы:

  

Это и есть правило прямоугольника.

Например, для прямоугольника, обозначенного в первоначальной таблице, в новой таблице получаем значение:

0 -  =  -

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



Сб

Б

0

60

40

0

0

0

60

200

1

0

0

400

0

300

0

- 1,5

1

0

=120

0

400

0

-

0

1

160

zj - cj

12000

0 

- 10

30

0

0

Произошел переход к новому базису: ,,. При этом переменные х2, х3 являются свободными, и в опорном плане их значения равны нулю. Значения остальных переменных получаем из нового столбца свободных членов:

х1 = 200;      х4 = 300;     х5 = 400.

Запишем опорный план в векторной форме:

= ( 200 ; 0 ; 0 ; 300 ; 400 ).

Этому плану соответствует значение целевой функции, равное 12000 (проверьте подстановкой компонент  в выражение (4)). В новой таблице это значение зафиксировано в индексной строке в столбце свободных членов.

Как видим, в индексной строке остался один отрицательный элемент, поэтому полученный план не является оптимальным. Значение  -10 находится в столбце , поэтому  войдет в новый базис. Минимальное симплексное отношение достигается в строке базисного вектора , который выходит из базиса.

Теперь пересчитываем таблицу первой итерации и получаем таблицу второй итерации:

Сб

Б

0

60

40

0

0

0

60

140

1

0

4/5

- 1/5

0

40

120

0

1

- 3/5

2/5

0

0

100

0

0

1

- 1

1

zj - cj

13200

0

0

24

4

0

Аналогично определяем новый опорный план:

= ( 140 ; 120 ; 0 ; 0 ; 100 ).

Ему соответствует значение целевой функции, равное 13200. Поскольку в индексной строке уже нет отрицательных элементов, план является оптимальным:

;  =13200.

Итак, задача линейного программирования решена.

Теория двойственности в линейном программировании

Построение двойственной ЗЛП

Рассмотрим прямую задачу планирования производства (об использовании ресурсов): найти вектор  при ограничениях

(1)

(2)

который обеспечивает максимум целевой функции

(3)

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

Цель продавца здесь: выручка за сырьё, идущее на производство единицы продукции каждого вида, должна быть не меньше цены единицы этой продукции (иначе выгоднее самому организовать производство).

Рассмотрим себестоимость единицы продукции первого вида в этих учетных ценах. Стоимость ресурса первого вида в этой продукции равна , стоимость ресурса второго вида равна , и т.д., стоимость m-го ресурса в первом изделии составляет . Просуммируем эти величины, получим себестоимость первого изделия, которая должна быть не меньше цены реализации этого изделия С1.. Аналогичные неравенства составим и для всех остальных видов продукции, получаем ограничения двойственной задачи:

(4)

Ограничения на переменные традиционны (поскольку цены на ресурсы не могут быть отрицательными):

(5)

Целью покупателя является минимизация затрат на приобретение ресурсов:

(6)

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

Общие правила составления двойственной задачи такие:

  1.  Матрица системы ограничений транспонируется.
  2.  Ограничения вида «меньше или равно» заменяются на ограничения «больше или равно».
  3.  Свободные члены исходной задачи становятся коэффициентами целевой функции задачи двойственной.
  4.  Коэффициенты целевой функции исходной задачи становятся свободными членами двойственной.
  5.  Исходная задача на максимум преобразуется в двойственную к ней на минимум.

Пример. Составить двойственную задачу к ранее рассмотренной:

Двойственная задача будет записана в такой форме:

Исследование пары двойственных задач

Поскольку двойственная задача также является ЗЛП, то её можно решить симплекс-методом. Однако двойственная задача и экономически, и математически тесно связана с прямой задачей, поэтому есть более простые способы её решения, если известно решение прямой задачи. Поэтому рассмотрим некоторые результаты, связывающие обе эти задачи.

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

(7)

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

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

(8)

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

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

(9)

(10)

Формулы (9) и (10) можно применять следующим образом:

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

Определение двойственных оценок ЗЛП

Вернемся к нашему примеру ЗЛП:

Эта задача в двойственной форме имеет вид:

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

Решая эту систему, получаем .

Другим способом получения двойственного решения является использование симплекс-таблиц исходной задачи. Рассмотрим последюю симплекс-таблицу из предыдущего раздела. Решение двойственной задачи (план) находится в индексной строке, в столбцах, соответствующих первоначальному базису. 

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

Теорема. Если основная задача линейного программирования имеет оптимальный план , то  является оптимальным планом двойственной задачи.

Применительно к рассмотренному нами примеру матрица D, составленная из столбцов первоначальной симплекс-таблицы, соответствующих окончательному базису, имеет вид:

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

. Эти значения и находятся в индексной строке последней таблицы.

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

Согласно первой теореме двойственности, , следовательно, можем записать:

(11)

т.е. доход зависит от объёмов ресурсов: . Вычислим градиент этой функции:

(12)

Сделаем следующие выводы:

Формула (11) отражает общий принцип баланса результатов производства  и затрат . Двойственные оценки обеспечивают этот баланс.

Из (11) и (12) следует, что  при изменении отдельно взятого ресурса на единицу увеличивается ровно на величину двойственной оценки этого ресурса:

(13)

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

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

Замечание. Формула (13) верна только при достаточно малом изменении объёмов ресурсов по сравнению с их общим количеством. Если это изменение велико, то учетная цена того или иного ресурса может стать нулевой. Точные количественные границы такого изменения рассмотрим ниже.

Устойчивость двойственных оценок

Двойственные оценки  при некотором изменении запасов ресурсов  называются устойчивыми, если при решении измененной ЗЛП эти двойственные оценки не изменяются. Разумеется, обеспечить устойчивость двойственных оценок можно только в определенных границах. Эти границы определяются следующей теоремой.

Теорема. При изменении объёма ресурсов двойственные оценки будут устойчивыми, если выполняется неравенство:

(14)

В формуле (14) вектор  означает первоначальный объём ресурсов. Матрица  составлена, как уже указывалось выше, из столбцов последней симплекс-таблицы, соответствующих первоначальному базису. Например, если изменить запасы ресурсов в ранее рассмотренной задаче на величину  (штрих означает транспонирование, а знак минус уменьшение объёма третьего ресурса ), то можно проверить условие устойчивости так:

Таким образом, при данном изменении объёмов ресурсов двойственные оценки не изменятся (будут устойчивыми).

Новое значение целевой функции при измененных ресурсах можно определить по выражению:

.

Значение  находим с использованием первой теоремы двойственности:

.

Применяя результаты нашего примера, получим

. Отсюда

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

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

Постановка транспортной задачи

Транспортная задача (ТЗ)-частный случай ЗЛП, который в силу своих особенностей допускает решение более простыми методами. В задаче имеются следующие исходные данные:

  •  есть m пунктов отправления (ПО), или поставщиков, или баз , где находятся запасы груза ;
  •  есть n пунктов назначения (ПН), или потребителей, или получателей , подавших заявки на  единиц груза;
  •  известны тарифы , или стоимость перевозки единицы груза от i-го поставщика к j-му потребителю.

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

Обозначим через  объём перевозок от i-го поставщика к j-му потребителю. Рассмотрим распределительную (транспортную) таблицу:

ПН

ПО

B1

B2

Bn

Запасы

А1

C11

x11

C12

x12

C1n

x1n

a1

А2

C21

x21

C22

x22

C2n

x2n

a2

Аm

Cm1

xm1

Cm2

xm2

Cmn

xmn

am

Потребности

b1

b2

bn

Строки таблицы соответствуют базам, а столбцы-заказчикам. Например, перевозка груза с 3-й базы 2-му заказчику соответствует клетке на пересечении строки А3 и столбца В2.

Составим экономико-математическую модель задачи. Будем считать, что общее количество запасов на всех базах равно общему объёму заявок потребителей (такая ТЗ называется закрытой).

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

(1)

Составим ограничения по потребностям. Поскольку каждый потребитель должен получить точно заказанное количество единиц груза, сумма перевозок по каждому столбцу транспортной таблицы будет равна объёму заказа:

(2)

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

(3)

Целевая функция имеет смысл общей стоимости всех перевозок, которая должна быть минимальна:

(4)

Основные свойства ТЗ

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

(5)

иначе будет открытая модель:

(6)

  1.  ТЗ всегда имеет решение для закрытой модели.
  2.  Число уравнений задачи (1)-(4) равно (m+n), а число переменных – mn.
  3.  Коэффициенты при переменных в урвнениях (1) и (2) равны 1.
  4.  Количество независимых уравнений будет (m+n-1), так как сумма m уравнений (1) всегда равна сумме n уравнений (2) (рассматривается закрытая модель). Значит, базисных переменных будет (m+n-1), а свободных переменных – (m-1)(n-1) (столько нулей, по крайней мере, будет в оптимальном плане).

Методы построения первоначального плана

Решение транспортной задачи проводится в два этапа.

  1.  На первом этапе находится первоначальный опорный план.
  2.  На втором этапе на базе опорного плана методом потенциалов определяется оптимальный план.

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

Самыми простыми методами построения первоначального плана ТЗ являются:

Метод северо-западного угла (или диагональный метод).

Метод минимальной стоимости (или  минимального элемента, или минимального тарифа).

Метод двойного предпочтения.

Из методов оптимизации первоначального плана самым распространенным является метод потенциалов.

Метод северо-западного угла

Рассмотрим транспортную задачу по следующим исходным данным, представленным в виде таблицы:

ПН

ПО

В1

В2

В3

В4

В5

Запасы аi

А1

4

11

6

5

15

200

А2

8

7

9

13

10

200

А3

10

5

12

7

20

100

Потребнос- ти bj

70

80

150

110

90

В методе северо-западного угла, или диагональном, заполнение транспортной таблицы всегда начинается с клетки (А1 , В1), т.е. “северо-западного угла” таблицы. Далее заполнение идет вокруг диагонали таблицы и всегда заканчивается в правом нижнем углу (клетка ( А3 , В5 )). В каждой клетке объем перевозки определяется как наименьшее значение из двух чисел: остатка запаса на базе и остатка заявки потребителя. Отсюда:

х11  =  min { a1 , b1 } = { 200 ; 70 } = 70.

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

Далее наступает очередь второго заказчика, который со своей заявкой приходит на первую базу, где еще остался товар:

х12  =  min { 200 - 70 ; 80 } = { 130 ; 80 } = 80.

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

Теперь на первой базе осталось только 50 т груза. Поэтому третий заказчик получит только эти 50 т, хотя ему требуется 150 т.

х13  =  min { 200 – 70 – 80 ; 150} = 50.

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

Остальную часть своего заказа второй заказчик получит на второй базе:

х23  =  min { 200 ; 150 – 50 } = 100.

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

ПН

ПО

В1

В2

В3

В4

В5

аi

А1

4

70

11

80

6

50

5

15

200

А2

8

7

9

100

13

100

10

200

А3

10

5

12

7

10

20

90

100

bj

70

80

150

110

90

В  этом опорном  плане  семь занятых клеток. Поскольку их должно быть m +n1, где  m – число баз,  n  -  число заказчиков, план является  невырожденным. Если бы клеток было меньше, чем  m +n1, план был бы вырожденным.

Осталось подсчитать общую стоимость перевозок. Она складывается из произведений объемов перевозок и тарифов по всем занятым клеткам, т.е.:

F ( X1 ) = 70 4 + 80 11 + 50 5 + 100 9 + 100 13 + 10 7 + 90 20 =  5530.

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

Метод минимальной стоимости

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

В данном случае сама дешёвая клетка ( А1 , В1 ). С неё  и начинаем распределение грузов:

х11  =  min { 200 ; 70 } = 70.

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

х14  =  min { 200 - 70 ; 110 } = 110;

х32  =  min  { 100 ; 80 } = 80;

х13  =  min { 200 – 70 – 110 ; 150 } = 20;

х23  =  min { 200 ; 150 - 20 } = 130;

х25  =  min { 200 - 130 ; 90 } = 70;

х35  = 20.

Получаем следующий опорный план:

ПН

ПО

В1

В2

В3

В4

В5

bj

А1

4

70

11

6

20

5

110

15

200

А2

8

7

9

130

13

10

70

200

А3

10

5

80

12

7

20

20

100

аi

70

80

150

110

90

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

F ( X2 ) = 4 70 + 6 20 + 5 110 + 9 130  + 10 70 + 5 80  + 20 20 = 3620.

Как видим, этот опорный план дешевле первого.

Метод двойного предпочтения

Теперь построим опорный план методом двойного предпочтения. При этом сначала в каждом столбце отметим галочкой клетку с наименьшей стоимостью, затем то же самое делаем с каждой строкой. Далее максимально возможные объемы перевозок помещаем в клетки, отмеченные двойной галочкой. Затем распределяем перевозки по клеткам, отмеченным одной галочкой. В оставшейся части таблицы перевозки распределяем по методу минимальной стоимости.

Как видим, данный метод фактически является модифицированным методом минимальной стоимости.

Очевидно, что по крайней мере одна клетка таблицы будет иметь двойную галочку (этой клеткой обязательно будет клетка с минимальным тарифом). В нашем случае таких клеток будет две: (А1, В1 ) и (А3, В2 ). Их и заполним в первую очередь:

х11 = 70 ;    х32 =80.

Клетками с одной галочкой будут : (А1, В4 ) ;   (А2, В5 ) ;   (А2, В2 ) и  (А1, В3 ) (проверьте это). Клетка (А2, В2 ) не будет заполнена, в этом нет необходимости, поскольку во втором столбце занята одна клетка : (А3, В2 ) с двойной галочкой. Остальные клетки используем:

х14 = 110 ;    х13 = 20 ;    х25 = 90.

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

х23 = 110 ;    х33 =20.

Получаем новый опорный план транспортной задачи:

ПН

ПО

В1

В2

В3

В4

В5

аi

А1

         4

70

11

             6

20

             5

110

15

200

А2

8

             7

9

110

13

           10

90

200

А3

10

         5

80

12

20

7

20

100

bj

70

80

150

110

90

Этому опорному плану соответствует стоимость перевозок:

F (X3) =4 70 + 6 20 + 5 110 + 10 90 + 5 80 + 12 20 = 3480.

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

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

Метод потенциалов получения оптимального плана ТЗ

Теорема о потенциалах

План (  ) транспортной задачи является оптимальным тогда и только тогда, когда существуют  числа  такие  ui  (i = ),    vj  ( j =), называемые соответственно потенциалами поставщиков и потребителей, при которых  выполняются соотношения:

(7)

Как видим из системы (7), уравнения записываются для заполненных клеток, а неравенства – для свободных клеток. Справа везде стоят тарифы перевозок в соответствующих клетках.

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

Алгоритм метода потенциалов

Шаг 1.Определение потенциалов поставщиков и потребителей.

На этом шаге составляем систему уравнений для потенциалов, используя только занятые клетки. Используем последний опорный план:


ПН

ПО

В1

v1=4

В2

v2= -1

В3

v3=6

В4

v4=5

В5

v5=7

аi

А1           u1=0

4

70

11

6

20

5

110

15

200

А2        u2=3

8

7

9

110

13

10

90

200

А3        u3=6

10

5

80

12

20

7

20

100

bj

70

80

150

110

90

Заметим, что в этой системе всего 8 неизвестных, т.е. m + n  (3 + 5). Однако уравнений всего 7,  поскольку  в  невырожденном  опорном  плане  всего  7  заполненных  клеток  (т.е.  m + n - 1 ). Для однозначного решения не хватает одного уравнения. В этом случае один из потенциалов, например, и1 (может быть и другой потенциал) приравнивают некоторому постоянному числу, например, нулю:

и1=0.

Это и будет недостающим уравнением в системе. Теперь систему можно легко решить, имея в виду, что все уравнения состоят только из двух неизвестных. Результаты решения записаны в заголовочных клетках таблицы. Решать систему можно и непосредственно по таблице, используя занятые клетки с известными значением одного из потенциалов. Этот процесс всегда можно начать с первой строки, где уже известно значение  и1=0.

Сделаем замечание для случая, когда опорный план является вырожденным. В этом случае количество уравнений для определения потенциалов будет меньше, чем  m + n – 1. Это недопустимо мало, поэтому используют следующий приём. В недостающее число свободных клеток записывают нулевые значения перевозок, а сами эти клетки считаются занятыми, и для них записывают уравнения потенциалов. Такая модификация опорного плана не влияет на его стоимость, поскольку нулевые перевозки имеют нулевую стоимость. Свободные клетки значащих нулей для подстановки выбираются не произвольно, однако об этом поговорим ниже.

Шаг 2. Проверка оптимальности опорного плана.

На этом шаге проверяем выполнение неравенств (7) для свободных клеток. Перепишем  их  в  виде:

,    ; .

Если все Sij неотрицательны, значит, опорный план оптимален, и на этом наш вычислительный процесс заканчивается. Подсчитаем оценки для свободных клеток:

S12 = 11 – (0 - 1) = 12 0

S15 = 15 – (0 +7)  =  8 0

S21 = 8 –  (3 + 4)  =  1 0

S22 = 7 –  (3 - 1)   =  5 0

S24 = 13 – (3 + 5)  = 5 0

S31 = 10 – (6 + 4)  = 0 0

S34 = 7 – (6 + 5)  = - 4 < 0

S35 = 20 – (6 + 7)  = 7 0

Оценка S34 оказалась отрицательной, значит, одно из неравенств (7) нарушено, и опорный план не является оптимальным . Таким образом, он нуждается в модификации, которую проведем на следующем этапе.

Шаг 3. Пересчет по циклу.

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

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

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

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

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

В данном случае цикл пойдет через клетки (А3, В4 ) ;   (А1, В4 ) ;   (А1, В3 ) и  (А3, В3 ). В таблице цикл обрисован пунктирным прямоугольником.

Одним из признаков опорного плана транспортной задачи является то обстоятельство, что для любой свободной клетки всегда можно построить замкнутый цикл, где все остальные вершины будут располагаться в занятых клетках. Однако такой цикл будет единственным. С другой стороны, в опорном плане нельзя построить замкнутый цикл, в который входили бы только занятые клетки. Это привело бы к противоречивой системе уравнений для потенциалов. Данное замечание подсказывает правило, по которому в вырожденный опорный план должны быть помещены значащие нули: их нельзя располагать в клетках, которые могут создать замкнутый цикл только из занятых клеток.

Отсюда  следует, что,  если  в  транспортной задаче число занятых клеток превышает  m + n – 1, то из них можно построить замкнутый цикл, и план уже не будет опорным.

Теперь вернемся к построенному нами циклу. Из всех отрицательных вершин цикла выбираем наименьшее значение перевозок:

Далее на значение  уменьшаем перевозки в отрицательных вершинах цикла, а во всех положительных вершинах значения перевозок увеличиваем на эту же величину. Поскольку в цикле чётное число вершин, то в пределах цикла общий объём перевозок не изменится, что не приведет к нарушению баланса между запасами и заявками. Пересчитанная таблица выглядит так:

ПН

ПО

В1

v1=4

В2

v2=3

В3

v3=6

В4

v4=5

В5

v5=7

аi

А1           u1=0

4

70

11

6

40

5

90

15

200

А2        u2=3

8

7

9

110

13

10

90

200

А3        u3=2

10

5

80

12

7

20

20

100

bj

70

80

150

110

90

Пересчитаем стоимость нового плана:

F ( X4 ) = 4 70 + 6 40 + 5 90 + 9 110  + 10 90 + 5 80  + 7 20 = 3400.

Как видим, стоимость перевозок уменьшилась.

Шаг 4. Определение потенциалов в новом плане.

Этот шаг является повторением шага 1. Система уравнений здесь почти не отличается от предыдущей, кроме одного уравнения. Это связано с тем, что свободная клетка (А3, В4 ) стала занятой, а клетка (А3, В3) стала свободной. Фактически здесь идет речь о преобразовании однократного замещения, которое имело место в симплекс-методе. Соответственно одно из уравнений для потенциалов заменяется другим. Запишем новую систему:

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

Шаг 5. Расчет оценок для свободных клеток.

Этот шаг повторяет шаг 2. Считаем оценки:

S12 = 11 – (0 + 3) =  8 0

S15 = 15 – (0 +7)  =  8 0

S21 = 8 –  (3 + 4)  =  1 0

S22 = 7 –  (3 + 3)  =  1 0

S24 = 13 – (3 + 5)  = 5 0

S31 = 10 – (2 + 4)  = 4 0

S33 = 12 – (2 + 6)  = 4 0

S35 = 20 – (2 + 7) =11 0

Поскольку все оценки свободных клеток неотрицательны, полученный план является оптимальным. В противном случае пришлось бы продолжать шаги 1-3 процесса до тех пор, пока не будет получен оптимальный план.

Запишем решение транспортной задачи:

Fmin = F ( X* ) = 3400.

Другие типы транспортных задач

Открытые мадели ТЗ

  1.  В пунктах отправления имеются избыточные запасы тавара

В этом случае .

Экономико-математическая модель такой ТЗ также является ЗЛП:

(8)

Обратите внимание, что вместо уравнений (1) в модели (8) появились неравенства, означающие, что не все товары будут вывезены с баз.

Введение дополнительных (балансовых) переменных в эти неравенства для получения каконического вида модели эквивалентно введению (n+1)-го заказчика (фиктивного заказчика) с заявкой:

и нулевыми тарифами перевозок к нему от каждого поставщика . В транспортной таблице модифицированной задачи появляется дополнительный столбец, в каждой клетке которого вписываются нулевые тарифы. Таким образом, получаем закрытую модель ТЗ. Эта задача решается обычными методами, рассмотренными выше. Смысл полученных в решении значений балансовых переменных здесь-остатки грузов на базах. Другими словами, в некоторых клетках дополнительного столбца после оптимального решения остаются ненулевые значения перевозок (фиктивные значения); значит, с соответствующих баз не вывезены остатки товаров.

  1.  Открытая модель ТЗ с дефицитом ресурсов.

В этом случае . ЭММ имеет вид:

(9)

Обратите внимание на то, что вместо системы уравнений (2) записана система неравенств. Вводим фиктивного поставщика с номером (n+1) и запасом груза в нем, равным:

В транспортной таблице появится дополнительная строка с номером (m+1), в каждую клетку которой ставим нулевой тариф: . Перевозки в этих клетках являются балансовыми переменными. В результате получаем закрытую модель ТЗ и решаем её обычными методами. При этом в оптимальном решении некоторые из дополнительных клеток обязательно будут заполнены ненулевыми значениями перевозок. Смысл этих значений-недополученный груз соответствующими заказчиками.

ТЗ с дополнительными требованиями

  1.  ТЗ с блокированием перевозок.

В некоторых случаях реальных перевозок отдельные маршруты отсутствуют. В этом случае в соответствующие клетки таблицы ставят очень большие тарифы, которые обозначают М:

Тогда в результате решения ТЗ все клетки без перевозок в оптимальное решение не попадут.

  1.  Ограничения типа .

В этом случае на отдельных маршрутах предписываются конкретные объёмы перевозок. Исходная транспортная задача модифицируется так: в клетках, где зафиксированы объёмы перевозок, пересекаются некоторые базы и заказчики; из заявок этих заказчиков и из запасов на этих базах вычитаются величины , а вклетки ставят очень большие тарифы М. Далее решается обычная транспортная задача. В результате решения в нужных клетках будут нулевые перевозки. Окончательный план образуется вписыванием заданных величин в исключенные клетки.

  1.  Ограничения типа .

На отдельных маршрутах объёмы перевозок должны быть не меньше некоторого минимального уровня. Модификация задачи и её решения в общем виде можно представить на следующей схеме:

  1.  Дополнительное требование типа , то есть от iго поставщика к j-му потребителю можно вывести не более ij единиц груза (более сложная схема изменения ТЗ).

Задача модифицируется так: заявка некоего фиктивного потребителя фиксируется на уровне ij, а остальная часть заявки j-го потребителя помещается в дополнительный столбец. В этот же дополнительный столбец вносятся те же тарифы, что и в j-й столбец, кроме клетки в i-й строке, куда записывают бесконечно большой тариф М. Таким образом, вместо одного столбца для соответствующего потребителя появляются два, отвечающие за неких фиктивных потребителей, суммарная заявка которых равна заявке прежнего заказчика. В результате при решении модифицированной задачи в одном из дополнительных столбцов ни в одной клетке перевозка не превысит величину  ij, поскольку вся заявка этого столбца и равна этой величине, а в другом столбце в соответствующей клетке вообще не будет перевозок, так как клетка имеет тариф М. В результате при пересчете суммарные перевозки двух фиктивных поставщиков в соседних клетках равны их суммам, а в нужной клетке общая перевозка не превысит предельную величину (ведь вторым слагаемым здесь будет нулевое значение перевозки!).

Cij

xij

Cij

xij

M

0

bj

Транспортная задача по критерию времени

В некоторых транспортных задачах вместо тарифов задают величины tij – время доставки товара от i-го поставщика к j-му потребителю (например, при перевозках скоропортящихся грузов). Требуется найти план перевозок, при котором будет затрачено минимальное время. Эта задача не является ЗЛП, поскольку целевая функция не линейна относительно переменных xij. Рассмотрим метод решения этой задачи, который называется «методом запрещенных клеток».

Алгоритм решения (для закрытой модели ТЗ) содержит следующие этапы:

  1.  Находим опорное решение, например, методом северо-западного угла.
  2.  Находим время, затрачиваемое на этот план: , т.е. самое продолжительное время перевозок в занятых клетках.
  3.  Пытаемся улучшить решение, для чего:
    1.  Вычеркиваем свободные клетки, в которых время перевозки не меньше, чем Т1 (эти клетки нет смысла занимать)
    2.  Для самой продолжительной среди занятых клеток строим разгрузочную цепь- замкнутую линию с прямыми углами в вершинах. Первая вершина та, для которой строится цепь. Нечетные вершины должны попасть в занятые клетки, и они помечаются знаком плюс, четные вершины могут попасть и в занятую, и в незанятую клетки, и они помечаются знаком минус. Перебрасываемая величина  прибавляется к четным вершинам и вычитается из нечетных вершин. Для данной клетки может быть несколько цепей.
  4.  План будет оптимальным, а время минимальным, когда для самой продолжительной из занятых клеток нельзя построить разгрузочную цепь.

Пример. Решить ТЗ по критерию времени (рассмотрим таблицу с планом перевозок по методу С-З угла).

bj

ai

50

60

30

80

70

4

50   -

2

20 +

1

-

6

-

90

1

-       +

3

40  -

3

30

2

20

60

3

-

6

-

4

-

3

60

Отметим запрещенные клетки. Целевая функция имеет значение T1=max(4;2;3;3;2;3)=4=t11. Расставим разгрузочную цепь и знаки – плюсы и минусы – в вершинах. Перебрасываемая величина =min(50;40)=40  (минимум берем по перевозкам в отрицательных вершинах). Значение этой величины вычитаем из отрицательных вершин и прибавляем к положительным вершинам цепи, получаем новый опорный план:

bj

ai

50

60

30

80

70

4

10   -

2

60

1

-       +

6

-

90

  1

40   +

3

- 

3

30   -

2

20

60

3

-

6

-

4

-

3

60

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

bj

ai

50

60

30

80

70

4

-

2

60

1

10

6

-

90

  1

50

3

- 

3

20

2

20

60

3

-

6

-

4

-

3

60

Теперь целевая функция имеет значение 3, поэтому в новом плане запрещаем очередные клетки. После этого не остается ни одной свободной незапрещенной клетки, разгрузочную цепь построить нельзя, план оптимален. Задача решена.

31

PAGE  39


С1

С2

Z0

Z1>Z0

Z2>Z1

0

x2

x1

2X1+X2=400

X2

X1

400

200

X*

600

400

300

200

100

500

400

300

200

100

X1

X1

C

40

60

EMBED Equation.3  

EMBED Equation.3  

+

+

_

_

+

_

_

_

_

_

_

_

_

_

+

+

+

+

+

+

+

+

М

xij

Сij

ij

bj-ij

ai-ij

Сij=М

0

Далее блокировка

Возвращение к исходной задаче

Сij

xij+ij

Решается новая задача

Сij

xij

ai-ij

bj-ij

Сij

ij


 

А также другие работы, которые могут Вас заинтересовать

4063. Особенности определения удельного заряда электрона методом магнетрона 82.5 KB
  Определение удельного заряда электрона методом магнетрона Цель работы: Целью данной работы является определение удельного заряда электрона (отношение заряда электрона к его массе). Приборы и инструменты Название Предел измерения Цена деления...
4064. Проектирование автоматизированных систем. Конспект лекций 227 KB
  Общие сведения об автоматизированных системах управления. Понятие об АСУ, основные определения, классификация Особенности современных систем. В последние десятилетия быстро возрастает сложность объектов и систем, создаваемых в различных ...
4065. Экономическое обоснование технического решения в курсовом проекте по разработке технологической линии производства опилкобрикета 106 KB
  Введение Спад производства в лесной деревообрабатывающей промышленности России за последние 10 лет в среднем составляет 40. Инфраструктура лесопромышленного комплекса разрушен на 50-70. Из-за недостатка древесного сырья простаиваются предприятия ...
4066. АФС агентство недвижимости ООО Любимый город 267.5 KB
  Характеристика предприятия Общество с ограниченной ответственностью Любимый город создано в соответствии с Гражданским кодексом Российской Федерации. Компания зарегистрирована 19 декабря 2007 года регистратором Единым государственным реестром ю...
4067. Глобальные сети для доступа удаленных ЭВМ и терминалов к мощным ЭВМ и host-компьютерам 311 KB
  Введение Глобальные сети (Wide Area Networks, WAN), которые также называют территориальными компьютерными сетями, служат для того, чтобы предоставлять свои сервисы большому количеству конечных абонентов, разбросанных по большой территории - в предел...
4068. Характеристика сетей и технологий ISDN 187.5 KB
  Введение Integrated Services Digital Network (ISDN) (Цифровая Сеть с Интегрированными Услугами) - это всеми доступная интерактивная телефонная сеть, использующая новейшую цифровую технологию передачи сигнала, а так же включающая в себя обширный набо...
4069. Оценка стоимости машин, оборудования и транспортных средств методом чистых активов 242 KB
  Введение Стабилизация и дальнейшее развитие российской экономики непосредственно зависит от развития производственного аппарата промышленности, формируемого в первую очередь отраслями машиностроения. Машины и оборудование, транспортные средства сост...
4070. Психолого-акмеологическое обеспечение эффективности организационного лидерства 238.5 KB
  В рамках курса слушатели академии пополняют знания относительно важного в государственном управлении социально-психологического явления - лидерства, овладевают современными акмеологическими и психолого-педагогическими технологиями, ориентир...
4071. Предпринимательство: сущность и роль в экономическом развитии. Формы и сферы 97.5 KB
  Введение У истоков теории предпринимательства стоял шотландский экономист французского происхождения Р. Кантильен, который и ввел понятие «предприниматель» в экономическую теорию. По Кантильену, предприниматель- это человек с неопределен...