Экономико-математические методы

Оглавление:

Экономико - математические методы

Здравствуйте, на этой странице я собрала полный курс лекций по предмету «Экономико-математические методы».

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

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

Если что-то непонятно, Вы всегда можете написать мне в воцап и я помогу!

Математические методы в экономике — научное направление в экономике, посвящённое исследованию экономических систем и процессов с помощью математических моделей. wikipedia.org/wiki/Математическиеметодыв_экономике

Предмет экономико-математические методы

Экономико-математические методы (эмм) [economic-mathematical
methods] — это обобщающее название комплекса экономических и математических научных дисциплин, объединенных для изучения экономики. введено академиком василием сергеевичем немчиновым в начале 60-х гг. встречаются высказывания о том, что это название весьма условно и не отвечает современному уровню развития экономической науки, так как ― экономико-математические методы не имеют собственного предмета исследования, отличного от предмета исследования специфических экономических дисциплин

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

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

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

1) целевая функция

Экономико-математические методы

2)ограничения

Экономико-математические методы

3) естественные ограничения

Экономико-математические методы

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

В каждом случае целевая функция имеет свое выражение в зависимости от целей исследования.

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

Экономико-математические методы

Векторы Экономико-математические методы и Экономико-математические методы в матричной форме будут:

Экономико-математические методы

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

Матрица

Экономико-математические методы

называется матрицей ограничений (затрат или технологической).

Ограничения (1.2) — (1.4) и (1.2) — (1.4) называются основными, а ограничения (1.5) и (1.5*) прямыми или естественными (неосновными).

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

Задача с ограничениями (1.3) или (1.4) называется стандартной или симметричной, если отыскивается максимум (минимум) целевой функции все ограничения, которой записываются со знаками неравенств Экономико-математические методы либо Экономико-математические методы.

Если отыскивается максимум (минимум) целевой функции, все ограничения которой имеют вид (1.2), то есть, имеют знак Экономико-математические методы, то задача называется канонической или основной.

Вектор Экономико-математические методы, удовлетворяющий системе ограничений

задачи, называется планом. Множество планов, удовлетворяющих системе ограничений (1.2) — (1.5), называется множеством допустимых планов. Допустимый план Экономико-математические методы, при котором достигается экстремальное значение целевой функции (1.1), называется оптимальным.

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

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

Составляются ограничения (1.2) — (1.4), накладываемые па переменные, выражающие взаимосвязи исследуемого процесса.

Составляется целевая функция Экономико-математические методы (1.1).

На переменные накладываются естественные ограничения Экономико-математические методы (1.5).

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

  1. задачи определения оптимального ассортимента продукции (производственные задачи);
  2. задачи транспортного типа;
  3. задачи составления кормовой смеси (задачи о диете);
  4. задачи об оптимальном раскрое;
  5. задачи формирования кольцевых маршрутов (задачи коммивояжера);
  6. задачи многостороннего коммерческого арбитража.
  7. задачи выбора портфеля цепных бумаг и др.

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

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

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

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

Экономико-математические методы

Возможно эта страница вам будет полезна:

Решение экономико математических методов

Пример 1.1.

Определение оптимального ассортимента продукции (производственная задача).

Пусть определённая фирма выпускает два вида продукции П1 и П2, на производство которых используется сырьё трёх типов Экономико-математические методы и Экономико-математические методы. Максимально возможный расход сырья на единицу продукции, и доход (в условных единицах), получаемый фирмой от реализации единицы продукции,приведены в таблице 1.2.

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

Решение:

  • Обозначим через Экономико-математические методы — количество продукции П1, выпускаемой фирмой; Экономико-математические методы — количество продукции П2.
Экономико-математические методы
  • Целевая функция должна отражать доход, получаемый фирмой (максимизируется):
Экономико-математические методы
  • Составляем систему ограничений. На производство продукции фирма может израсходовать сырья не больше, чем у неё имеется. С учётом наличия сырья определённого типа на производство каждого вида продукции, получаем неравенства
Экономико-математические методы

То есть, математическая модель задачи в соответствие с (1.1)-(1.5) имеет вид:

Экономико-математические методы

Возможно эта страница вам будет полезна:

Экономико-математические методы задачи с решением и примерами

Пример 1.2.

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

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

Экономико-математические методы

Решение:

Переменными являются количества разводимых птиц:

  • Экономико-математические методы — количество расходуемого корма Экономико-математические методы, Экономико-математические методы — корма Экономико-математические методы.
  • Целевая функция будет отражать расходы фабрики (минимизируется)
Экономико-математические методы

Система ограничений представляет собой суточный расход корма для каждой породы птицы

Экономико-математические методы

Учитывая положительность естественных ограничений

Экономико-математические методы

математическая модель задачи будет иметь вид:

Экономико-математические методы

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

Если Экономико-математические методы какие-либо точки линейного пространства, то выпуклой линейной комбинацией этих точек называется сумма

Экономико-математические методы

где Экономико-математические методы — произвольные неотрицательные числа, удовлетворяющие условию

Экономико-математические методы

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

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

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

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

Базисные планы с неотрицательными компонентами называются опорными.

Справедливы теоремы.

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

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

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

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

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

Экономико-математические методы

можно перейти к нахождению максимума функции

Экономико-математические методы

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

Случай двух переменных

Постановка задачи в этом случае имеет вид:

Экономико-математические методы

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

Экономико-математические методы

Если рассматривается система неравенств, то областью её решений может быть один из следующих случаев. 1) Система несовместна, когда область решений является пустым множеством. 2) Система неравенств совместна, то есть, область её решений выпуклое непустое множество, называемое многоугольником решений (в отличие от «многогранника решений», когда число неизвестных Экономико-математические методы3), либо выпуклая многогранная область, уходящая в бесконечность.

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

Для определения экстремума ограниченной сверху целевой функции необходимо:

  • Из начала координат построить вектор — градиент целевой функции Экономико-математические методы. Построить линию уровня перпендикулярно градиенту, так как она проходит через начало координат, то такая линия называется опорной. Переместить её таким образом, чтобы она проходила через многоугольник решений. Тогда её уравнение будет иметь вид Экономико-математические методы, где Экономико-математические методы — любая постоянная. Если Экономико-математические методы, то передвигая линию уровня параллельно самой себе в направлении градиента, до тех пор, пока не будет достигнута последняя точка многоугольника решений (Рис. 1.1), получим необходимую точку, где целевая функция достигает максимума.

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

  1. Если Экономико-математические методы, то линия уровня Экономико-математические методы передвигается в направлении, противоположном своему градиенту (в направлении антиградиента Экономико-математические методы) до достижения крайней точки многоугольника решений (Рис. 1.2).

При решении могут встретиться следующие случаи.

1) 1) Целевая функция Экономико-математические методы принимает максимальное значение Экономико-математические методы в единственной точке Экономико-математические методы рис. 1.1 (единственное решение).

Экономико-математические методы
Экономико-математические методы

2) Целевая функция принимает минимальное значение Экономико-математические методы в единственной точке Экономико-математические методы рис. 1.2 (единственное решение).

3) Целевая функция F принимает максимальное значение в любой точке отрезка Экономико-математические методы рис 1.3. Прямая Экономико-математические методы перпендикулярна градиенту, (бесконечное множество решений).

4) Целевая функция не ограничена сверху на множестве допустимых решений рис. 1.4. Максимум недостижим.

5) Система ограничений несовместна рис. 1.5. Решений нет.

Таким образом, чтобы найти решение задачи линейного программирования геометрическим способом, необходимо:

  • Построить область решений задачи, то есть, многоугольник решений:

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

6) найти полуплоскости, определяемые каждым из ограничений.

  • Для определения целевой функции:
Экономико-математические методы

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

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

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

Возможно эта страница вам будет полезна:

Решение задач по ЭММ

Пример 1.5.

Найти максимальное и минимальное значения функции

Экономико-математические методы

при ограничениях

Экономико-математические методы

Решение:

Строим координатную плоскость Экономико-математические методы и наносим па

неё прямые — ограничения (рис. 1.6. а)). Первое уравнение неравенства можно преобразовать в равенство, уравнение границы или уравнение прямой (1) в отрезках Экономико-математические методы и построить её, откладывая па соответствующих осях Экономико-математические методы и Экономико-математические методы отрезки 3 и 8. Если в неравенство (1) подставить координаты точки 0(0;0), то неравенство будет 0 Экономико-математические методы24, что неверно, отсюда следует, что области решений будет принадлежать полуплоскость со стороны, противоположной началу координат. Аналогичным образом преобразуем второе неравенство: Экономико-математические методы и построим прямую (2). Области решений будет принадлежать полуплоскость с той стороны от прямой, где находится начало координат, так как при подстановке точки Экономико-математические методы получим верное неравенство 0Экономико-математические методы30. Преобразуем третье неравенство:

Экономико-математические методы

и построим прямую (3). Области решений будет принадлежать полуплоскость с той стороны от прямой, где находится начало координат, так как при подстановке точки Экономико-математические методы получим верное неравенство 0Экономико-математические методы6. Таким образом, область решений задачи представляет собой треугольник Экономико-математические методы.

Для определения максимума целевой функции строим градиент из начала координат Экономико-математические методы линию уровня Экономико-математические методы, проходящую через начало координат. Затем перемещаем её в область решений, градиент остаётся перпендикулярным к пей. В направлении этого вектора перемещаем линию уровня параллельно самой себе до точки А, которая является конечной точкой области решений. Эта точка, в которой целевая функция достигает максимума. Чтобы найти её координаты, решаем совместно второе и третье уравнения

Экономико-математические методы

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

Экономико-математические методы

Оптимальное решение

Экономико-математические методы

Чтобы найти минимальное значение целевой функции, линию

уровня передвигаем в направлении антиградиента Экономико-математические методы, до конечной точки Экономико-математические методы (рис. 1.6. б)). Получаем Экономико-математические методы. Координаты точки Экономико-математические методы получаем, решая совместно первое и третье уравнения

Экономико-математические методы

Следовательно, минимальное значение целевой функции будет

Экономико-математические методы

Оптимальное решение

Экономико-математические методы

Случай многих переменных

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

Экономико-математические методы

где Экономико-математические методы — число неизвестных, Экономико-математические методы — число линейно независимых уравнений системы ограничений.

Если условие (1.7) не выполняется, то задача графическим методом неразрешима.

При выполнении условия (1.7) решение задачи осуществляется в следующей последовательности.

  1. Выбираем две любые переменные, которые назовём свободными.
  2. Выражаем все остальные переменные через свободные, то есть, решаем систему ограничений задачи.
  3. Выражаем целевую функцию через свободные переменные.
  4. Полученную двухмерную задачу решаем обычным графическим методом.
  5. Определив координаты оптимального решения двухмерной задачи, подставляем их в ограничения исходной задачи и определяем остальные координаты оптимального решения.

Пример 1.6.

Найти решение задачи

Экономико-математические методы
Экономико-математические методы

Решение:

В качестве свободных переменных примем, например, Экономико-математические методы и Экономико-математические методы. Из уравнений ограничений выразим переменные Экономико-математические методы и Экономико-математические методычерез свободные:

Экономико-математические методы

Выразим целевую функцию Экономико-математические методы через свободные переменные Экономико-математические методы и Экономико-математические методы

Экономико-математические методы

Опуская неотрицательные переменные Экономико-математические методы и Экономико-математические методы, получаем задачу с двумя переменными

Экономико-математические методы

Графическое решение задачи показано на рис. 1.7.

Совместное решение уравнений, полученных из первого и четвёртого неравенств, даёт значения

Экономико-математические методы

При этом целевая функция будет равна

Экономико-математические методы

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

Экономико-математические методы

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

Экономико-математические методы

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

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

Пусть задача линейного программирования (1.1)-(1.5) задана в симметричной форме, то есть, ограничения даны в виде неравенств вида (1.3), (1.4). Симметричную задачу можно привести к каноническому виду. Для этого, в левые части неравенств (1.3), при знаке «Экономико-математические методы«, вводятся дополнительные (неотрицательные) переменные со знаком плюс, а в левые части неравенств (1.4), при знаке «Экономико-математические методы«, — со знаком минус. Эти дополнительные переменные называются балансовыми. Тогда все неравенства превращаются в равенства, и система линейных уравнений может быть решена обычными методами линейной алгебры, например, методом Гаусса.

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

Пример 1.8.

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

Экономико-математические методы

Преобразуем ограничения введением балансовых переменных

Экономико-математические методы

Тогда кроме условий

Экономико-математические методы

добавляются неравенства

Экономико-математические методы

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

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

Пример 1.9.

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

Экономико-математические методы
Экономико-математические методы

Решение:

В данном случае можно из второго уравнения выразить Экономико-математические методы а из первого уравнения выразить Экономико-математические методы

Экономико-математические методы

Затем воспользоваться выражением для Экономико-математические методы

Экономико-математические методы

Получили решение

Экономико-математические методы

Учитывая условия

Экономико-математические методы

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

Экономико-математические методы

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

Симплексный метод

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

  1. Задача приводится к каноническому виду.
  2. Выбираются базисные и свободные переменные. Переменные являются базисными, если они линейно независимы и соответствуют единичным векторам (чаще всего это балансовые переменные):
Экономико-математические методы

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

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

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

Пусть задача (1.1)-(1.5) максимизируется, а её система ограничений записана в симметричной форме

Экономико-математические методы

За счёт введения балансовых переменных

Экономико-математические методы

задача приведена к каноническому виду с условиями

Экономико-математические методы

Если балансовые переменные принять за базисные и выразить их через остальные переменные

Экономико-математические методы

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

В первом столбце таблицы 1.5 приводятся базисные переменные (Б.П.). Во втором столбце — свободные члены.

Экономико-математические методы

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

Алгоритм поиска решения будет следующим.

Этап 1. Определение начального опорного плана

Просматриваем столбец свободных членов таблицы 1.5, если в нём все элементы положительны, то приравниваем свободные переменные

Экономико-математические методы

к нулю и имеем опорный план

Экономико-математические методы

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

Выполняем следующие действия:

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

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

в) Делаем шаг симплексных преобразований. Составляем новую таблицу, в которой:

  • разрешающий элемент заменяется обратной величиной;
  • остальные элементы разрешающей строки и разрешающего столбца делятся иа разрешающий элемент. Для решения задачи максимизации функции при делении элементов столбца знаки меняются на противоположные (для минимизации — знаки строки меняются на противоположные);
  • базисная переменная строки и свободная переменная столбца меняются местами.

Замечание. 1*. Если в разрешающем столбце есть нулевой элемент, то строка, в которой он находится, остаётся без изменений.

Экономико-математические методы

Если в разрешающей строке есть нулевой элемент, то соответствующий столбец, остаётся без изменений.

2*. Если в процессе вычислений образуется строка, полностью состоящая из нулей, то она может быть отброшена.

Экономико-математические методы

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

Экономико-математические методы

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

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

Экономико-математические методы

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

Этап 2. Определение оптимального опорного плана.

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

Просматриваем Экономико-математические методы — строку:

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

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

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

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

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

Замечание 1. Если в разрешающем столбце есть нулевой элемент, то строка, в которой он находится, остаётся без изменений.

Если в разрешающей строке есть нулевой элемент, то соответствующий столбец, в котором он находится, остаётся без изменений.

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

Экономико-математические методы

где

Экономико-математические методы

будет оптимальной.

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

Экономико-математические методы

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

При решении задачи на минимум:

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

Случай вырождения

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

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

Устранение «зацикливания» возможно с помощью следующего правила. Если на каком-то этапе вычислений при выборе разрешающей строки возникает неопределённость, то есть оказывается

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

Пример 1.10.

Найти какой-либо опорный план задачи

Экономико-математические методы

Решение:

Приведем систему ограничений к каноническому виду введением неотрицательных балансовых переменных Экономико-математические методы и Экономико-математические методы

Экономико-математические методы

Балансовые переменные сделаем базисными

Экономико-математические методы

Составим симплексную таблицу (табл. 1.6)

Экономико-математические методы

Из таблицы (1.6) видно, что начальный опорный план есть, так-как в столбце свободных членов все элементы положительны — Экономико-математические методы. Можно найти другой опорный план. Для этого в Экономико-математические методы — строке выбираем элемент (-6), соответствующий переменной Экономико-математические методы, так как он является наибольшим по абсолютной величине отрицательным числом в Экономико-математические методы — строке. Столбец Экономико-математические методы будет разрешающим. Затем находим отношение элементов столбца свободных членов к элементам разрешающего столбца. Поместим эти отношения в столбец (С.С.). Минимальное значение находится в строке Экономико-математические методы. Эта строка будет разрешающей. Разрешающий элемент стоит на пересечении этой строки и столбца, он равен 4.

В таблице 1.7:

  • строка Экономико-математические методы получена делением разрешающей строки таблицы 1.6 на разрешающий элемент 4;
  • столбец Экономико-математические методы получен делением разрешающего столбца таблицы 1.6 на разрешающий элемент 4 и переменой знака на противоположный;

Остальные элементы вычислены по правилу прямоугольников, в том числе и элементы Экономико-математические методы — строки. Например, для вычисления элемента Экономико-математические методы и строим прямоугольник, показанный в таблице 1.6, и вычисляем этот элемент по формуле прямоугольников (1.10)

Экономико-математические методы

Аналогично вычислены остальные элемент таблицы 1.7. В новой таблице меняем местами переменные Экономико-математические методы и Экономико-математические методы.

В итоге, после одного шага симплексных преобразований, получен ещё один опорный план исходной задачи

Экономико-математические методы

Он так же, как и предшествующий не является оптимальным, так как в Экономико-математические методы — строке есть отрицательный элемент.

Пример 1.11.

Для предшествующей задачи найти оптимальный опорный план.

Решение:

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

Экономико-математические методы

В симплексном столбце таблицы 1.8 только один элемент, он и определяет разрешающую строку. Значит, разрешающим элементом будет элемент 3/2, расположенный па пересечении столбца, в котором находится Экономико-математические методы, и строки, в которой находится Экономико-математические методы. В таблице 1.9 меняем местами Экономико-математические методы и Экономико-математические методы. Вычислим только столбец свободных членов и элементы Экономико-математические методы — строки. Если в них все элементы будут положительными, то оптимальное решение достигнуто. В таблице 4 именно так и есть. Все элементы в столбце свободных членов и в Экономико-математические методы -строке положительны, значит достигнут оптимальный план.

Экономико-математические методы

При этом

Экономико-математические методы

а оптимальный план

Экономико-математические методы

Решение можно интерпретировать геометрически. На Рис. 1.10. точка Экономико-математические методы является опорным планом Экономико-математические методы, точка Экономико-математические методы — опорным планом Экономико-математические методы, точка Экономико-математические методы — оптимальным опорным планом Экономико-математические методы. Ломаная Экономико-математические методы (рис. 1.10) показывает путь, продвигаясь по которому от одного опорного плана к другому, достигнуто оптимальное решение.

Пример 1.12.

Найти оптимальный опорный план задачи

Экономико-математические методы

Решение:

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

Экономико-математические методы

Откуда

Экономико-математические методы

Составим симплексную таблицу (табл. 1.10).

Экономико-математические методы

В столбце свободных членов есть отрицательный элемент, следовательно, данный план

Экономико-математические методы

не является опорным.

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

Делим на этот элемент все остальные элементы разрешающей строки, и меняем местами неизвестные Экономико-математические методы и Экономико-математические методы.

Получаем табл. 1.11.

Экономико-математические методы

Полученный план является опорным, по не является оптимальным, так как один из элементов Экономико-математические методы — строки является отрицательным. Для отыскания оптимального плана необходимо выбрать в качестве разрешающего столбца тот, в котором находится элемент (-14). Но следует обратить внимание на то, что в соответствующем столбце нет ни одного положительного элемента. Это говорит о том, что задача не имеет решения. Геометрически это представлено на Рис. 1.11. Область решений является неограниченной.

Пример 1.13.

Найти оптимальное решение задачи

Экономико-математические методы

Решение:

Перейдём в ограничениях задачи от симметричной формы к канонической, для чего введём неотрицательные балансовые переменные Экономико-математические методы

Экономико-математические методы

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

Экономико-математические методы

Составим симплексную таблицу 1.12.

Экономико-математические методы

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

Экономико-математические методы

Чтобы найти опорный план, поступим следующим образом. Разрешающим столбцом будет столбец Экономико-математические методы. Выберем в качестве разрешающей строку Экономико-математические методы, так как симплексное отношение в ней наименьшее. Тогда разрешающим элементом будет Экономико-математические методы. Делим разрешающую строку на (-2), — разрешающий столбец — на Экономико-математические методы. Все остальные элементы вычисляем по правилу прямоугольника. Меняем местами переменные Экономико-математические методы и Экономико-математические методы. Получаем таблицу 1.13.

Найден начальный опорный план Экономико-математические методы (точка Экономико-математические методы рис. 1.12), все координаты которого неотрицательны. Этот план не является оптимальным, так как в Экономико-математические методы — строке имеются отрицательные элементы. Делаем шаг симплексных преобразований. Для этого выбираем в качестве разрешающего столбца тот, в котором наименьший элемент, а именно (-3/2). Вычисляем симплексные отношения. Единственное значение в симплексном столбце, которое даёт возможность определить разрешающую строку это значение 2, в строке, в которой находится неизвестная Экономико-математические методы. Таким образом, разрешающим элементом будет Экономико-математические методы.

Делаем обычные симплексные преобразования, получаем новую таблицу 1.14.

Экономико-математические методы

Очередной опорный план Экономико-математические методы (точка Экономико-математические методы рис.1.12). Он не является оптимальным, так как в Экономико-математические методы — строке есть ещё один отрицательный элемент. Необходимо сделать следующий шаг симплексных преобразований. Разрешающим столбцом будет столбец под переменной Экономико-математические методы. Вычисляем симплексные отношения. Наименьшим будет отношение 3/2, расположенное в строке, где находится переменная Экономико-математические методы. Тогда разрешающим элементом будет Экономико-математические методы.

Делаем обычный шаг симплексных преобразований, получаем таблицу 1.15, в которой все переменные и элементы Экономико-математические методы — строки положительны. Значит, найден оптимальный опорный план Экономико-математические методы (точка Экономико-математические методы рис. 1.12). Максимальное значение целевой функции Экономико-математические методы.

Экономико-математические методы

Геометрическое решение изображено на рис. 1.12. Точка Экономико-математические методы соответствует опорному плану Экономико-математические методы.

Точка Экономико-математические методы соответствует опорному плану Экономико-математические методы. Точка Экономико-математические методы — оптимальному опорному плану

Экономико-математические методы

Возможно эта страница вам будет полезна:

Помощь по экономико математическим методам

Пример 1.14.

Найти решение задачи

Экономико-математические методы

Решение:

Для решения задачи используем соотношение:

Экономико-математические методы

тогда получим

Экономико-математические методы

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

Экономико-математические методы

Балансовые переменные примем за базисные:

Экономико-математические методы

Составляем симплексную таблицу 1.16.

Экономико-математические методы

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

Экономико-математические методы

Находим опорный план. В строке Экономико-математические методы там, где свободный член отрицательный, находим наименьший элемент (-2), этот столбец Экономико-математические методы будет разрешающим. Вычисляем элементы симплексного столбца. Находим Экономико-математические методы. Следовательно, разрешающей строкой будет строка Экономико-математические методы, а разрешающим элементом будет (-2). Меняем местами Экономико-математические методы и Экономико-математические методы. Проделываем все вычисления одного шага симплексных преобразований. Получаем таблицу 1.17.

Полученный план

Экономико-математические методы

является опорным, так как все координаты его положительны, но не является оптимальным, так-как в Экономико-математические методы — строке есть отрицательный элемент (-5/2). Чтобы найти оптимальный план, сделаем столбец с элементом (-5/2) разрешающим. Вычислим симплексные отношения. Найдём

Экономико-математические методы

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

Экономико-математические методы

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

Экономико-математические методы

при этом значение функции

Экономико-математические методы

Тогда, минимум функции Экономико-математические методы будет

Экономико-математические методы

Метод искусственного базиса

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

Метод состоит в том, что в ограничения исходной задачи вводятся некоторые искусственные переменные. В целевую функцию эти искусственные переменные входят с коэффициентом Экономико-математические методы (Экономико-математические методы -некоторое число). При этом для задачи на максимум искусственные переменные входят в целевую функцию со знаком «минус», для задачи на минимум — со знаком «плюс». В общем виде математическая модель задачи записывается следующим образом:

Экономико-математические методы

при ограничениях

Экономико-математические методы
Экономико-математические методы

где Экономико-математические методы — дополнительные неотрицательные переменные.

Составленная задача называется Экономико-математические методы — задачей. Для задачи на минимум целевая функция имеет вид:

Экономико-математические методы

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

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

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

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

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

Теорема 1.5. Если Экономико-математические методы — задача неразрешима, то исходная задача также неразрешима либо по причине несовместности системы ограничений, либо по причине неограниченности функции.

Так как целевая функция состоит из двух частей

Экономико-математические методы

то при решении табличным симплекс — методом после Экономико-математические методы — строки необходимо ввести Экономико-математические методы — строку. Решение сначала осуществляется по Экономико-математические методы — строке. Выводимые из базиса искусственные переменные можно опускать, так как вводить их снова в базис нецелесообразно.

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

Первоначальная симплексная таблица для Экономико-математические методы — задачи имеет вид:

Экономико-математические методы

где Экономико-математические методы— коэффициенты при переменных Экономико-математические методы — слагаемого целевой функции.

Пример 1.6.

Найти решение методом искусственного базиса следующей задачи

Экономико-математические методы

Решение:

1. Составляем Экономико-математические методы — задачу. Уравнения системы ограничений не разрешены относительно естественных базисных переменных. Поэтому вводим в них искусственные переменные: Экономико-математические методы — в первое уравнение и Экономико-математические методы — во второе. В результате получим следующую Экономико-математические методы — задачу:

Экономико-математические методы
Экономико-математические методы
  • Выразим целевую функцию и базисные переменные через свободные переменные
Экономико-математические методы

Подставляем выражения для базисных переменных в целевую функцию Экономико-математические методы— задачи, получим:

Экономико-математические методы
  • Составим симплексную таблицу 1.20.
Экономико-математические методы
  • Расчёт ведём по Экономико-математические методы — строке. Сделав шаг симплексных преобразований с разрешающим элементом 14, придём к таблице 1.21. Переменную Экономико-математические методы после вывода из базиса мы исключили из дальнейшего рассмотрения (соответствующий ей столбец опустили). В этой таблице ещё содержится решение Экономико-математические методы — задачи
Экономико-математические методы
Экономико-математические методы
  • В качестве разрешающего выберем столбец Экономико-математические методы и снова делаем шаг симплексных преобразований с разрешающим элементом 24/14, (таблица 1.22).
Экономико-математические методы

Полученное решение

Экономико-математические методы

является оптимальным для Экономико-математические методы — задачи. Для исходной задачи оно ещё не является оптимальным, так как в Экономико-математические методы — строке есть отрицательный элемент.

  • Отбрасываем Экономико-математические методы — строку и по Экономико-математические методы — строке выбираем в качестве разрешающего первый столбец. В качестве разрешающего элемента принимаем 13/24. Делаем ещё шаг симплексных преобразований, результаты которого представлены в таблице 1.23.
Экономико-математические методы

Получили оптимальный план исходной задачи

Экономико-математические методы
Экономико-математические методы

Возможно эта страница вам будет полезна:

Курсовая работа по экономико математическим методам

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

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

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

Экономико-математические методы

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

Экономико-математические методы

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

Экономико-математические методы

Для двойственной

Экономико-математические методы

При записи двойственной задачи действуют следующие правила.

  1. Если прямая (исходная) задача решается на максимум (1.17) — (1.19) или (1.17) — (1.19), то двойственная к ней (1.20) — (1.22) или (1.20) — (1.22) — на минимум и наоборот.
  2. Коэффициенты целевой функции прямой задачи Экономико-математические методы становятся свободными членами для ограничений двойственной задачи.
  3. Свободные члены прямой задачи Экономико-математические методы, становятся коэффициентами двойственной целевой функции.
  4. Матрица ограничений двойственной задачи является транспонированной по отношению к матрице ограничений прямой задачи.
  5. Если прямая задача решается на максимум, то её система ограничений имеет в неравенствах знак « Экономико-математические методы » или « = ». Двойственная ей задача решается на минимум, и её система ограничений имеет вид неравенств типа « Экономико-математические методы » или « = ».
  6. Число ограничений прямой задачи равно числу переменных двойственной, а число ограничений двойственной — числу переменных прямой.
  7. Если прямая задача задана в симметричной форме с Экономико-математические методы переменными и при приведении её к канонической форме были добавлены ещё Экономико-математические методы переменных, то между переменными Экономико-математические методы и Экономико-математические методы устанавливается взаимно однозначное соответствие
Экономико-математические методы

Замечания.

  1. Исходной задачей может быть задача на минимум (1.20) — (1.22), тогда двойственная к ней будет задача на максимум (1.17) — (1.19).
  2. В теории двойственности исходная задача должна быть упорядоченной. То есть, если целевая функция задачи максимизируется. то ограничения — неравенства должны быть вида « Экономико-математические методы », если минимизируется, то вида « Экономико-математические методы ». Если в некоторых ограничениях это условие не выполняется, то их выполнение достигается умножением соответствующих ограничений па (-1).
  3. Если па Экономико-математические методы — переменную исходной задачи не наложено условие неотрицательности, то Экономико-математические методы — ограничение двойственной задачи будет равенством. В противном случае Экономико-математические методы — ограничение будет неравенством.
  4. В двойственной задаче условие неотрицательности накладывается на те переменные, которым в исходной задаче соответствовали ограничения со знаком неравенства.

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

Экономико-математические методы
Экономико-математические методы

Двойственной к ней будет задача

Экономико-математические методы

Задачи (1.23) и (1.24) образуют пару симметричных двойственных задач.

  • Пусть исходная задача имеет вид:
Экономико-математические методы

Двойственная к ней задача запишется в виде:

Экономико-математические методы

Задачи (1.25) и (1.26) образуют пару симметричных двойственных задач.

Пример 1.18.

Записать задачу двойственную к задаче

Экономико-математические методы

Решение:

Для исходной задачи двойственной к ней будет задача на минимум. Соответствующие матрицы Экономико-математические методы и Экономико-математические методы будут:

Экономико-математические методы

Тогда, двойственная задача будет иметь вид:

Экономико-математические методы

В соответствие с пунктами 3 и 4 замечаний на неизвестную Экономико-математические методы не наложено условие неотрицательности, так как во втором условии ограничений прямой задачи имеется знак равенства.

Пример 1.19.

Записать задачу двойственную к задаче

Экономико-математические методы

Решение:

Упорядочим запись исходной задачи. Так как решается задача на минимум, то неравенства в ограничениях должны иметь знаки « Экономико-математические методы ». Умножаем ограничения 1 и 3 на (-1).

Экономико-математические методы

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

Экономико-математические методы

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

Основные теоремы двойственности

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

Лемма 1. Если Экономико-математические методы — некоторый план исходной задачи (1.17)-(1.19), а Экономико-математические методы — произвольный план двойственной задачи (1.20) — (1.22), то значение целевой функции исходной задачи при плане Экономико-математические методы не превосходит значения целевой функции двойственной задачи при плане Экономико-математические методы, то есть,

Экономико-математические методы

Лемма 2. Если выполняется равенство

Экономико-математические методы

для некоторых планов х задачи (1.17) — (1.19) и у задачи (1.20) —

(1.22), то Экономико-математические методы — оптимальный план исходной задачи, а Экономико-математические методы — оптимальный план двойственной задачи.

Теорема 1.7. (первая теорема двойственности). Если одна из пары двойственных задач (1.17) — (1.19) или (1.20) — (1.22) имеет оптимальный план, то и другая имеет оптимальный план и значения целевых функций задач при их оптимальных планах равны между собой, то есть

Экономико-математические методы

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

Теорема 1.8. (вторая теорема двойственности). План

Экономико-математические методы

задачи (1.17) — (1.19) и план

Экономико-математические методы

задачи (1.20) — (1.22) являются оптимальными планами этих задач тогда и только тогда, когда для любого номера Экономико-математические методы выполняются равенства

Экономико-математические методы

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

В этом случае можно таблицу строить следующим образом

Экономико-математические методы

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

Пример 1.20.

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

если

даны следующие условия:

Экономико-математические методы

Решение:

Прямая задача максимизирует целевую функцию, следовательно, задача, двойственная к исходной, имеет вид:

Экономико-математические методы

При решении прямой задачи после трех шагов симплексных преобразований от таблицы 1.26 переходим к таблице 1.27, затем к таблице 1.28.

Экономико-математические методы

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

Экономико-математические методы

Базисным переменным исходной задачи Экономико-математические методы и Экономико-математические методы соответствуют свободные переменные двойственной Экономико-математические методы и Экономико-математические методы. Свободным переменным исходной задачи Экономико-математические методы и Экономико-математические методы, соответствуют базисные переменные двойственной Экономико-математические методы и Экономико-математические методы (табл. 1.28).

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

Экономико-математические методы

Возможно эта страница вам будет полезна:

Контрольная по экономико математическим методам

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

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

1) обе задачи имеют оптимальные планы;

2) планы имеет только одна задача;

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

Пример 1.22.

Пусть дана пара двойственных задач. Найти графическое решение обеих задач.

Экономико-математические методы

Решение:

Обе задачи содержат по две переменных. Следовательно, они разрешимы. По системе ограничений исходной задачи строим область допустимых решений (Рис. 1.13). Затем строим линию уровня для функции Экономико-математические методы, и передвигаем её параллельно самой себе в направлении вектора Экономико-математические методы, пока не достигнем крайней точки области допустимых решений.

Экономико-математические методы

Этой точкой будет являться точка Экономико-математические методы, то есть,

Экономико-математические методы

В точке Экономико-математические методы целевая функция достигает максимума

Экономико-математические методы

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

Экономико-математические методы

Между переменными существует взаимно однозначное соответствие

Экономико-математические методы

Базисным переменным исходной задачи Экономико-математические методы и Экономико-математические методы соответствуют свободные переменные двойственной Экономико-математические методы и Экономико-математические методы. Свободным переменным исходной задачи Экономико-математические методы и Экономико-математические методы, соответствуют базисные переменные двойственной Экономико-математические методы и Экономико-математические методы.

Двойственный симплекс — метод

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

Алгоритм двойственного симплекс — метода состоит в следующем.

Этап 1. Определение начального опорного плана (псевдоплана)

Заполняем исходную симплексную таблицу.

1.1. Просматриваем коэффициенты Экономико-математические методы — строки симплексной таблицы. Если среди них нет отрицательных, то делаем переход к пункту 2.1 поиска оптимального плана.

1.2. Если в Экономико-математические методы — строке имеются отрицательные элементы, то делаем следующие преобразования.

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

1.3. По найденному разрешающему элементу делаем шаг симплексных преобразований.

Этап 2. Определение оптимального плана

2.1. Просматриваем столбец свободных членов. Если среди них нет отрицательных элементов, то оптимальное решение достигнуто.

2.2. Если в столбце свободных членов есть отрицательные элементы, то делаем следующие преобразования.

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

2.3. С найденным разрешающим элементом делается шаг симплексных преобразований.

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

  1. Области решений обеих задач пустые.
  2. Одна задача имеет неограниченную область допустимых решений, другая — пустую.

Замечание 2. При решении задачи на максимум можно сделать замену Экономико-математические методы и находить минимум полученной функции Экономико-математические методы, взятому со знаком минус.

Пусть исходная двойственная задача сформулирована в виде

Экономико-математические методы

при ограничениях

Экономико-математические методы

Вычисления удобно проводить, используя следующую таблицу

Экономико-математические методы

Пример 1.23.

Двойственным симплекс-методом найти решение задачи

Экономико-математические методы

Решение:

Так как в Экономико-математические методы — строке (таблица 1.30) имеется отрицательная оценка (-4), то второй столбец таблицы 1 считается выделенным, то есть, разрешающим. В нём содержится единственное отрицательное число (-2). Строка, содержащая этот элемент, будет разрешающей и, соответственно, разрешающим является элемент (-2).

Находим отношения

Экономико-математические методы

Из двух одинаковых отношений можем выбрать любое. Например, возьмём второй столбец. Делаем шаг симплексных преобразований (табл. 1.31).

Смотрим элементы Экономико-математические методы — строки таблицы 1.31. Среди них нет отрицательных. Поэтому переходим ко второму этапу алгоритма — находим оптимальный план.

Экономико-математические методы

Просматриваем элементы столбца свободных членов. Среди них есть отрицательный элемент (-4). Следовательно, полученный план не является оптимальным. Принимаем строку, содержащую этот элемент, за разрешающую. Так как в Экономико-математические методы — строке есть нуль, то имеет место случай вырождения. Над нулём имеется элемент, равный 4, следовательно, этот элемент будет разрешающим. Соответственно, разрешающим будет первый столбец. С этим разрешающим элементом делаем шаг симплексных преобразований (табл. 1.32).

Экономико-математические методы

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

Экономико-математические методы

Минимальное значение функции Экономико-математические методы

Экономико-математические методы

Так как в Экономико-математические методы — строке есть нулевой коэффициент, то решений задачи бесконечное множество. Например, еще одно решение:

Экономико-математические методы

Пример 1.24.

Найти решение задачи двойственным симплекс -методом

Экономико-математические методы

Решение:

Двойственной к исходной задаче будет:

Экономико-математические методы

Приведём ограничения к каноническому виду:

Экономико-математические методы

Выразим базисные переменные

Экономико-математические методы

Исходная таблица будет иметь вид (табл. 1.33)

Экономико-математические методы

Строка Экономико-математические методы будет разрешающей. В ней свободный член отрицательный и наименьший из всех свободных членов. Тогда столбец Экономико-математические методы будет разрешающим. С разрешающим элементом 2 делаем шаг симплексных преобразований, получаем таблицу 1.34.

В полученной таблице нет оптимального решения, так как в столбце свободных членов есть отрицательный элемент (-1/2). Делаем следующие преобразования. Строка Экономико-математические методы будет разрешающей, а элемент (1/2) — разрешающим элементом. С этим элементом делаем шаг симплексных преобразований (табл. 1.35).

Экономико-математические методы

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

Экономико-математические методы

Минимальное значение функции

Экономико-математические методы

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

Анализ моделей на чувствительность

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

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

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

  • Анализ изменений запасов ресурсов позволяет ответить на два вопроса:

а) На сколько можно увеличить запас некоторого ресурса для улучшения полученного оптимального значения целевой функции?

б) На сколько можно снизить запас некоторого ресурса при сохранении полученного оптимального значения целевой функции?

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

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

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

а) Каков диапазон изменения того или иного коэффициента целевой функции, при котором не происходит изменения оптимального решения?

б) На сколько следует изменить тот или иной коэффициент целевой функции, чтобы сделать некоторый недефицитный ресурс дефицитным, и, наоборот, дефицитный ресурс сделать иедефицитным?

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

Пример 1.26.

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

Экономико-математические методы

Отпускная цена единицы продукции 1-го вида равна Экономико-математические методы = 2 ден. ед., 2-го вида — Экономико-математические методы = 3 ден. ед. Найти объем выпуска продукции каждого вида, максимизирующий суммарный доход производственного предприятия.

  1. Построить математическую модель и найти симплексным методом оптимальное решение задачи.
  2. Построить математическую модель двойственной задачи и найти ее оптимальное решение.
  3. Указать статус ресурсов.
  4. Определить, па сколько можно уменьшить запасы недефицитных ресурсов.
  5. Определить максимальное приращение дефицитных ресурсов.
  6. Определить наиболее выгодный ресурс.
  7. Оценить целесообразность приобретения Экономико-математические методы единиц 2-го ресурса стоимостью Экономико-математические методы ден. ед.
  8. Установить целесообразность ввода в производство нового вида продукции Экономико-математические методы, удельный расход ресурсов Экономико-математические методы на изготовление которой составляет Экономико-математические методы единиц, а отпускная цена готовой продукции равна Экономико-математические методы= 5 ден. ед.
  9. Привести пример анализа на чувствительность оптимального решения к изменению произвольного коэффициента целевой функции.

Решение:

  • Обозначим через Экономико-математические методы и Экономико-математические методы — объемы выпуска производственным предприятием продукции Экономико-математические методы и Экономико-математические методы соответственно.

Тогда математическая модель задачи примет вид (1.1)-(1.5):

Экономико-математические методы

Использование графического метода

Изобразим вектор Экономико-математические методы, граничные прямые

Экономико-математические методы

и построим многоугольник решений Экономико-математические методы, как показано на рис. 1.15.

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

В нашем примере максимальное значение целевой функции достигается в точке Экономико-математические методы — точке пересечения двух прямых: Экономико-математические методы и Экономико-математические методы. Оптимальное решение задачи:

Экономико-математические методы
Экономико-математические методы

Использован не симплекс-метода.

Преобразуем исходную математическую модель к каноническому виду

Экономико-математические методы

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

Допустимое базисное решение имеет вид Экономико-математические методы.

Построим начальную симплекс-таблицу 1.36.

Решение Экономико-математические методы не является оптимальным, так как в Экономико-математические методы — строке таблицы стоят отрицательные элементы.

Экономико-математические методы

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

Строку Экономико-математические методы определим в качестве разрешающей, так как ей соответствует наименьшее симплекс-отношение симплекс — столбца.

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

Делаем один шаг симплексных преобразований.

Таким образом, симплекс-таблица примет вид (1.37). Новое базисное решение Экономико-математические методы, хотя и улучшает значение целевой функции по сравнению с начальным, но не является оптимальным, поскольку в последней Экономико-математические методы — строке симплекс-

Экономико-математические методы

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

Выберем столбец Экономико-математические методы в качестве разрешающего, как содержащий отрицательный элемент в Экономико-математические методы — строке симплекс-таблицы 1.37.

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

Экономико-математические методы

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

  • Построим математическую модель двойственной задачи (1) -(3).
Экономико-математические методы

Оптимальное решение двойственной задачи (4) — (6) определить на основе оптимального решения прямой задачи Из теорем двойственности следует:

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

Экономико-математические методы

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

Значение переменной Экономико-математические методы двойственной задачи соответствует теневой цене Экономико-математические методы-го ресурса прямой задачи.

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

Экономико-математические методы

Оптимальное решение двойственной задачи будет

Экономико-математические методы
  • Определим статус ресурсов.

Использование графического метода.

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

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

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

для Экономико-математические методы — израсходован не полностью;
для Экономико-математические методы — израсходован полностью;
для Экономико-математические методы — израсходован полностью.

Использовапие симплекс-таблицы.

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

Таким образом, можно сделать следующие выводы:

1) ресурс Экономико-математические методы является недефицитным, поскольку соответствующая ему остаточная переменная Экономико-математические методы вошла в базис и равна 1,6 (величина избытка), а теневая цена Экономико-математические методы = 0;

2) ресурс Экономико-математические методы является дефицитным, поскольку соответствующая ему остаточная переменная Экономико-математические методы не вошла в базис и равна нулю (израсходован полностью), а теневая цепа Экономико-математические методы = 0,3 > 0;

3) ресурс Экономико-математические методы является дефицитным, поскольку соответствующая ему остаточная переменная Экономико-математические методы не вошла в базис и равна нулю (израсходован полностью), а теневая цена Экономико-математические методы = 0,8 > 0.

  • Запасы недефицитных ресурсов можно уменьшить на величину избытка без изменения значения целевой функции.

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

Максимальный расход ресурса Экономико-математические методы в точке Экономико-математические методы составляет 6,4 ед., т.е. величина избытка равна 8 — 6,4 — 1,6 ед. (балансовая переменная 1,6).

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

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

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

Использование графического метода.

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

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

Экономико-математические методы

Значение целевой функции в точке Экономико-математические методы составит

Экономико-математические методы

Следует, однако, заметить, что при смещении точки максимума от точки Экономико-математические методы до точки Экономико-математические методы дефицитными будут уже ресурсы Экономико-математические методы и Экономико-математические методы, в то время как ресурс Экономико-математические методы станет недефицитным.

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

Экономико-математические методы

Значение целевой функции в точке Экономико-математические методы(4; 4) составит

Экономико-математические методы

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

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

Экономико-математические методы

Значение целевой функции в точке Экономико-математические методы составит

Экономико-математические методы

Использование симплекс-таблицы.

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

Экономико-математические методы

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

Поэтому должно выполняться

Экономико-математические методы

Откуда

Экономико-математические методы

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

Запас ресурса Экономико-математические методы можно увеличить на 16 ед. с 40 до 56. При этом значение целевой функции увеличится на 0,3 х 16-4,8 и составит 15,2 + 4,8 — 20.

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

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

Для получения аналогичного результата необходимо решить задачу

Экономико-математические методы

в которой уже учтен прирост второго ресурса.

На основе полученной итоговой симплекс-таблицы 1.41

Экономико-математические методы

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

Для этого нужно решить систему неравенств

Экономико-математические методы

Откуда

Экономико-математические методы

Таким образом, запас ресурса Экономико-математические методы можно увеличить на 24 ед. с 56 до 80. При этом значение целевой функции увеличится па 0,17 х 24 — 4 и составит 20 + 4 — 24.

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

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

Экономико-математические методы

Как и для второго ресурса должно выполняться

Экономико-математические методы

Откуда

Экономико-математические методы

Таким образом, запас ресурса Экономико-математические методы можно увеличить на 8/3 ед. с 4 до 4 + 8/3 = 20/3. При этом значение целевой функции увеличится на 0,8 х 8/3 = 32/15 и составит 15,2 + 32/15 = 52/3.

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

Использование графического метода

Рассчитать значение теневой цепы можно по формуле (1.22). Сведем результаты графического анализа из п.п. 4 и 5 в таблицу 1.43 и определим теневые цены ресурсов

Экономико-математические методы

при перемещении прямой Экономико-математические методы до точки Экономико-математические методы; ** при перемещении прямой Экономико-математические методы от точки Экономико-математические методы до точки Экономико-математические методы; *** при перемещении прямой Экономико-математические методы до точки Экономико-математические методы.

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

Использование симплекс-таблицы

Как было сказано в п. 2, значение переменной Экономико-математические методы (теневую цену Экономико-математические методы-го ресурса) следует искать в последней строке итоговой симплекс-таблицы. Поэтому на основе полученной выше итоговой симплекс-таблицы 1.43 можно сделать следующий вывод: при изменении запаса ресурса Экономико-математические методы от 40 до 56 теневые цены ресурсов Экономико-математические методы будут соответственно равны Экономико-математические методы. Ресурс Экономико-математические методы будет наиболее выгодным. Дальнейшее увеличение запаса ресурса Экономико-математические методы от 56 до 80 изменяет статус ресурсов. Данную ситуацию мы анализировать не будем.

  • Увеличение запаса 2-го ресурса на Экономико-математические методы единиц находится в пределах устойчивости двойственных оценок (ранее было показано, что при изменении запаса ресурса Экономико-математические методы на 16 единиц от 40 до 56 теневая цена 2-го ресурса равна Экономико-математические методы). Поэтому данное дополнительное приобретение ресурса приведет к увеличению значения целевой функции (дохода предприятия) на 0,3 х 10 = 3 ден. ед. В то же время затраты возрастут на Экономико-математические методы ден. ед. Итоговая прибыль уменьшится на 2 ден. ед. (3 — 5 = -3). Следовательно, данное приобретение нецелесообразно.
  • С позиции эффективности производства в оптимальный план может быть включена лишь та продукция Экономико-математические методы-го вида, для которой выполняется условие
Экономико-математические методы

В нашей ситуации

Экономико-математические методы

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

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

Использование графического метода

Увеличение значения Экономико-математические методы или уменьшение значения Экономико-математические методы приводит к вращению прямой Экономико-математические методы, представляющей целевую функцию, вокруг точки Экономико-математические методы по часовой стрелке. Уменьшение значения или увеличение значения Экономико-математические методы — к вращению против часовой стрелки.

Когда наклон прямой Экономико-математические методы станет равным наклону прямой Экономико-математические методы, получим две альтернативные оптимальные угловые точки Экономико-математические методы и Экономико-математические методы. Аналогично для прямой Экономико-математические методы — получим точки Экономико-математические методы и Экономико-математические методы. В этом случае при различных значениях переменных Экономико-математические методы и Экономико-математические методы целевая функция будет иметь одинаковые значения.

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

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

Экономико-математические методы

Следовательно,

Экономико-математические методы

При уменьшении Экономико-математические методы до 0 прямая Экономико-математические методы совпадет с прямой Экономико-математические методы.

Поэтому при 0 < Экономико-математические методы< 5 точка Экономико-математические методы будет оптимальной точкой.

Использование симплекс-таблицы

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

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

Экономико-математические методы
Экономико-математические методы

Откуда

Экономико-математические методы

Таким образом, при изменении Экономико-математические методы — коэффициента целевой функции при переменной Экономико-математические методы — от 0 (3 — 3 = 0) до 5 (3 + 2 — 5) оптимальные значения переменных остаются неизменными.

Применение Excel «Поиск решения»

Инструкция по использованию надстройки «Поиск решения»

Надстройка «Поиск решения» из пакета электронных таблиц Microsoft Excel может быть использоваиа для решения широкого спектра задач исследования операций, в том числе и задач линейного программирования.

Диалоговое окно надстройки «Поиск решения» представлено на рис. 1.16.

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

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

В поле «Изменяя ячейки» задаются адреса ячеек, выделенных для хранения искомых неизвестных. Ячейки должны влиять (прямо или косвенно) на значение целевой функции.

Экономико-математические методы

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

Кнопка «Предположить» позволяет автоматически определить ячейки, влияющие на целевую функцию.

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

В поле «Ограничения» с помощью кнопок «Добавить», «Изменить», «Удалить» надо сформировать список граничных условий. Процесс формирования граничных условий производится следующим образом. При первом нажатии па кнопку «Добавить» появляется диалоговое окно «Добавление ограничений» (рис. 1.17). В поле «Ссылка па ячейку» указывается адрес ячейки (или диапазон ячеек), содержащей левую часть граничного условия. Затем в поле со списком выбирается знак ограничения. Наконец, в поле «Ограничение» задается правая часть граничного условия.

Экономико-математические методы

Нажатие кнопки «Добавить» позволяет в том же окне перейти к вводу очередного граничного условия. Кнопка «ОК» служит для завершения ввода ограничений оптимизационной задачи.

Кнопка «Восстановить» (рис. 1.16) предназначена для очистки полей диалогового окна и возврату к заданным по умолчанию параметрам поиска решения.

Кнопка «Параметры» из диалогового окна «Поиск решения» (рис. 1.16) позволяет выполнять ряд настроек (рис. 1.18), влияющих на процесс поиска. Это дает возможность в некоторых случаях найти более точное решение либо получить решение задачи, которое при заданных по умолчанию параметрах не может быть найдено.

Выделяют следующие параметры поиска решения.

  • Максимальное время — это время в секундах, которое может быть затрачено па поиск решения. Максимально допустимое значение — 32767. По умолчанию задано 100 секунд.
  • Предельное число итераций (шагов) — количество действий (вычисление очередного значения и проверка, насколько оно подходит в качестве ответа), которые могут быть сделаны. Максимально допустимое значение — 32767. По умолчанию задано 100 промежуточных значений.
  • Относительная погрешность задает, насколько близко друг к другу расположены два последовательных приближения. Задается числом в диапазоне от 0 до 1. Чем больше десятичных знаков указано после запятой, тем выше точность вычислений.
Экономико-математические методы
  • Допустимое отклонение используется в случае целочисленных ограничений на изменяемые ячейки. Определяет допуск отклонения полученного ответа от возможного наилучшего решения. Задается в процентах. Увеличение допустимого отклонения приводит к уменьшению времени поиска.
  • Сходимость — относительное изменение значения в целевой ячейке за последние пять шагов. Если эта величина становится меньше указанного числа, поиск прекращается. Задается числом в диапазоне от 0 до 1. Параметр применим только к нелинейным задачам. Уменьшение значения в поле сходимость (улучшение сходимости) приводит к увеличению времени поиска оптимального решения.
  • Линейная модель приводит к использованию методов линейного программирования, что ускоряет процесс поиска оптимального решения для линейных задач.
  • Неотрицательные значения позволяет задать нулевую нижнюю границу для тех изменяемых ячеек, для которых она не была указана в поле Ограничение.
  • Автоматическое масштабирование приводит к автоматической нормализации входных и выходных значений, существенно различающихся по величине.
  • Показывать результаты итераций выводит промежуточный результат и делает паузу после каждого шага вычисления.

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

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

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

Математические модели могут быть сохранены и прочитаны с помощью кнопок «Сохранить модель» и «Загрузить модель» (рис. 1.18). Это позволяет хранить па рабочем листе более одной модели оптимизации.

Кнопка «Выполнить» диалогового окна «Поиск решения» (рис. 1.16) запускает процесс поиска оптимального решения. Прервать ход вычислений можно нажатием клавиши Esc.

При успешном окончании поиска (рис. 1.19) можно сохранить найденное решение, восстановить исходные значения изменяемых ячеек, сформировать один или несколько типов отчетов (по результатам, по устойчивости, по пределам). Существует также возможность найти ряд решений с различными исходными данными или параметрами задачи, а затем сравнить их между собой с помощью Диспетчера сценария (кнопка «Сохранить сценарий»).

Экономико-математические методы

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

Для создания отчета выделите мышкой в одноименном списке (рис. 1.19) требуемый тип отчета (или все типы) и нажмите кнопку «ОК». Каждый отчет будет помещен на новый лист рабочей книги.

Отчет по результатам состоит из трех таблиц.

  1. Первая таблица содержит сведения о характере исследования функции (Максимум, Минимум или Значение); адрес (Ячейка) и имя (Имя) ячейки, содержащей формулу для вычисления целевой функции; значения целевой функции до начала (Исходное значение) и после проведения вычислений (Результат).
  2. Вторая таблица содержит информацию об искомых переменных (изменяемых ячейках): их адреса (Ячейка) и имена (Имя); значения до (Исходное значение) и после вычислений (Результат).
  3. Третья таблица содержит данные об ограничениях задачи: адреса (Ячейка), имена (Имя) и значения (Значение) левых частей ограничений; вид ограничений (Формула). Столбец Статус показывает равны ли между собой левые и правые части ограничений (связанное) или нет (не связан.). Столбец Разница — разницу между правыми и левыми частями ограничений.

Отчет по устойчивости состоит из двух таблиц.

  • Первая таблица содержит следующую информацию: адреса (Ячейка) и имена (Имя) изменяемых ячеек; оптимальное решение задачи (Результ. значение); Нормир. стоимость, показывающую, как изменяется значение целевой функции при принудительном увеличении нижней границы изменения переменных на единицу; коэффициенты целевой функции (Целевой Коэффициент); предельные значения изменений коэффициентов целевой функции, при которых сохраняется набор переменных, входящих в оптимальное решение (Допустимое Увеличение, Допустимое Уменьшение).
  • Вторая таблица содержит аналогичные значения для ограничений: адреса (Ячейка), имена (Имя) и значения (Результ. значение) левых частей ограничений; двойственные оценки, которые показывают, как изменится целевая функция при увеличении правых частей ограничений на единицу (Теневая Цена); правые части ограничений (Ограничение Правая часть); предельные значения изменений ресурсов, при которых сохраняется оптимальный набор переменных, входящий в оптимальное решение (Допустимое Увеличение, Допустимое Уменьшение).

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

Отчет по пределам показывает адрес (Ячейка), имя (Целевое Имя) и оптимальное значение (Значение) целевой функции; адреса (Ячейка), имена (Изменяемое Имя) и оптимальное значение (Значение) изменяемых ячеек; нижние пределы изменения значений переменных и значения целевой функции на нижнем пределе (Нижний предел. Целевой результат); верхние пределы изменения значений переменных и значения целевой функции на верхнем пределе (Верхний предел. Целевой результат).

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

Возможно эта страница вам будет полезна:

Заказать работу по экономико математическим методам

Решение задачи с использованием пакета MS Excel

Рассмотрим методику решения ЗЛП средствами пакета электронных таблиц MS Excel и возможность поведения экопомического анализа полученных результатов на примере решения задачи из примера 18.

Реализация расчетных формул представленной математической модели средствами MS Excel показана на рис. 1.20.

Ячейки ВЗ:С5 содержат удельный расход ресурсов Экономико-математические методы для изготовления каждого вида продукции.

Ячейки ЕЗ:Е5 — имеющиеся в наличии суточные запасы Экономико-математические методы для каждого типа ресурсов.

В ячейках В6:С6 находится цепа Экономико-математические методы единицы продукции каждого вида (удельный доход).

Ячейки В7:С7 отведены под значения неизвестных Экономико-математические методы (оптимальный план выпуска продукции).

Экономико-математические методы

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

Экономико-математические методы

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

Ячейки D3:D5 содержат формулы для расчета затрат ресурсов каждого типа при производстве указанного количества продукции каждого вида.

Выделим ячейку, содержащую целевую функцию (D6). Теперь па вкладке «Данные» в группе «Анализ» выберем команду «Поиск решения» и заполним диалоговое окно надстройки «Поиск решения» как показано на рис. 1.21.

Использование кнопки «Предположить» в пашем примере для попытки автоматического определения изменяемых ячеек приведет к неверному результату (В6:С6). Это обусловлено тем, что ячейки В6:С’6 (цена единицы продукции каждого вида), хоть и влияют на формирование значения суммарного дохода предприятия, но не должны изменяться в ходе решения задачи.

Экономико-математические методы

Не забудьте установить флажок параметра «Линейная модель».

Нажмем кнопку «Выполнить» для поиска оптимального решения сформулированной ЗЛП.

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

Решение сформулированной задачи дает следующие результаты:

Экономико-математические методы

Максимальный доход предприятия при этом составит 15,2 ден. ед.

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

Отчет по результатам (рис. 1.22) позволяет оценить статус имеющихся ресурсов.

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

В столбце «Статус» отчета по результатам состояние «связанное» определяет дефицитный ресурс, а «не связан.» — недефицитный. В нашем случае дефицитными ресурсами являются ресурсы Экономико-математические методы и Экономико-математические методы. Суточный запас ресурса Экономико-математические методы, напротив, превышает потребность на 1,6 ед. (см. столбец «Разница»). Запас этого ресурса можно уменьшить на величину избытка без изменения значения целевой функции.

Столбец «Теневая цена» отчета по устойчивости (рис. 1.23) показывает решение задачи

Экономико-математические методы

которая является двойственной к исходной. Решение двойственной задачи имеет вид:

Экономико-математические методы

Решение двойственной задачи также позволяет определить наиболее выгодный ресурс из дефицитных ресурсов. В нашем случае при вложении дополнительных средств предпочтение следует отдать ресурсу Экономико-математические методы

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

В нашем случае, если цены на продукцию Экономико-математические методы и Экономико-математические методы будут изменяться в пределах

Экономико-математические методы

оптимальным планом производства будет

Экономико-математические методы

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

Так изменение запаса недефицитного ресурса Экономико-математические методы в пределах

Экономико-математические методы

не меняет точку оптимального решения.

В то же время при изменении запасов дефицитных ресурсов Экономико-математические методы и Экономико-математические методы в диапазоне

Экономико-математические методы

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

Экономико-математические методы
Экономико-математические методы

Транспортные задачи

Понятие «транспортная задача» (ТЗ) охватывает круг задач транспортного характера и других, связанных с транспортными общей математической моделью. Общим для них является распределение ресурсов, находящихся у Экономико-математические методы поставщиков Экономико-математические методы (производителей), по Экономико-математические методы потребителям Экономико-математические методы этих ресурсов.

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

1) прикрепление потребителей ресурса к производителям;

2) привязка пунктов отправления к пунктам назначения;

3) взаимная привязка грузопотоков прямого и обратного направлений;

4) отдельные задачи оптимальной загрузки промышленного оборудования;

5) оптимальное распределение объемов выпуска промышленной продукции между заводами-изготовителями и др.

В общем виде транспортную задачу можно сформулировать следующим образом.

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

Обозначим через Экономико-математические методы объем перевозок от Экономико-математические методы-го поставщика Экономико-математические методы-ому потребителю. Математическая модель задачи имеет вид: — общая сумма затрат на перевозку груза должна быть минимальной

Экономико-математические методы
  • объем поставок Экономико-математические методы-го поставщика должен равняться количеству имеющегося у него груза
Экономико-математические методы
  • объем поставок Экономико-математические методы-ому потребителю должен быть равен его спросу
Экономико-математические методы
  • объемы поставок должны выражаться неотрицательными числами
Экономико-математические методы
  • суммарный объем отправляемых грузов равен суммарному объему потребностей в этих грузах по пунктам назначения
Экономико-математические методы

Если транспортная задача имеет вид (2.1.1) — (2.1.5), то она называется закрытой (сбалансированной), если не выполняется условие (2.1.5), — открытой (несбалансированной).

Открытую транспортную задачу необходимо свести к закрытой:

1) в случае перепроизводства — ввести фиктивного потребителя Экономико-математические методы, то есть фиктивный Экономико-математические методы столбец, с необходимым объемом потребления

Экономико-математические методы

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

2) в случае дефицита — ввести фиктивного поставщика Экономико-математические методы, то есть фиктивную Экономико-математические методы строку, с недостающим объемом отправляемых грузов

Экономико-математические методы

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

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

Постановка транспортной задачи бывает в сетевой или матричной формах. Матричная форма позволяет существенно сократить трудоёмкость расчётов. Сетевая форма в наглядном виде даёт решение задачи.

Модель трапспортной задачи является моделью линейного программирования. Её оптимальный план можно найти симплексным методом. Однако, матрица системы ограничений специфична, что позволяет существенно упростить решение задачи.

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

Экономико-математические методы

Транспортные задачи имеют следующие особенности:

1) распределению подлежит однородный груз;

2)основные ограничения задачи описываются только уравнениями;

3) все неизвестные имеют одинаковые единицы измерения;

4) во всех уравнениях коэффициенты при неизвестных равны единице;

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

Все методы решения транспортной задачи делятся на две группы:

1) последовательного улучшения опорного плана;

2) последовательного сокращения невязок.

К первой группе относятся: распределительный метод, метод потенциалов и его модификации. Ко второй — методы: дифференциальных рент, разрешающих слагаемых, венгерский метод и другие.

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

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

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

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

Наиболее простыми методами построения начального опорного плана являются методы: северо — западного угла, минимального (максимального) элемента и Фогеля.

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

Решение задачи всегда начинается с определения начального опорного плана. В соответствие с теоремой о структуре координат опорного плана задачи линейного программирования, в невырожденном опорном плане должно содержаться Экономико-математические методы отличных от нуля координат, где Экономико-математические методы — ранг системы ограничений (2.1.2)-(2.1.4), равный Экономико-математические методы.

Допустимый план транспортной задачи в матричном виде является опорным планом тогда и только тогда, когда: 1) по занятым клеткам нельзя построить замкнутый контур (цикл); 2) число заполненных клеток равно Экономико-математические методы.

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

В цикл могут входить и самопересекающиеся линии (рис.2.1 в), но в этом случае точки самопересечения не являются вершинами цикла.

Экономико-математические методы

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

Заполнение распределительной таблицы начинается с клетки левого верхнего («северо — западного») угла, двигаясь либо по строке вправо, либо по столбцу вниз.

Алгоритм метода будет следующим.

  • Находим для клетки (1,1) Экономико-математические методы. Если Экономико-математические методы то клетку (1,1) заполняем поставкой Экономико-математические методы и вычёркиваем из рассмотрения первую строку как удовлетворённую. По первому столбцу опускаемся вниз и рассматриваем клетку (2,1). В неё помещаем поставку Экономико-математические методы.
  • Если Экономико-математические методы то клетку (1,1) заполняем поставкой, равной Экономико-математические методы вычёркиваем первый столбец. По первой строке движемся вправо. Для клетки (1,2) вычисляем Экономико-математические методы. Если Экономико-математические методы, то в клетку (1,2) записываем поставку, равную Экономико-математические методы, и проверяем условие Экономико-математические методы. Если выполняется равенство, то переходим в клетку (2,2), а первую строку вычёркиваем, как удовлетворённую.

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

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

Недостатком метода является то, что построенный опорный план, как правило является далёким от оптимального, так как при его построении игнорируются тарифы Экономико-математические методы.

Пример 2.1.

Найти опорный план задачи, приведённой в таблице2.2, методом «северо — западного» угла.

Экономико-математические методы

Решение:

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

Экономико-математические методы

Построение начального опорного плана начинаем с клетки (1,1). Так как

Экономико-математические методы

то в клетку (1;1) помещаем поставку Экономико-математические методы, и вычёркиваем первый столбец, так как потребности потребителя Экономико-математические методы удовлетворены. Первая строка остаётся не удовлетворённой, поскольку Экономико-математические методы, следовательно, движемся вправо по первой строке.

Рассматриваем клетку (1,2). Для неё максимальная поставка

Экономико-математические методы

Тогда, первая строка получается удовлетворённой.

Переходим ко второй строке. Переход ведём по столбцу, соответствующему последней заполненной клетке, то есть — по второму. Рассматриваем клетку (2;2). Максимальная поставка для неё равна

Экономико-математические методы

Записываем в клетку (2;2) поставку Экономико-математические методы. Вторая строка ещё не полностью удовлетворена, так как сумма поставок на ней равна Экономико-математические методы. Движемся вправо по этой же строке, переходим к клетке (2;3). Для неё находим

Экономико-математические методы

Помещаем в клетку (2;3) Экономико-математические методы. Вторая строка станет удовлетворённой. По третьему столбцу переходим на третью строку. Рассматриваем клетку (3;3). Для неё

Экономико-математические методы

Записываем в клетку (3;3) поставку Экономико-математические методы. Движемся вправо по третьей строке. Переходим к клетке (3;4). Для неё поставка

Экономико-математические методы

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

Экономико-математические методы

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

Экономико-математические методы

Метод минимального элемента

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

Рассмотрим на примере.

Пример 2.2.

Найти начальный опорный план методом минимального элемента.

Экономико-математические методы

Решение:

Выбираем клетку (2:1) таблицы 2.3, имеющую наименьший тариф, равный 1. В неё можно поместить максимальную поставку, равную Экономико-математические методы. Есть ещё одна клетка с таким же тарифом (3;4). В неё можно поместить величину поставки такого же объёма, что и в рассмотренную клетку (2;1). Поэтому из них можно взять любую. Выберем клетку (2;1). Первый столбец вычеркнем, так как потребности потребителя Экономико-математические методы полностью удовлетворены. Далее переходим в клетку (2;2) с наименьшим в этой строке тарифом 2. В эту клетку можно загрузить поставку Экономико-математические методы. Потребности второй строки полностью удовлетворены, и поэтому она может быть вычеркнута. Просматриваем второй столбец. В нём наименьший тариф 7 в первой строке. Однако потребности потребителя Экономико-математические методы, уже удовлетворены, следовательно, в клетке (1;2) ставим значащий нуль и второй столбец можно вычеркнуть. Продвигаемся по первой строке. В ней наименьший тариф 3 в клетке (1;3). Заносим в эту клетку поставку Экономико-математические методы. Потребности потребителя Экономико-математические методы полностью удовлетворены. Следовательно, третий столбец может быть вычеркнут. Поскольку у поставщика Экономико-математические методы ещё не вывезен весь запас, то по первой строке переходим в клетку (1;4), так как в ней меньший тариф 5. Загружаем в неё поставку Экономико-математические методы. У поставщика Экономико-математические методы всё распределено, закрываем эту строку. По столбцу 4 перемещаемся в единственную, оставшуюся свободной клетку (3;4) и помещаем туда оставшуюся поставку Экономико-математические методы. Весь запас распределён. В результате получен начальный опорный план

Экономико-математические методы

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

Экономико-математические методы

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

  • Найдём опорный план исходной задачи, рассматривая по столбцам таблица2.4. Решение начинаем с первого столбца. Минимальный тариф в нём равен 1 и находится в клетке (2:1). Заполняем эту клетку, поместив в неё поставку, равную Экономико-математические методы. Первый столбец заполнен. Он исключается из дальнейшего рассмотрения.

Переходим ко второму столбцу. Минимальный тариф в нём равен 2 и находится в клетке (2;2). Загружаем эту клетку поставкой Экономико-математические методы. Второй столбец и вторая строка оказываются загруженными. Исключаем их из дальнейшего рассмотрения.

Экономико-математические методы

Рассматриваем третий столбец. Минимальный тариф в нём среди свободных равен 3 и находится в клетке (1;3). Загружаем эту клетку поставкой Экономико-математические методы. Третий столбец заполнен. Исключаем его из дальнейшего рассмотрения.

Переходим к четвертому столбцу. Минимальный тариф в нём равен 1 и находится в клетке (3;4). Загружаем эту клетку поставкой Экономико-математические методы. Третья строка заполнена, а четвёртый столбец ещё нет. В нём осталась единственная свободная клетка (1;4). Помещаем в неё поставку Экономико-математические методы.

Четвёртый столбец и третья строка — заполнены.

Таким образом, получили план, в котором число заполненных клеток равно 5 и не равно

Экономико-математические методы

Необходимо ввести нулевую поставку. Введём её так, чтобы по заполненным клеткам не было циклов. Например, в клетку (3;1). Окончательно опорный план будет иметь вид:

Экономико-математические методы

Значение функции па этом плане будет равно

Экономико-математические методы

Метод Фогеля

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

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

Экономико-математические методы

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

Пример 2.3.

Найти опорный план задачи (таблица 2.5) методом Фогеля.

Решение:

Экономико-математические методы
  1. Находим разность между двумя минимальными тарифами по столбцам и записываем в строку, соответствующую первому ходу (внизу таблицы 2.6).Для первого столбца минимальные тарифы равны 1 и 2. Разность между ними равна 2-1 = 1. Для второго столбца минимальными тарифами являются 3 и 4. Разность между ними также равна единице. И так производим вычисления по всем столбцам.
  2. Аналогично первому шагу находим разности между минимальными тарифами по строкам и записываем их в столбце, расположенном правее таблицы. Для первой строки минимальными тарифами являются 1 и 2. Их разность равна единице, и так вычисляем по всем строкам.
  3. Из элементов полученных строки и столбца разностей выбираем наибольший. В рассматриваемом примере максимальный элемент равен 6. Он соответствует пятому столбцу Экономико-математические методы. (В таблице 2.6 он взят в скобки).
  4. В пятом столбце, соответствующем выбранному максимальному элементу, среди разностей минимальных тарифов помещаем поставку в клетку, соответствующую минимальному тарифу. Минимальный тариф в данном случае Экономико-математические методы. Объём помещаемой в выбранную клетку поставки определяем как в методе «северозападного» угла:
Экономико-математические методы

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

  • С оставшейся таблицей поступаем аналогичным образом, то есть, переходим к пункту 1 — 4.

Из таблицы 2 видим, что максимальная разность на втором шаге равна 4 и соответствует третьему столбцу Экономико-математические методы, на третьем шаге равна 3 и соответствует четвёртому столбцу. На четвертом шаге максимальная разность равна 3 и соответствует четвёртой строке Экономико-математические методы.

На пятом шаге равна 6 и соответствует третьей строке Экономико-математические методы. После первого хода рассматриваем таблицу 2.7.

Экономико-математические методы

После второго хода рассматриваем таблицу 2.8, а после третьего хода рассматриваем таблицу 2.9.

Экономико-математические методы

После четвёртого хода рассматриваем таблицу 2.10

Экономико-математические методы

На пятом ходе заполняем клетку (2;4). Помещаем в неё поставку Экономико-математические методы. Полученный в процессе решения план показан в таблице 2. Получили, что число заполненных клеток равно Экономико-математические методы. Поэтому вводим две нулевые поставки:

Экономико-математические методы

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

Экономико-математические методы

Количество вычислений значительно сокращается при использовании модифицированного метода Фогеля. В этом методе разности выбираются обычным методом Фогеля, а в рассмотрение включаются строки или столбцы, имеющие наибольшее значение произведения разности на объём потребления или производства. Так для рассмотренного примера на первом шаге необходимо включить пятый столбец (6-50 = 30), на втором третий столбец Экономико-математические методы и так далее. Значение функции на этом плане равно

Экономико-математические методы

Метод максимального элемента

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

Экономико-математические методы

при всех прочих условиях (2.1.2)-(2.1.5).

В этом случае в распределительной таблице начинаем поиск начального опорного плана с наибольшего тарифа. Дальше действуем так же, как в методе минимального элемента.

Пример 2.4.

Найти начальный опорный план методом максимального элемента.

Экономико-математические методы

Решение:

Начинаем с клетки (3;3) таблицы 2.11 с наибольшим тарифом 15. Загружаем в неё поставку Экономико-математические методыЭкономико-математические методы. Третий потребитель Экономико-математические методы удовлетворён, значит вычёркиваем третий столбец, но не удовлетворён поставщик Экономико-математические методы.

Следующий наибольший тариф в третьей строке равен 10. Загружаем клетку (3;2) поставкой Экономико-математические методы Экономико-математические методы. Поставщик Экономико-математические методы удовлетворён, вычеркиваем третью строку. Не удовлетворён потребитель Экономико-математические методы. Во втором столбце наибольший тариф в клетке (1;2) равный 7. Загружаем в эту клетку поставку

Экономико-математические методы

Потребитель Экономико-математические методы удовлетворён, по не удовлетворён поставщик Экономико-математические методы. Из оставшихся не вычеркнутых столбцов 4 и 1 наибольший тариф в столбце 1, он равен 6. Загружаем в клетку (1;1) поставку

Экономико-математические методы

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

Экономико-математические методы

Потребитель Экономико-математические методы удовлетворён. Остаётся незагруженной единственная клетка (2;4). В неё загружаем оставшуюся во второй строке поставку 150-50=100. Начальный опорный план найден. В нём отсутствуют замкнутые циклы. Число загруженных клеток соответствует требованиям

Экономико-математические методы

таблица 2.12.

Экономико-математические методы

Найденный план имеет вид:

Экономико-математические методы

Этому плапу соответствует значение целевой функции

Экономико-математические методы

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

Методы оптимизации опорного плана

Метод потенциалов

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

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

Решение транспортной задачи заключается в определении такой системы потенциалов, для которой выполняются условия:

для свободных клеток

Экономико-математические методы

Для заполненных клеток

Экономико-математические методы

Если условия (2.3.1) и (2.3.2) выполняются, то решением будет план Экономико-математические методы, соответствующий полученной системе потенциалов, является оптимальным. В данном случае для любой пары пунктов Экономико-математические методы и Экономико-математические методы, связанных транспортными связями, разность потенциалов равна стоимости перевозок единицы продукции между этими пунктами. Решение Экономико-математические методы называют потенциальным, а условия (2.3.1) и (2.3.2) — условиями потенциальности. Чтобы допустимый опорный план был оптимальным, необходимо и достаточно, чтобы он удовлетворял условиям потенциальности.

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

Полученный план проверяется на оптимальность.

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

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

  • Для небазисных (свободных) клеток определяют оценки
Экономико-математические методы

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

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

Пусть

Экономико-математические методы

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

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

В вершинах контура ставим знаки: в перспективной вершине (+), в следующей (-) и так далее, чередуя знаки. Делается ли обход по часовой стрелке, или — против, безразлично.

Из всех вершин, где стоит знак (-), выбираем наименьшую поставку

Экономико-математические методы

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

Остальные перевозки не изменяются. За итерацию целевая функция уменьшается на величину Экономико-математические методы.

Снова переходим к пункту 2. И так далее, до получения оптимального решения, то есть, когда во всех загруженных клетках будет удовлетворяться условие (2.3.3).

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

Если в оптимальном плане Экономико-математические методы есть базисные переменные Экономико-математические методы, то оптимальный план не единственный.

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

Экономико-математические методы

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

Замечания.

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

Пример 2.6.

Методом потенциалов найти оптимальный план задачи минимизирующий транспортные расходы (табл.2.35)

Экономико-математические методы

Решение:

1. Пусть опорный план получен методом минимального элемента (табл.2.36).

Экономико-математические методы

Опорный план

Экономико-математические методы

Значение функции Экономико-математические методы Количество заполненных клеток Экономико-математические методы. Опорный план имеет именно столько заполненных клеток.

  • Для всех заполненных клеток составляем условие потенциальности
Экономико-математические методы
  • Для всех свободных клеток определяем оценки Экономико-математические методы и проверяем выполнение условий оптимальности при решении задачи па минимум:
Экономико-математические методы

Оценки Экономико-математические методы и Экономико-математические методы больше нуля. Выберем перспективную клетку (1;3)и обозначим её(*).

Для выбранной перспективной клетки строим замкнутый контур (табл.2.36). Величина сдвига по циклу

Экономико-математические методы

Получим новый опорный план (табл.2.37).

Экономико-математические методы
Экономико-математические методы

То есть

Экономико-математические методы

Целевая функция:

Экономико-математические методы

Количество занятых клеток равно 5.

Для полученного опорного плана составляем новую систему потенциалов:

Экономико-математические методы

Оценки свободных клеток

Экономико-математические методы

Полученный план является оптимальным

Экономико-математические методы
Экономико-математические методы

Суммарные затраты — функция Экономико-математические методы. Оптимальный план не единственный, так как среди оценок есть одна равная нулю.

Пример 2.7.

Методом потенциалов найти решение транспортной задачи минимизирующий транспортные расходы (табл.2.38)

Экономико-математические методы

Решение:

1. Строим опорный план методом минимального элемента (табл.2.39).

Экономико-математические методы
Экономико-математические методы

Число занятых клеток равно 5. То есть, условие опорности

Экономико-математические методы

не выполнено. Получили вырожденный план. В клетку (1;3) запишем «О’». План имеет вид:

Экономико-математические методы

Целевая функция будет равна:

Экономико-математические методы

Определяем потенциалы. Для запятых клеток записываем систему:

Экономико-математические методы

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

Определяем оценки для свободных клеток (по формуле (2.4.3)):

Экономико-математические методы
Экономико-математические методы

Получили положительную оценку Экономико-математические методы. Следовательно, полученный план не является оптимальным. Его можно улучшить, если перспективной клеткой выбрать клетку (2;3).

Строим для клетки (2;3) замкнутый контур (табл.2.39). Вершинам контура присваиваем знаки (+) и (-), начиная с перспективной клетки, обозначенной (*).

Находим минимальную поставку, которую нужно переместить по построенному контуру

Экономико-математические методы
  • Минимальную поставку перемещаем по полученному контуру. Новый опорный план приведён в таблице 2.40, имеет вид:
Экономико-математические методы

Целевая функция

Экономико-математические методы

Вычисляем потенциалы изменённых строк и столбцов:

Экономико-математические методы

Проверяем свободные клетки:

Экономико-математические методы

Полученный план не оптимальный, так как есть оценки не удовлетворяющие условию (2.3.3), то есть — большие пуля.

  • Перспективной будет клетка (1;1). Для неё строим замкнутый контур (табл.2.40). Минимальная перемещаемая поставка равна нулю. Перемещаем её по контуру, получим следующий опорный план (табл.2.41).
Экономико-математические методы
Экономико-математические методы

Новый опорный план —

Экономико-математические методы

Целевая функция не изменяется.

  • Снова определяем потециалы для полученного плана:
Экономико-математические методы

Для свободных клеток определяем оценки

Экономико-математические методы

Все оценки удовлетворяют условию (2.3.3). Следовательно, получен оптимальный план Экономико-математические методы

Экономико-математические методы

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

Пример 2.8.

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

Экономико-математические методы

Решение:

Начальный опорный план найден методом максимального элемента в задаче (табл.2.43)

Экономико-математические методы
Экономико-математические методы

Составляем систему уравнений для определения потенциалов и находим её решение

Экономико-математические методы

Вычисляем оценки незагруженных клеток

Экономико-математические методы

Все оценки удовлетворяют условию (2.3.5). Следовательно, найденный план

Экономико-математические методы

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

Одна из оценок Экономико-математические методы, значит оптимальное решение не единственное.

Распределительный метод

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

Оценки для свободных клеток определяются по формуле

Экономико-математические методы

где Экономико-математические методы — сумма тарифов в нечётных вершинах контура,

Экономико-математические методы — сумма тарифов в чётных вершинах контура.

Если для всех свободных клеток оценки Экономико-математические методы >0, то полученный план является оптимальным. Если хотя бы одна из оценок окажется отрицательной, то построенный план не будет оптимальным. Его улучшение возможно за счёт перемещения груза по замкнутому контуру любой из клеток, для которой Экономико-математические методы < 0. Величина перемещаемого по контуру груза равна наименьшей из поставок, расположенных в вершинах цикла со знаком (-).

Алгоритм распределительного метода

  1. Располагаем исходные данные в таблице матричного типа.
  2. Строим исходный опорный план по методу «северо-западного» угла, минимального элемента или Фогеля.
  3. Производим оценку свободной клетки , строя для неё цикл, и вычисляем величину. Если Экономико-математические методы < 0, то переходим к пункту 4. Если Экономико-математические методы, то оцениваем следующую свободную клетку и так далее, пока обнаружим клетку с отрицательной оценкой. Если оценки всех свободных клеток окажутся положительными, то решение заканчивается. Полученное решение будет оптимальным.
  4. По циклу, имеющему Экономико-математические методы<0, перемещаем груз, равный наименьшей из поставок, размещённых в чётных клетках цикла. То есть, в клетках, имеющих нечётные номера, груз увеличивается на минимальную поставку, а в чётных уменьшается. Клетка, по которой выбиралась минимальная перемещаемая поставка, остаётся свободной. Далее возвращаемся к пункту 3.

Замечания.

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

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

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

Пример 2.10.

Распределительным методом найти оптимальный план задачи, заданной в таблице 2.44.

Экономико-математические методы
Экономико-математические методы

Решение:

Начальный опорный план Экономико-математические методы, построенный с помощью метода минимального элемента, приведен в таблице 2.45.

Экономико-математические методы

Опорный план

Экономико-математические методы

Транспортные расходы равны

Экономико-математические методы

Число заполненных клеток

Экономико-математические методы

Следовательно, план является опорным.

Проверим этот план на оптимальность. Для этого среди свободных клеток находим клетку с минимальным тарифом — (1;1). Для неё в таблице 2 строим цикл перерасчёта, все вершины которого находятся в загруженных клетках

Экономико-математические методы

Находим оценку Экономико-математические методы. Следовательно, план не оптимальный.

Для его улучшения переместим по построенному контуру поставку Экономико-математические методы. Прибавим Экономико-математические методы к вершинам со знаком (+), и вычтем эту величину из вершин со знаком (-). Полученный сдвиг на величину Экономико-математические методы приводит к новому опорному плану (табл. 2.46).

Экономико-математические методы

Опорный план

Экономико-математические методы

Транспортные расходы:

Экономико-математические методы

Расположим свободные клетки в порядке возрастания тарифов:

Экономико-математические методы

Находим оценки:

Экономико-математические методы
Экономико-математические методы

Так как для всех свободных клеток Экономико-математические методы, то найденный в таблице 3 план — оптимален. Но так как Экономико-математические методы и Экономико-математические методы, то оптимальный план не единственный, и для этих клеток можно перерасчётом построить новые опорные планы.

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

Экономико-математические методы

где Экономико-математические методы. Задаваясь численными значениями Экономико-математические методы из интервала ГО; 11, будем получать различные оптимальные планы, для которых Экономико-математические методы.

Пример 2.11.

Распределительным методом найти решение задачи (табл. 2.47).

Экономико-математические методы

Решение:

1. Пусть план Экономико-математические методы получен методом минимального элемента (табл.2.48)

Экономико-математические методы

Экономико-математические методы

Опорный план

Экономико-математические методы

Транспортные расходы

Экономико-математические методы
  1. Выписываем свободные клетки в порядке возрастания их тарифов: (1;3), (3;1), (3;3), (2;2).
  2. Для клетки (1,3) строим замкнутый контур (табл.2.48), и проверяем его на оптимальность, то есть, Экономико-математические методы.
Экономико-математические методы

Условие оптимальности не выполняется. Улучшим его за счёт клетки (3;1) (табл. 2.49). Получим контур (1 ;3)-(3;2)-( 1 ;2)-( 1 ;3)-(2;3)-(2;1)-(3;1). Переместим поставку Экономико-математические методы.

Экономико-математические методы

Новый план Экономико-математические методы

Экономико-математические методы

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

Число загруженных клеток равно Экономико-математические методы. По загруженным клеткам нет замкнутых контуров. Проверим этот план на оптимальность. Выпишем свободные клетки в порядке возрастания тарифов: (3;1),(3;3), (2;2), (1;1).

Их оценки:

Экономико-математические методы

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

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

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

Пусть Экономико-математические методы затраты времени на перевозку продукции от Экономико-математические методы-го поставщика Экономико-математические методы-му потребителю. Имеем Экономико-математические методы поставщиков и Экономико-математические методы потребителей. Объёмы производства поставщиков — Экономико-математические методы, объёмы требований у потребителей — Экономико-математические методы.

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

Математическая модель задачи будет иметь вид:

Экономико-математические методы

при ограничениях:

Экономико-математические методы

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

Экономико-математические методы

Система ограничений (2.4.2)-(2.4.4) не отличается от соответствующей системы ограничений модели обычной транспортной задачи. Изменилась только целевая функция. Величины Экономико-математические методы определяет время, в течение которого производится план перевозок, то есть, Экономико-математические методы, так как каждому плану перевозок соответствует своё значение целевой функции.

Для решения таких задач могут применяться различные методы.

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

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

Для этого строим «разгрузочный» цикл. Он строится ходом шахматной ладьи, начиная с клетки, для которой Экономико-математические методы. Основным

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

Экономико-математические методы

Вычитаем найденное значение из объёма перевозок клеток со знаком (+), и прибавляем к грузу клеток со знаком (-). Получим новый план перевозок. При выборе Экономико-математические методы могут возникнуть ситуации:

Экономико-математические методы

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

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

Пример 2.13.

По критерию времени найти решение следующей транспортной задачи (табл. 2.50)

Экономико-математические методы

Решение:

1. Данная задача является закрытой моделью, так как выполняется условие (2.4.5).

  • Строим план методом «северо — западного» угла (табл.2.51)
Экономико-математические методы
Экономико-математические методы

определяем

Экономико-математические методы

В таблице эту клетку выделяем.

  • Среди свободных клеток вычёркиваем те, для которых Экономико-математические методы . Такими являются клетки (3;1) и (3;2).
  • Для клетки (1;1), имеющей Экономико-математические методы, строим замкнутый цикл (табл.2.51).
  • Для построенного цикла Экономико-математические методы.
  • Перемещаем Экономико-математические методы по построенному циклу, то есть в клетках со знаком (+) прибавляем эту величину, в клетках со знаком (-) вычитаем эту величину. Получаем новый опорный план (табл.2.52)
Экономико-математические методы
Экономико-математические методы

В новой таблице клетка (1;1) оказалась загруженной. Мы её вычеркиваем и в дальнейших расчётах не рассматриваем.

  1. Определяем новое значение =7.
  2. Вычёркиваем из рассмотрения свободные клетки, имеющие Экономико-математические методы. В данном случае такой является клетка (1 ;4).
  3. Для клетки (2;3), имеющей Экономико-математические методы, строим замкнутый цикл (табл.2.52).
  4. Для построенного контура Экономико-математические методы.
  5. Перемещаем 10 единиц груза по замкнутому контуру, получаем новый план (табл.2.53)
Экономико-математические методы
Экономико-математические методы
  • Определяющая по данной итерации клетка (2;3) оказалась ещё загруженной (в ней перевозка Экономико-математические методы). Поэтому для неё снова строим замкнутый цикл (табл.2.53).
  • Экономико-математические методы.
  • Перемещаем 10 единиц груза по циклу и получаем новый план перевозок (табл.2.54) или
Экономико-математические методы
Экономико-математические методы
  • Для построенного плана
Экономико-математические методы

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

Следовательно, оптимальный план перевозок осуществляется за время

Экономико-математические методы

Пример 2.14.

Найти оптимальный план перегона вагонов со станций в пункты погрузки определённого груза, при котором минимизируются затраты времени на поставку вагонов под погрузку. Значения Экономико-математические методы — затраты времени на перегон вагонов со станции в пункт погрузки груза (табл. 2.55).

Решение:

Строим начальный опорный план задачи любым методом (например, методом северо-западного угла).

Среди загруженных ячеек выбираем ячейку с наибольшим значением времени Экономико-математические методы. Это ячейка Б2, для которой Экономико-математические методы. Эта величина определяет время, в течение которого осуществляется план перевозок. Далее следует исключить из рассмотрения все свободные ячейки, для которых Экономико-математические методы. Это ячейки Б1, А4. Мы их перечеркиваем и в дальнейших расчетах не рассматриваем (табл.2.56).

Экономико-математические методы
Экономико-математические методы

Строим цикл (контур) разгрузки, основными требованиями для которого являются:

1) наличие груза в разгружаемых ячейках; 2) ячейка Б2 является разгружаемой.

Определяем величину груза, перемещаемого по циклу (минимальное значение объема перевозок среди всех разгружаемых ячеек):

Экономико-математические методы

Перемещая груз, получаем новый опорный план (табл. 2.57).

Экономико-математические методы

Ячейка Б2 оказалась разгруженной. Мы ее перечеркиваем и в дальнейших расчетах не рассматриваем.

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

Строим цикл (контур) разгрузки, определяем величину груза, перемещаемого по циклу (минимальное значение объема перевозок среди всех разгружаемых ячеек):

Экономико-математические методы

Перемещая груз, получаем новый опорный план (табл. 2.58):

Экономико-математические методы

Ячейка В2 оказалась разгруженной. Мы ее перечеркиваем и в дальнейших расчетах не рассматриваем.

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

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

Экономико-математические методы

Перемещая груз, получаем новый опорный план (табл. 2.59):

Экономико-математические методы

Ячейка В3 осталась неразгруженной, но для нее нельзя построить новый разгрузочный цикл.

Следовательно, оптимальный план перевозок осуществляется за время

Экономико-математические методы

Замечание.

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

Экономико-математические методы

Транспортные задачи в усложнённой постановке

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

  1. Отдельные поставки от определенных поставщиков некоторым потребителям должны быть исключены (из-за отсутствия необходимых условий хранения, чрезмерной перегрузки коммуникаций и т.д.). Это достигается искусственным значительным завышением затрат на перевозки Экономико-математические методы в клетках, перевозки через которые следует запретить.
  2. На предприятии необходимо определить минимальные суммарные затраты на производство и транспортировку продукции. С подобной задачей сталкиваются при решении вопросов, связанных с оптимальным размещением производственных объектов. Здесь может оказаться экономически более выгодным доставлять сырье из более отдаленных пунктов, но зато при меньшей его себестоимости. В таких задачах за критерий оптимальности принимают сумму затрат на производство и транспортировку продукции.
  3. Ряд транспортных маршрутов, по которым необходимо доставить грузы, имеют ограничения по пропускной способности. Если, например, по маршруту Экономико-математические методы можно провести не более Экономико-математические методы единиц груза, то Экономико-математические методы-й столбец матрицы разбивается на два столбца — Экономико-математические методы и Экономико-математические методы. В первом столбце спрос принимается равным Экономико-математические методы, во втором — Экономико-математические методы. Несмотря на то, что фактические затраты Экономико-математические методы в обоих столбцах одинаковы и равны исходным, в столбце Экономико-математические методы вместо истинного тарифа Экономико-математические методы ставится искусственно завышенный тариф Экономико-математические методы (клетка блокируется). Затем задача решается обычным способом.
  4. Поставки по определенным маршрутам обязательны и должны войти в оптимальный план независимо от того, выгодно это или нет. В этом случае уменьшают запас груза у поставщиков и спрос потребителей и решают задачу относительно тех поставок, которые необязательны. Полученное решение корректируют с учетом обязательных поставок.
  5. Необходимо максимизировать целевую функцию задачи транспортного типа (например, задача об оптимальном распределении оборудования).

Рассмотрим на примерах особенности решения транспортных задач в других моделях.

Пример 2.15.

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

В пунктах Экономико-математические методы производится однородная продукция в количествах 30, 190, 250 единиц. Себестоимость изготовления единицы продукции в каждом пункте производства различна и соответственно равна 2, 4, 3 ден. ед. Готовая продукция поставляется в пункты Экономико-математические методы потребности которых 70, 120, 150, 130 единиц. Стоимости перевозки единицы продукции из пункта Экономико-математические методы в пункт Экономико-математические методы заданы матрицей Экономико-математические методы

Экономико-математические методы

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

  1. Построить табличную модель транспортной задачи.
  2. Построить начальный опорный план транспортной задачи.
  3. Методом потенциалов найти план перевозок продукции, при котором минимизируются суммарные затраты по ее изготовлению и доставке потребителям.
  4. Определить максимально возможные суммарные затраты по изготовлению и доставке продукции потребителям.
  5. Определить, как изменится решение исходной транспортной задачи, если требуется учесть ряд дополнительных условий:
  • по маршруту Экономико-математические методы перевозки пе могут быть осуществлены из-за проведения дорожных ремонтных работ;
  • по маршруту Экономико-математические методы должно быть перевезено не менее 100 ед. груза;
  • по маршруту Экономико-математические методы должно быть перевезено не более 50 ед. груза.
  • Найти оптимальный план перевозок продукции, который обеспечивает минимальное время транспортировки грузов. Количество транспортных средств считать достаточным для организации перевозок. Время доставки груза из пункта отправления Экономико-математические методы в пункт назначения Экономико-математические методы принять равным Экономико-математические методы.

Решение:

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

Данную матрицу следует использовать для дальнейшего решения задачи.

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

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

  • суммарные затраты на перевозку груза должны быть минимальными
Экономико-математические методы
  • объем поставок из пункта отправления Экономико-математические методы — должен равняться запасу имеющегося груза
Экономико-математические методы
  • объем поставок в пункт назначения Экономико-математические методы должен быть равен потребности
Экономико-математические методы
  • объемы поставок должны выражаться неотрицательными числами
Экономико-математические методы

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

Экономико-математические методы

Примечание.

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

Так, если бы объемы производства продукции составляли бы 30, 190, 270 единиц при прежних объемах спроса, то математическая модель задачи приняла бы вид (добавлен фиктивный потребитель):

Экономико-математические методы
Экономико-математические методы

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

Если бы спрос на продукцию составил бы величину 70, 120, 150, 160 единиц при прежних объемах производства, то математическая модель задачи приняла бы вид (добавлен фиктивный поставщик):

Экономико-математические методы

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

  • Табличная модель исходной транспортной задачи будет иметь вид.
Экономико-математические методы
  • Для построения начального опорного плана транспортной задачи могут применяться следующие методы:
  • «северо-западного» угла (диагональный);
  • минимального элемента (минимальной стоимости) и др.

Воспользуемся методом «северо-западного» угла.

Загрузим левую верхнюю клетку (1;1) транспортной таблицы 2.61. Исходя из объемов спроса (70 ед.) и предложения (30 ед.), в данную клетку можно записать значение объемов поставок 30 ед. Для пункта потребления Экономико-математические методы остался неудовлетворенным спрос в 40 ед. продукции. Поскольку запас первого поставщика (пункта производства Экономико-математические методы) исчерпан, то мы не будем больше рассматривать оставшиеся клетки из первой строки транспортной таблицы.

Переходим к лежащей ниже клетке (2;1). Исходя из оставшихся объемов спроса (40 ед.) и предложения (190 ед.), в данную клетку можно записать значение объемов поставок 40 ед. Потребность пункта назначения Экономико-математические методы теперь удовлетворена полностью. Поэтому далее в столбце Экономико-математические методы оставшиеся клетки рассматривать не будем. В пункте отправления Экономико-математические методы остался запас в 150 ед. продукции.

Переходим к клетке справа (2;2). Исходя из имеющихся на данный момент объемов спроса (120 ед.) и предложения (150 ед.), в данную клетку можно записать значение объемов поставок 120 ед. Потребность пункта назначения Экономико-математические методы удовлетворена полностью. Поэтому также как и ранее в столбце Экономико-математические методы оставшиеся клетки рассматриваться не будут. В пункте отправления Экономико-математические методы остался запас в 30 ед. продукции.

Переходим к клетке (2;3). Исходя из текущих объемов спроса (150 ед.) и предложения (30 ед.), в данную клетку можно записать значение объемов поставок 30 ед. Запас второго поставщика (пункта производства Экономико-математические методы) исчерпан полностью. Поэтому мы не будем больше рассматривать оставшиеся клетки из второй строки транспортной таблицы. Для пункта потребления Экономико-математические методы остался неудовлетворенным спрос в 120 ед. продукции.

Переходим к клетке (3;3). Исходя из оставшихся объемов спроса (120 ед.) и предложения (250 ед.), в данную клетку можно записать значение объемов поставок 120 ед. Потребность пункта назначения Экономико-математические методы теперь удовлетворена полностью. В пункте отправления Экономико-математические методы остался запас в 130 ед. продукции.

Переходим к клетке справа (3;4). Это нижняя левая клетка транспортной таблицы. В силу сбалансированности исходной транспортной задачи оставшиеся объемы спроса и предложения для данного маршрута совпадают и равны 130 ед. продукции. Поэтому в клетку (3;4) записываем поставку в 130 ед. Условие сбалансированности транспортной задачи является обязательным условием для построения ее табличной модели.

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

Экономико-математические методы

Значение целевой функции на данном опорном плане равно

Экономико-математические методы

Воспользуемся методом минимального элемента.

Минимальная стоимость перевозок (4 ден. ед.) записана в двух клетках (1;3) и (2;3). Исходя из объемов спроса и предложения, в клетку (1;3) можно записать значение объемов поставок 30 ед. (запас — 30 ед., спрос — 150 ед.), а в клетку (2;3) — 150 ед. (запас — 190 ед., спрос — 150 ед.). Поэтому загрузке подлежит клетка (2;3), как имеющая больший возможный объем поставок. Потребность пункта назначения Экономико-математические методы удовлетворена полностью. Поэтому далее в столбце Экономико-математические методы, оставшиеся клетки рассматриваться не будут. В пункте отправления Экономико-математические методы остался запас в 40 ед.

Среди оставшихся незаполненных клеток минимальная стоимость перевозок (5 ден. ед.) также записана в двух клетках (2;2) и (1;4). Исходя из текущих объемов спроса и предложения, в клетку (2;2) можно записать значение объемов поставок 40 ед. (запас — 40 ед., спрос — 120 ед.), а в клетку (1;4) — 30 ед. (запас — 30 ед., спрос -130 ед.). Поэтому загрузке подлежит клетка (2;2), как имеющая больший возможный объем поставок. Запасы пункта отправления Экономико-математические методы исчерпаны. Поэтому далее в строке Экономико-математические методы оставшиеся клетки рассматриваться не будут. В пункте назначения Экономико-математические методы остался неудовлетворенным спрос в 80 ед. продукции.

Поскольку загрузка клетки (2;2) не повлияла на текущее состояние спроса и предложения в первой строке и четвертном столбце транспортной таблицы, то далее загрузке подлежит клетка (1;4), куда следует записать значение объемов поставок 30 ед. Запасы пункта отправления Экономико-математические методы исчерпаны. Поэтому далее в строке Экономико-математические методы оставшиеся клетки рассматриваться также не будут. В пункте назначения Экономико-математические методы остался неудовлетворенным спрос в 100 ед. продукции.

Для рассмотрения осталась только одна третья строка транспортной таблицы. Заполним оставшиеся клетки, исходя из объемов неудовлетворенного спроса: в клетке (3;1) — 70 ед. груза, в (3;2) — 80 ед. груза, в (3;4) — 100 ед. груза.

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

Экономико-математические методы

Значение целевой функции на данном опорном плане равно

Экономико-математические методы

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

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

Количество загруженных клеток равно 6, что равно числу

Экономико-математические методы

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

Экономико-математические методы

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

Экономико-математические методы
Экономико-математические методы

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

Экономико-математические методы
Экономико-математические методы

Среди разгружаемых ячеек находим минимальную величину поставок:

Экономико-математические методы

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

Экономико-математические методы

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

Вычислим потенциалы по загруженным клеткам транспортной таблицы.

Экономико-математические методы

Проверим опорный план на оптимальность.

Экономико-математические методы
Экономико-математические методы

Опорный план является оптимальным, поскольку среди незагруженных клеток для всех выполнено условие (2.3.3), то есть — Экономико-математические методы.

Определим величину минимальных затрат при оптимальном плане перевозок:

Экономико-математические методы

Заметим, что данный оптимальный план не является единственным, поскольку существуют незагруженная клетка (2;4), для которой Экономико-математические методы.

Рассмотрим опорный план следующего вида (может быть получен путем перераспределения поставок по контуру с вершиной максимальной неоптимальности в клетке (2;4)) таблица 2.65

Экономико-математические методы

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

Экономико-математические методы

Проверим опорный план на оптимальность.

Экономико-математические методы

Опорный план является оптимальным, поскольку среди незагруженных клеток для всех выполнено условие (2.3.3) — Экономико-математические методы.

Определим величину минимальных затрат при данном оптимальном плане перевозок:

Экономико-математические методы

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

  • При определении максимально возможных суммарных затрат по изготовлению и доставке продукции потребителям можно поступить одним из двух способов:

1) Изменить знак в матрице затрат Экономико-математические методы на противоположный и решать задачу аналогично описанному выше. Отрицательное итоговое значение затрат (максимальные затраты) считать положительным.

2) Выбирать в качестве вершины максимальной неоптимальности вершину, для которой Экономико-математические методы принимает наименьшее отрицательное значение. План будет оптимальным, если все Экономико-математические методы.

Рассмотрим подробнее второй способ решения.

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

Опорный план нашей транспортной задачи будет иметь вид (табл. 2.66)

Экономико-математические методы
Экономико-математические методы

Данный опорный план является вырожденным, поскольку содержит 5 загруженных клеток вместо необходимых 6. Поэтому в произвольную незагруженную клетку (например,(1;2)) запишем пулевую поставку(табл. 2.67)

Экономико-математические методы

Вычислим потенциалы по загруженным клеткам транспортной таблицы.

Экономико-математические методы

Проверим опорный план на оптимальность.

Экономико-математические методы
Экономико-математические методы

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

Среди разгружаемых клеток находим минимальную величину поставок:

Экономико-математические методы

Для всех разгружаемых клеток (-) уменьшаем объем перевозок па эту величину, а для загружаемых (+) — увеличиваем.

Получаем транспортную таблицу 2.68 вида

Экономико-математические методы

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

Вычислим потенциалы по загруженным клеткам транспортной таблицы.

Экономико-математические методы

Проверим опорный план на оптимальность.

Экономико-математические методы
Экономико-математические методы

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

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

Экономико-математические методы
  • Найти решение исходной транспортной задачи с учетом дополнительных условий.

Запрет перевозок по маршруту Экономико-математические методы достигается путем искусственного завышения стоимости перевозок в указанной ячейке (например, заданием величины 50 ден. ед.).

Для выполнения условий типа «не менее» (т.е. учета обязательных поставок по заданным маршрутам) следует уменьшить объемы спроса и предложения в заданных пунктах отправления и назначения на указанную величину (т.е. избавиться от обязательных поставок). После нахождения оптимального решения ответ корректируется с учетом обязательных поставок.

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

С учетом дополнительных условий табличная модель нашей транспортной задачи примет вид (табл. 2.69)

Экономико-математические методы
Экономико-математические методы

Построим начальный опорный план методом минимального элемента (табл. 2.70)

Экономико-математические методы

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

Вычислим потенциалы по загруженным клеткам транспортной таблицы.

Экономико-математические методы

Проверим опорный план на оптимальность.

Экономико-математические методы

Опорный план не является оптимальным, поскольку среди незагруженных клеток имеется Экономико-математические методы Клетка (2:4) будет вершиной максимальной неоптимальности (в качестве вершины максимальной неоптимальности выбирают клетку с набольшим положительным значением Экономико-математические методы).

Строим контур перераспределения поставок.

Среди разгружаемых клеток находим минимальную величину поставок:

Экономико-математические методы

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

Получаем транспортную таблицу 2.71 вида

Экономико-математические методы

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

Вычислим потенциалы по загруженным клеткам транспортной таблицы.

Экономико-математические методы

Проверим опорный план на оптимальность.

Экономико-математические методы

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

В результате получим таблицу 2.72 следующего вида

Экономико-математические методы

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

Экономико-математические методы

Таким образом, в силу учета дополнительных условий суммарные затраты по изготовлению и доставке продукции потребителям увеличились на 3360 — 3070 = 290 ден. ед.

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

Построим начальный опорный план транспортной задачи методом «северо-западного» угла (табл. 2.73)

Экономико-математические методы

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

Строим цикл (контур) разгрузки, основными требованиями для которого являются: 1) наличие груза в разгружаемых клетках; 2) клетка (3;4) является разгружаемой (табл. 2.74)

Экономико-математические методы
Экономико-математические методы

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

Экономико-математические методы

Перемещая груз, получаем новый опорный план (табл. 2.75)

Экономико-математические методы

Клетка (3;4) осталась еще загруженной. Поэтому для нее строим еще контур.

Определяем величину груза, перемещаемого по циклу:

Экономико-математические методы

Перемещая груз, получаем новый опорный план (табл. 2.76):

Экономико-математические методы
Экономико-математические методы

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

Среди загруженных клеток выбираем клетку с наибольшим значением времени Экономико-математические методы. Это клетка (3;2), для которой Экономико-математические методы. Исключаем из рассмотрения все свободные клетки, для которых Экономико-математические методы. Такая клетка одна -(1 ;2).

Для клетки (3;2) строим контур. Определяем величину груза, перемещаемого по циклу:

Экономико-математические методы

Перемещая груз, получаем новый опорный план (табл. 2.77)

Экономико-математические методы

Клетка (3;2) осталась еще загруженной. Поэтому для нее строим еще контур.

Определяем величину груза, перемещаемого по циклу:

Экономико-математические методы

Перемещая груз, получаем новый опорный план (табл. 2.78)

Экономико-математические методы
Экономико-математические методы

Данное решение является оптимальным, так как нельзя построить разгрузочный цикл для клетки (3;2). Следовательно, оптимальный план перевозок осуществляется за время

Экономико-математические методы

Транспортная задача в сетевой форме

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

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

Основные понятия теории графов

Графом называется множество точек, соединённых линиями.

Обозначается граф Экономико-математические методы, где Экономико-математические методы -множество точек. Точки, входящие в множество Экономико-математические методы, называются вершинами графа.

Экономико-математические методы — множество отрезков, соединяющих вершины графа. Эти отрезки называются рёбрами графа. Пример графа показан на рисунке 2.6.1.

Экономико-математические методы

Точки 1, 2, 3, 4, 5 являются вершинами графа. Рёбрами являются отрезки (1-2), (1-3), (1-4), (1-5), (2-3), (3-4), (2-5), (3-5), (4-5). Если рёбра графа ориентированы, то есть, указано направление движения, то граф называется ориентированным (рис.2.6.2). Если рёбра графа не ориентированы, то граф называется неориентированным (рис.2.6.3). Граф, в котором есть и ориентированные ребра, и неориентированные называется смешанным (рис. 2.6.4).

Экономико-математические методы

Любые две вершины графа называются смежными, если они соединены ребром. Для графа, показанного на рис. 2.6.3, смежными являются пары вершин: (1-2), (1-3), (1-5), (2-4), (3-4), (4-5). Два графа называются изоморфными, если между их вершинами существует соответствие, сохраняющее смежность (рис.2.7.5).

Экономико-математические методы

Изоморфизм графов обозначают Экономико-математические методы. Подграфом графа Экономико-математические методы называется граф, у которого все вершины и рёбра принадлежат графу Экономико-математические методы. Для графа, приведённого на рис.2.6.6, подграф показан на рис. 2.6.7.

Экономико-математические методы

Граф, у которого все вершины соединены между собой, называется полным (рис.2.6.8).

Экономико-математические методы

Степенью вершины называется число рёбер графа, которым принадлежит эта вершина. Для графа, показанного на рис. 2.6.9, степень первой вершины равна 1, степень второй вершины равна 2. Степень вершины может быть чётной или нечётной. Число вершин нечётной степени — четно. Это утверждение справедливо для любого графа. Дугой на графе называется ориентированная пара

Экономико-математические методы

Экономико-математические методы вершин Экономико-математические методы. Например, для графа, показанного на рис. 2.6.10, дугами являются: (1-2), (2-1), (3-4) и (4-3).

Путём (маршрутом) на графе называется последовательность сцепленных дуг, позволяющих пройти из одной вершины в другую. Для графа, показанного на рис. 2.6.11, примерами пути являются: (1 -2-5-6), (1 -2-5-4), (1 -4-6), (1 -4-6-5)Б (1 -4-5-2).

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

Экономико-математические методы

Замкнутая простая цепь называется циклом. Пример цикла показан на рис. 2.6.13. Цикл, содержащий отличные друг от друга рёбра , называется простым, в противном случае — сложным. Контур, образованный одной дугой, называется петлёй. На рис. 2.7.13. показана петля на вершине 6.

Экономико-математические методы

Гамильтоповым циклом (путём) на графе называется цикл, проходящий через каждую вершину графа только один раз.

Гамильтопов цикл (путь) всегда является простым. Он может не содержать все рёбра графа.

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

Экономико-математические методы

Если в графе существует маршрут, соединяющий две любые вершины, то граф называется связным, (рис. 2.6.15).

Связный граф, не содержащий циклов, называется деревом. Для графа, показанного на рис. 2.6.16, деревом является граф, приведённый на рис.2.6.17.

Экономико-математические методы

Дерево не имеет петель и кратных рёбер, и любые две вершины связаны единственной цепыо. Вершины дерева, степень которого равна единице, называется висячей. Например, для дерева, приведённого на рис. 2.6.17, висячими будут вершины 1, 2, 5 и 6.

Ветвями дерева являются рёбра графа, входящие в дерево. Для рассматриваемого примера (рис.2.6.17) ветвями являются рёбра (1-4), (4-6), (3-4). (2-3) и (3-5). Граф без циклов, состоящий из нескольких деревьев, называется лесом. То есть, лес представляет собой объединение деревьев (рис. 2.6.18).

Ориентированный граф, элементам которого поставлены в соответствие некоторые параметры, называется сетью. Параметры задаются для вершин и для дуг графа. Параметром вершины Экономико-математические методы является некоторое число Экономико-математические методы, называемое интенсивностью или дивергенцией Экономико-математические методы. Вершины, для которых Экономико-математические методы, называются источниками, вершины, для которых — Экономико-математические методы называются стоками. Если Экономико-математические методы, то — нейтральными.

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

Потоком на сети называется функция, сопоставляющая каждой дуге Экономико-математические методы целое число Экономико-математические методы и обладающая следующими свойствами:

Экономико-математические методы

для вершин Экономико-математические методы, не являющихся ни источником, ни стоком,

Экономико-математические методы

где Экономико-математические методы — источник, Экономико-математические методы — сток. Условия означают:

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

Разрезом в сети, отделяющим источник Экономико-математические методы и сток Экономико-математические методы, называется множество дуг вида Экономико-математические методы,

где Экономико-математические методы, а Экономико-математические методы, Экономико-математические методы — множество вершин графа. Подмножества Экономико-математические методы и Экономико-математические методы — не пересекаются. Множество Экономико-математические методы (рис.2.6.19) составляют вершины 3, 4 и 6, а множество Экономико-математические методы — вершины 1, 2 и 5.

Экономико-математические методы

Разрез составляют дуги (1-3), (2-3),(2-4), (2-6), (5-6). То есть, в разрез входят только те дуги, которые начинаются во множестве Экономико-математические методы и заканчиваются во множестве Экономико-математические методы.

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

Экономико-математические методы

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

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

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

Экономико-математические методы

ограничения

Экономико-математические методы

где Экономико-математические методы — множество поставщиков.

Экономико-математические методы

где Экономико-математические методы — множество потребителей,

Экономико-математические методы

где Экономико-математические методы — множество промежуточных пунктов,

Экономико-математические методы

Ограничения означают:

  • (2.6.6) количество груза, вывозимого от поставщика, должно быть равно его мощности,
  • (2.6.7) количество груза, ввозимого к потребителю, не должно превышать его потребности,
  • (2.6.8) для любой вершины, не являющейся ни поставщиком, ни потребителем, количество ввозимого груза должно быть равно количеству вывозимого из него груза,
  • (2.6.9) количество груза, перевозимого по каждой дуге Экономико-математические методы, не должно превышать её пропускной способности,
  • (2.6.10) количество перевозимого груза является величиной неотрицательной,
  • (2.6.11) количество груза, вывозимого от всех поставщиков, должно быть равно потребностям всех потребителей (задача будет закрытой).

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

Метод потенциалов для решения транспортной задачи на сети

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

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

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

а) все запасы грузов должны быть вывезены от поставщиков;

б) потребности потребителей должны быть полностью удовлетворены:

в)общее количество направленных дуг Экономико-математические методы должно быть на единицу меньше числа вершин, то есть, Экономико-математические методы. Иначе, если Экономико-математические методы, то вводятся дуги с нулевыми поставками;

г) дуги ие должны образовывать замкнутых контуров.

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

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

Экономико-математические методы

б) если стрелка (дуга) направлена к вершине (рис. 2.6.20 б)), то величину Экономико-математические методы вычитаем из потенциала вершины Экономико-математические методы.

Экономико-математические методы
Экономико-математические методы

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

Экономико-математические методы

где Экономико-математические методы и Экономико-математические методы — потенциалы вершин соответственно Экономико-математические методы и Экономико-математические методы ребра Экономико-математические методы.

Если для всех рёбер, не имеющих направленных дуг (не загруженных) выполняется условие

Экономико-математические методы

то построенный план является оптимальным.

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

  • Улучшение опорного плана. Для улучшения опорного плана необходимо:

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