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

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

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

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

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

Математические методы в экономике — научное направление в экономике, посвящённое исследованию экономических систем и процессов с помощью математических моделей. 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). Области решений будет принадлежать полуплоскость с той стороны от прямой, где находится начало координат, так как при подстановке точки получим верное неравенство 030. Преобразуем третье неравенство:

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

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

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

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

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

уровня передвигаем в направлении антиградиента , до конечной точки (рис. 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), то есть, , то построенный план не является оптимальным и требует улучшения.

• Улучшение опорного плана. Для улучшения опорного плана необходимо:

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

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

Перемещение груза ведётся по правилу:

• на дугах, имеющих то же направление, что и новая, объём перевозок увеличивается на выбранную поставку;
• на дугах, имеющих противоположное направление — вычитается. Дуга, соответствующая минимальной поставке, аннулируется. Общее число дуг остаётся прежним.

Новый опорный план проверяется на оптимальность, то есть, возвращаемся к пункту 2.

Замечания.

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

Вырождение плана

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

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

Пример 2.16.

Построить начальный опорный план для транспортной задачи , приведённой на рис 2.6.21 а).

Решение:

Поставщиками являются пункты 1 и 2. Потребителями — пункты 3, 4 и 6.

Распределение грузов по поставщикам приведено на рис 2.6.21 б).

Распределение грузов дало два дерева, которые не связаны между собой. Общее количество дуг равно . Это случай вырождения. Устраняем вырождение введением одной дуги (5 — 4 — 1) с нулевой поставкой, учитывая, что вводимая дуга с загруженными дугами не должна образовывать замкнутый контур на сети. Тогда, дугу можно ввести либо по ребру (2-3), либо по ребру (3-5), либо по ребру (3-6), либо по ребру (4-6). Ни в одном из указанных случаев мы не получим замкнутый контур. Заменим ребро (3-6) дугой (рис.2.6.21). Теперь общее число дуг равно =5. Следовательно, построенный план является опорным.

Пример 2.17.

Найти оптимальный опорный план перевозок транспортной задачи рис. 2.6.22.

Решение:

Поставщиками являются пункты 1 и 4. Потребителями — пункты 2, 3, 5 и 7. Объём поставок равен 90 единицам. Объёмы потребления поставлены в вершинах со знаком минус. Объём потребления — (30+20+10+30)=90. То есть, модель транспортной задачи является закрытой.

• Строим опорный план (рис 2.6.23). Для построенного начального плана дуги не образуют замкнутый контур. Их количество равно 5<=7-1=6. Следовательно, план ещё не является опорным. Нужно ввести одну дугу с нулевой поставкой. Такие дуги обозначены па рисунках штрих — пунктирными линиями. Возьмём, например, дугу (2-7). Теперь число дуг равно =6.
• Вычисляем потенциалы вершин графа. Для этого присвоим вершине 1 потенциал . Остальные вершины будут иметь потенциалы:

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

• Не все оценки удовлетворяют условию (2.6.15) . Следовательно, план не оптимальный. Улучшение плана перевозок произведём по ребру (5-7), имеющему наибольшую по абсолютной величине отрицательную оценку . Дугу (5-7) направим от вершины 5 к вершине 7, то есть от меньшего потенциала к большему. На рис. 2.7.23 дуга нарисована пунктиром.
• В полученном цикле две дуги имеют направление, противоположное построенной дуге (5-7). Это дуги (4-6) и (6-7).

Следовательно величина перемещаемого груза равна

• Увеличим объём поставок на дугах (4-5) и (5-7) на 10 единиц. На дугах (4-6) и (6-7) уменьшим на 10 единиц, и аннулируем дугу (4-6) как дугу, содержащую минимальную величину перемещаемой поставки груза.

Улучшенный план перевозок показан на рис. 2.6.24.

• Снова вычисляем потенциалы вершин графа (рис. 2.6.24).

• Оценки для рёбер графа, не имеющих дуг:

Так как есть оценки , то план не является оптимальным.

• Улучшаем план перевозок за счёт дуги (3-7) (рис. 2.6.24). Минимальная поставка из встречных дуг дуге (3-7) равна «О». Переместим её по контуру. Улучшенный план перевозок показан на рис. 2.6.25.
• Вычисляем потенциалы вершин графа (рис. 2.6.25):

Находим оценки для свободных рёбер графа:

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

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

Решений бесконечное множество (рис.2.6.26).

Определение кратчайшего пути на транспортной сети

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

Рассмотрим наиболее широко распространённый алгоритм Минта для задачи о кратчайшем расстоянии.

Алгоритм метода

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

Если , где — расстояние между рассматриваемыми смежными вершинами и , то вершине присваивается потенциал, равный П^ = П1 + е…

Если , то за вершиной сохраняется прежнее значение потенциала .

1. Выбираем любую вершину из рассмотренных. Для неё рассматриваем все смежные, являющиеся конечными по отношению к фиксированной вершине. Вычисление потенциалов производится по правилу, приведённому в пункте 2, и так далее. Шаг 3 повторяется до тех пор, пока не будут присвоены наименьшие потенциалы всем вершинам транспортной сети.
2. Строим сам кратчайший путь. Для этого рассматриваем транспортную сеть от конца к началу. Для каждого ребра определяем разность между потенциалами его вершин. Рёбра, для которых эта разность равна расстоянию между их вершинами, включаются в кратчайший путь. Таким образом, определяется кратчайший путь на транспортной сети.

Пример 2.18.

Определить кратчайший путь от точки до точки транспортной сети, приведённой на рис. 2.6.27.

Решение:

1. Присваиваем вершине потенциал , а всем остальным вершинам — потенциал , где — некоторое большое число.

• Рассмотрим вершины, смежные с вершиной , и вычислим их потенциалы.

Вершина 2.

Так как вычисленное значение потенциала меньше ранее присвоенного вершине 2 потенциала , то за вершиной 2 закрепляется наименьшее значение потенциала =2.

Вершина 3.

Следовательно, за вершиной 3 закрепляем потенциал .

Вершина 4.

Следовательно, за потенциал вершины 4 принимаем .

Таким образом, рассмотрены все вершины, связанные с начальной вершиной .

Теперь рассматриваем последовательно вершины: 2, 3 и 4.

Возьмём вершину 2. Связанными с ней являются вершины 3 и 5. Вычисляем их потенциалы:

Вершина 3.

Так как вычисленное значение больше ранее присвоенного вершине 3 потенциала =3, то за вершиной 3 сохраняем прежнее значение потенциала =3.

Для вершины 5.

Следовательно, принимаем .

Рассмотрим вершину 3. Связанными с ней являются вершины 6 и 4. Для них имеем:

Принимаем

Следовательно, за вершиной 4 сохраняем прежнее значение потенциала .

Теперь имеем конечными рассмотренными вершинами вершины 5, 6 и 4. Рассмотрим связанные с ними вершины. Для вершины 5 -будут вершины 8 и 6, для вершины 6 — будут 8, 10 и 7, Для вершины 4 — будет 7.

Следовательно, за вершиной 6 сохраняем ранее вычисленное значение потенциала

Следовательно, за вершиной 10 сохраняем ранее вычисленное значение потенциала .

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

Таким образом, мы определили кратчайший путь от точки до точки На рис. 2.6.27 он показан жирной линией.

Применение MS Excel

Практическая часть:

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

Пример 2.21.

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

Решение:

В соответствии с общепринятыми обозначениями запишем исходные данные задачи в виде таблицы 2.80

Представленная задача транспортного типа является закрытой, поскольку спрос 40 + 60 + 80 + 60 — 240 равен предложению 60 + 80+ 100 = 240.

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

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

В ячейки (клетках) В4:Е6 введены стоимости перевозок.

Ячейки В12:Е 14 отведены под значения неизвестных (объемы перевозок).

Ячейки F4:F6 содержат запасы груза у поставщиков, а ячейки В7:Е7 — потребность в грузах на соответствующих пунктах назначения.

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

В ячейки F12:F14 введены формулы для вычисления объемов груза, вывозимого из каждого пункта отправления.

Ячейки В15:Е 15 содержат формулы для определения объемов груза, поставляемого в соответствующие пункты назначения.

Выделим ячейку, содержащую целевую функцию (С 17), в меню «Сервис» выберем команду «Поиск решения…» и заполним диалоговое окно надстройки «Поиск решения» как показано на рис. 2.8.2.

Поле «Изменяя ячейки» содержит адреса искомых переменных (В 12:Е 14).

Кнопка «Добавить» позволяет ввести систему ограничений транспортной задачи. Если при вводе задачи возникнет необходимость в изменении или удалении внесенных ограничений, это можно сделать при помощи кнопок «Изменить», «Удалить».

Установите флажок параметра «Линейная модель». После нажатия кнопки «Выполнить» надстройка «Поиск решения» находит оптимальный план перевозок и соответствующие ему минимальные транспортные расходы (рис. 2.8.3).

Транспортные издержки по оптимальному плану составляют 280 ден. ед.

Элементы теории игр и принятия решений

Основные определения

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

Примерами конфликтных ситуаций могут быть:

1. Военные учения, когда каждая из сторон желает выиграть.
2. Арбитражные споры.
3. Спортивные игры.
4. Требования к скорости движения автомобилей со стороны водителя и работника ГАИ.

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

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

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

Цель теории игр — выработка рекомендаций по разумному поведению участников конфликта в предположении о полной разумности участников конфликта.

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

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

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

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

Классифицируются игры по разным признакам.

1. По количеству участников: а) двух «лиц» (парная игра), б) нескольких «лиц» (множественная игра).
2. По отношению участников друг к другу: а) коалиционные (кооперативные), б) бескоалиционные.
3. По характеру выигрышей: а) с пулевой суммой (когда выигрыш одного равен проигрышу другого), б) ненулевой суммой.

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

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

Парные матричные игры

Рассмотрим игру двух игроков ( и ) с нулевой суммой. Интересы игроков прямо противоположны: выигрыш игрока равен проигрышу игрока и наоборот. Число стратегий у игроков является конечным. Предполагается, что для каждого игрока существует некоторая единственная стратегия, называемая чистой, следуя однозначно которой игрок стремится максимизировать свой выигрыш (игрок — минимизировать проигрыш). Пусть у игрока имеется возможных конечных действий — чистых стратегий’.. У игрока чистых стратегий: . Величина — выигрыш игрока при применении им стратегии , а игроком — стратегии . Если выигрыш аи известен для всех возможных пар стратегий то игру можно свести к матричной игре (выигрышей для игрока и проигрышей для игрока ) с нулевой суммой.

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

Для большей наглядности игру представляют в виде таблицы 3.1.

Игра сводится к одпоходовой: от каждого игрока требуется сделать только один ход — выбрать стратегию. Основная теорема теории игр.

Теорема. Любая конечная игра двух лиц с нулевой суммой имеет хотя бы одно решение.

Решение матричных игр, как правило, начинается с упрощения платёжной матрицы.

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

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

Стратегия игрока называется доминирующей над стратегией , если выигрыши столбца меньше, либо равны соответствующим выигрышам столбца , то есть

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

Пример 3.1.

Дана парная игра с платёжной матрицей таблица 32. Необходимо упростить матрицу.

Решение:

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

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

Решение игры в чистых стратегиях

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

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

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

Затем находится верхняя чистая цена игры

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

Следует отметить, что для любой платежной матрицы .

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

Пример З.2.

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

Решение:

Дополним таблицу 3.6 ещё одним столбцом и одной строкой.

В них разместим решение и .

Для дизайнера

Для технолога

Цена игры .

Таким образом, решением игры являются два варианта и .

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

Примечание.

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

Так, например, платежную матрицу вида

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

После нахождения оптимального решения вычисленную цену игры следует уменьшить па величину =25.

Решение в смешанных стратегиях

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

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

Игроку желательно свой выигрыш сделать как можно большим:

где — нижняя цена игры.

Игроку желательно свой проигрыш сделать как можно меньшим:

где — верхняя цепа игры.

Справедливы следующие теоремы.

Теорема 1. Для всякой матричной игры с нулевой суммой существует решение в смешанных стратегиях.

Следовательно, для смешанных стратегий существует единственное оптимальное решение с ценой игры . Пусть — цена игры

Теорема 2. Для того чтобы число было ценой игры, а

оптимальными стратегиями, необходимо и достаточно выполнение неравенств

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

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

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

то для всех её элементов будет справедливо

в том числе и для цены игры

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

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

Полагая, что

введём обозначения

и, выполняя деление левой и правой частей неравенства (3.4.1) на , получим

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

Поскольку справедливо выражение (11) функция равна

Справедливо соотношение

1) Для игрока имеем следующую ЗЛП:

Если оптимальное решение , то выполняется

Введём обозначения

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

2) Для игрока имеем следующую ЗЛП.

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

Задачи (3.3.2), (3.3.3) и (3.3.4), (3.3.5) — взаимодвойственные. Решая одну из них, можно найти решение другой.

Пример 3.4.

Для данной платёжной матрицы найти решение игры

Решение:

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

Следовательно, нижняя цена игры

верхняя цена игры

Так как , то нет решения игры в чистых стратегиях. Следует искать решение в смешанных стратегиях.

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

Её нижняя цена игры будет

а верхняя цена игры

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

Составим ЗЛП для игры с платёжной матрицей .

Можно решать любую из этих задач. Остановимся па решении исходной задачи на максимум. Введём балансовые переменные и заполним таблицу 3.9. Чтобы избежать зацикливания, вычислим все симплексные столбцы и выберем из них самый маленький элемент [1/9]. Он определит разрешающую строку и разрешающий столбец.

С этим элементом делаем первый шаг симплексных преобразований. Получим таблицу 3.10.

По симплексному столбцу определяем разрешающий элемент [8]. Делаем следующий шаг симплексных преобразований.

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

Цена игры

то есть условие

выполняется. Оптимальные решения:

Находим вероятности

и вектор

вероятности

и вектор

Условия

выполняются. Решением задачи является рекомендация. Для игрока : использовать стратегию на 100/3 %, стратегию — на 200/3 %. Для игрока : использовать стратегию на 25 %, стратегию — на 75 %.

Решение матричной игры графическим методом

Решение матричных игр можно получить графическим методом, если размерности платёжных матриц

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

Рассмотрим на примерах особенности решения таких задач.

Пример 3.6.

Решить игру с платёжной матрицей

Решение:

Проверим, есть ли решение игры в чистых стратегиях.

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

Найдём графическое решение двойственной задачи.

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

Получаем значения

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

Из этой системы равенств следует, что

цена игры Таким образом, решение игры:

Пример 3.7.

Найти решение игры с платёжной матрицей

Решение:

Проверим, существует ли решение в чистых стратегиях. В данном случае

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

Вначале удобнее найти решение задачи на минимум.

Точка является точкой пересечения двух прямых (1) и (2). Координаты этой точки определяются из решения системы уравнений

и будут равны

тогда

Неравенство (3), при 8 8 подстановке значений и , является строгим, следовательно, в двойственной задаче неизвестная . Поэтому ограничения двойственной задачи превращаются в равенства, решая которые получим значения и

Вероятности будут равны

Решение задач теории игр в условиях частичной и полной неопределённости. Игры с «природой»

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

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

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

Рассмотрим решение таких задач па примере.

Пример 3.9.

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

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

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

1) Составить платежную матрицу

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

в год составляют

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

3) Дать обоснованные рекомендации по определению объемов выпуска повой продукции при условиях полной неопределённости на основе критериев, Вальда, Сэвиджа, Гурвица (у = 0,7).

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

Решение:

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

Стратегиями первого игрока будут его решения об организации производства продукции в объемах тыс. шт. в год соответственно. Значения объемов спроса па продукцию предприятия также определяются тремя состояниями природы соответствующими уровню спроса в 12, 14, 16 тыс. шт. в год.

Представим все данные в виде таблицы.

Выигрышами

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

Аналогичным образом определяются элементы и :

Если произведено продукции больше, чем можно ее реализовать. Элемент — прибыль при объеме производства 14 тыс. шт. в год в условиях спроса 12 тыс. шт. в год. Элемент — прибыль при объеме производства 16 тыс. шт. в год в условиях спроса 12 тыс. шт. в год. Элемент — прибыль при объеме производства 16 тыс. шт. в год в условиях спроса 14 тыс. шт. в год. Доход предприятия формируется исключительно по факту реализации продукции, а расходы равны затратам на общий объем производства:

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

Найдем верхнюю и нижнюю цену игры по формулам:

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

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

где

— заданные вероятности спроса на новую продукцию в объемах 12, 14, 16 тыс. шт. в год соответственно.

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

Соответственно при производстве 14 и 16 тыс. ед. продукции в год (стратегии ) ожидаемое значение прибыли предприятия будет равно

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

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

Ожидаемый платеж (прибыль предприятия) для стратегии вычисляется по формуле

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

Соответственно при производстве 14 и 16 тыс. ед. продукции в год (стратегии ) ожидаемое значение прибыли предприятия будет равно

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

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

3) Критерии Вальда, Сэвиджа, Гурвица предназначены для анализа ситуации, связанной с принятием решения в условиях подпой неопределенности (о вероятностном распределении, соответствующем возможным состояниям природы Sj ничего неизвестно).

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

вычисляется по формуле

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

Соответственно при производстве 14 и 16 тыс. ед. продукции в год (стратегии ) ожидаемое значение прибыли предприятия будет равно

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

Критерий Вальда называется критерием пессимизма.

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

Ожидаемый риск для стратегии вычисляется по формуле

Таким образом, при производстве 12 тыс. ед. продукции в год (стратегия ) ожидаемый риск предприятия составит

Соответственно при производстве 14 и 16 тыс. ед. продукции в год (стратегии ) ожидаемое значение риска предприятия будет равно

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

Критерий минимального риска.

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

где — показатель оптимизма .

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

Соответственно при производстве 14 и 16 тыс. ед. продукции в год (стратегии ) ожидаемое значение прибыли предприятия будет равно

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

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

Рассмотренные критерии дают разные ответы, не позволяющие сделать определённый вывод. В этом случае можно привлечь, например, вывод, полученный для критерия Лапласа, так как он рассматривает равновероятные исходы. Критерий Лапласа рекомендует стратегию и критерий Сэвиджа рекомендует эту стратегию. Следовательно, можно сделать вывод, что наилучшей стратегией для данного предприятия будет стратегия — производство 14 тыс. ед.продукции в год.

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

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

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

Решая задачу симплекс-методом, получим

Откуда

где — цена игры (среднее значение прибыли предприятия); — вероятности выбора руководством предприятия стратегий , соответственно. То есть, стратегию использовать па 85%, стратегию — па 15%.

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

продукции в год.

При этом значение прибыли составит 76,9 тыс. ден. ед.

Применение Microsoft Excel

Пример 3.16.

На технологическую линию поступает сырье с малым и большим количеством примесей. Линий может работать в трех режимах. Доход от реализации единицы продукции, изготовленной из сырья первого вида при различных режимах работы технологической линии, составляет соответственно 2, 5, 6 ден. ед., а из сырья второго вида — 5, 3, 1 ден. ед. В каких режимах и сколько времени должна работать технологическая линия, чтобы доход от выпущенной продукции был как можно большим?

Решение:

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

Построим платежную матрицу игры, как показано па рисунке 3.3, и определим нижнюю и верхнюю цену игры.

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

Рассмотрим два варианта реализации решения на компьютере. Вариаит 1. Запишем соответствующую ЗЛП:

Реализация расчетных формул для решения поставленной задачи для игрока А и пример заполнения диалогового окна «Поиск решения» представлены на рисунках 3.3 и 3.4 соответственно. В ячейках В13:В 16 находятся формулы для обратного преобразования реше-

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

Таким образом, чтобы добиться наибольшего среднего дохода в 3,8 деп. ед., 40% рабочего времени технологическая линия должна работать в первом режиме и 60% — во втором. Третий технологический режим использовать не рекомендуется.

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

Полученные рекомендации для игрока В им не будут использованы, так как игроком является «природа». Однако, реализация расчетных формул, пример заполнения диалогового окна «Поиск решения» и полученные результаты для игрока В представлены па рисунках 23, 24 и 25 соответственно.

Оптимальные значения вероятностей для игрока (природы) говорят о том, что для получения наименьшего среднего проигрыша в 3,8 ден. ед. 40% поступающего сырья должно содержать малое количество примесей и 60% — большое.

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

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

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

Реализация расчетных формул для решения поставленной задачи и пример заполнения диалогового окна «Поиск решения» представлены на рисунках 3.10 и 3.1 1 соответственно.

В результате решения задачи средствами MS Excel получены следующие значения искомых переменных:

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

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

Сетевое планирование и управление

Основные понятия и определения

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

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

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

Основано сетевое планирование па использовании сетевых моделей. {добавить о других экономических задачах)

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

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

На графике работы изображаются дугами {рёбрами), события являются вершинами графа (узлами). Они представляют собой начало или окончание, какого — либо действия (операции).

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

Начальным событием на рис. 4.1 является событие 1, конечным -событие 7. Весь комплекс включает выполнение следующих работ: (1-2), (1-3), (1-4), (2-5), (2-6), (3-6), (4-6), (4-7), (5-7), (5-6), (6-7). Продолжительность выполнения каждой работы равна .

Для того, чтобы началось выполнений рассматриваемого комплекса работ, необходимо, чтобы произошло событие 1. Затем начинается параллельное выполнение работ (1-2), (1-3) и (1-4). После завершения работы (1-2) начинают выполняться работы (2-5) и (2-6). По окончании работы (1-3) начинается выполнение работы (3-6). По окончании работы (1-4) начинается выполнение работы (3-6). По окончании работы (1-4) начинается выполнение двух параллельных работ (4-6) и (4-7). И так процесс ведётся последовательно до конечного события.

При построении сетевого графика необходимо учитывать следующие правила.

• События нумеруются так, чтобы для каждой работы номер начального события был меньше, чем номер конечного. Например, для работы (1-2), номер начального события — 1, конечного, 2 : 1<2.
• Каждая работа кодируется двумя символами: (1-2), (1-3) и так далее. Первая цифра означает начало работы и соответствует номеру предшествующего события. Вторая цифра означает окончание работы и соответствует номеру последующего события.
• Стрелки работы на сетевом графике направляют так, чтобы конец находился правее начала.
• Для удобства на сетевом графике следует избегать пересечения.
• На графике не может быть 2 и более работ, имеющих одинаковые коды.
• В сети не должно быть тупиков, то есть, событий, из которых не выходит пи одна работа (кроме последней).
• В сети не должно быть событий (кроме начального), которым не предшествует хотя бы одна работа.
• Два смежных события не могут быть связаны более чем одной работой. Например, нельзя изображать работы, как показано на рис. 4.2. Эти работы выполняются параллельно. Для правильного изображения необходимо ввести дополнительное событие и фиктивную работу (рис 4.3). Фиктивная работа (обозначается пунктирной линией) будет отражать логическую связь. Продолжительность фиктивной работы принимается равной нулю.

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

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

4.4, где работа разбита на три части: и . После выполнения начинаются работы и после и после —.

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

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

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

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

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

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

Наиболее вероятная оценка — возможное время выполнения данной работы при отсутствии неожиданностей.

Эти оценки являются исходными для определения ожидаемого времени выполнения работ .

Для нормального времени выполнения работ

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

где — вероятность принятия значения — постоянная, -параметры распределения, то при

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

Пример 4.1.

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

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

1. Анализ характеристик дорожной сети.
2. Анализ состояния и размещения заправочных станций, столовых и ремонтных мастерских.
3. Расчёт режимов движения автомобилей.
4. Разметка дорожного полотна.
5. Установка контрольных пунктов ГАИ.
6. Установка дорожных знаков.
7. Оборудование автобусных остановок.
8. Оборудование мест стоянки автомобилей.
9. Организация дорожного движения.
10. Выездной контроль над движением на дороге.
11. Контроль над состоянием дорожной сети.
12. Контроль над дорожными сооружениями.
13. Контроль над состоянием дорожных знаков.
14. Анализ дорожно-транспортных происшествий.
15. Разработка мероприятий по устранению конфликтных (аварийных) точек на дороге.
16. Устранение конфликтных точек на дороге.

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

Событие 2 соответствует моменту окончания анализа характеристик дорожной сети и началу расчётов режимов движения автомобилей.

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

Работа (4-5) является фиктивной. Она отражает только логическую связь и никакой физической работы не отражает. Её продолжительность берётся равной нулю.

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

Событие 5 соответствует моменту окончания разметки дорожного полотна и началу установки контрольных пунктов ГАИ, установки дорожных знаков, оборудованию автобусных остановок и мест стоянки автомобилей. Эти работы могут выполняться параллельно. Окончанию указанных работ соответствуют события 6, 7, 8 и 9. После завершения этих работ начинается эксплуатация дороги.

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

Конечным событием является событие 18. Оно соответствует окончанию рассматриваемого периода.

Сетевой график для данного примера приведён на рис. 4.5. Работы на графике означают: (1 -3) — анализ характеристик дорожной сети, (1-2) — анализ состояния и размещения заправочных станций, столовых и ремонтных мастерских, (3-4) — расчёт движения автомобилей, (2-4) — фиктивная работа, (4-5) — разметка дорожного полотна, (5-6) — установка контрольных пунктов ГАИ, (5-7) — установка дорожных знаков, (5-8) — оборудование автобусных остановок, (5-9) — оборудование мест стояики автомобилей, (6-10), (7-10), (8-10), (9-10) — фиктивные работы, (10-18) — организация дорожного движения, (10-11) — выездной контроль над движением на дороге, (10-12) — контроль над состоянием дорожной сети, (10-13) — контроль над дорожными сооружениями, (10-14) — контроль над состоянием дорожных знаков, (10-15) — анализ дорожно- транспортных происшествий, (15-16) — разработка мероприятий по устранению конфликтных точек на дороге, (16-17) — устранение конфликтных точек на дороге,, (12-18), (11-18), (17-18), (13-18), (14-18) — фиктивные работы. Продолжительность выполняемых работ показаны над стрелками. В качестве исследуемого периода взят один год.

Пример 4.2.

Требуется построить график перевозки населения по заявкам хозяйств.

Решение:

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

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

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

Работы на графике означают:

(1-2) — получение заявок на перевозки,

(2-3) — анализ пассажиропотока на транспортной сети,

(3-4) — составление маршрутов движения автобусов,

(4-5) — выбор подвижного состава,

(5-6) — составление расписания движения автобусов,

(6-7) — перевозка пассажиров,

(6-8) — контроль над работой подвижного состава на линии, (7-8) — анализ работы автобусов, (8-9) — составление отчёта о работе, (1-9) — управление транспортным процессом.

Продолжительность работы в условных единицах поставлена над дугами графа. Начальным событием является событие 1, конечным — событие 9.

Критический путь

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

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

Работы и события, через которые проходит критический путь, называются критическими. Для рассматриваемого сетевого графика критическими будут события: 1, 2, 3, 6, 7 и работы (1-2), (2-3), (3-6), (6-7).

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

Методы построения критического пути на сетевом графике

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

Метод потенциалов

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

Метод потенциалов рассматривается в направлении увеличения потенциалов вершин графа.

Потенциалы вершин вычисляются по формуле

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

Если , то вершине присваивается потенциал . Если то потенциал вершины принимается равным . Потенциал конечной вершины является длиной критического пути. Перед началом расчёта всем вершинам (событиям) графа (сетевого графика) присваиваются самые малые потенциалы — 0.

Пример 4.8.

Рассмотрим сетевой график, показанный на рис. 4.8.

Решение:

События пронумерованы цифрами в кружках: 1 — начальное событие, 16 — конечное событие. Продолжительность работ показана цифрами над рёбрами. Найдём критический путь с помощью метода потенциалов.

Присвоим всем вершинам графа (сетевого графика ) .

• Рассматриваем все вершины, связанные с вершиной 1 (событием 1):

Вычисленное значение больше ранее определённого потенциала .

Следовательно, событию 4 присваиваем новое значение потенциала (наибольшее из сравниваемых потенциалов).

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

Пример 4.4.

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

Решение:

Согласно принципу оптимальности Беллмапа, оптимальное управление на каждом этапе определяется целью управления, и состояния на начало этапа. Для свершения конечного события необходимо свершение предшествующих. Возможные состояния на начало последнего этапа работ — это свершение событий . Максимальная продолжительность пути, ведущая из 15 в 16, равна Вычисленные значения поставим над соответствующими событиями в квадратиках. Для того, чтобы было выполненное событие 15, необходимо выполнение событий 13 и 12. Определяем для них . Вершина 13 имеет 3 управления: 13-14, 13-16, 13-15. Для этих управлений равно:

Следовательно, для вершины

Для события 12 управление вынужденное. Для него

Предыдущим событием для вершины 14 является событие 11. Для него имеются два управления: 11-14 и 11-13:

Следовательно, для события 11 . И так проводятся вычисления до события 1. Получили критическое

Для определения самого критического пути рассматриваем сетевой график в обратном направлении от наибольшего. Полученный критический путь на графе (рис. 4.9 ) выделен жирной линией. Как видно из графика, он совпал с критическим путём, вычисленным методом потенциалов. Следовательно, решение найдено правильно.

Состояние сетевых графиков обычно ведётся в 4 этапа.

1. На первом этапе формулируется задание.
2. На втором этапе составляется структурная схема разработки.
3. На третьем этапе рассчитывается и строится график. Продолжительность работ определяется ответственными исполнителями или экспертами.
4. На четвёртом этапе проводится анализ построенного графика.

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

При планировании сложных комплексов взаимосвязанных работ и управления ходом их выполнения наиболее эффективны методы сетевого планирования и управления (СПУ). Разновидности этих методов получили названия PERT (Program Evaluation and Review Technique — оценка программ и способ проверки) и СРМ (Critical Path Method — метод критического пути). Оба метода проводят анализ проектов для составления временных графиков распределения фаз проектов. Методы, разработанные независимо друг от друга в разных странах, отличаются друг от друга тем, что в методе СРМ длительность каждого этапа проекта является детерминированной, а в системе PERT — стохастической.

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

Временные характеристики сетевого графика

Построенный сетевой график требует временной оценки.

Оценивание происходит по событиям и по работам.

Характеристиками событий являются:

• наиболее ранний срок наступления события на сети ,
• наиболее поздний срок наступления события на сети ,
• допустимый срок наступления события .

Характеристиками работ являются:

• раннее начало работы ,
• ранее окончание работы ,
• позднее начало работы ,

Позднее окончание работы ,

• полный запас времени .

Рассмотрим названные характеристики событий и работ.

Характеристики событий

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

Для начального события . Для любого другого события

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

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

Для критических событий

Для начального

Для других событий

где — наиболее поздний срок наступления последующего события.

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

Для критического пути

• Допустимый срок наступления события удовлетворяет условию

Для критических событий

Пример 4.5.

Для каждого из трех фрагментов сетевых графиков, представленных на рис. 4.10, подсчитать .

Решение:

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

На рис. 4.10 а) за событием 7 следует работа (7-8). Причём

Это означает, что работа (7-8) может начаться не позднее, чем за 6 временных единиц до события 8. Известно ещё, что

Следовательно, поздний срок наступления события 7

На рис. 4.10 б) за событием 7 следуют две работы : (7-8) и (7-9). Причём

Работа (7-8) может начаться не позднее, чем за 2 временные единицы до события 8, а работа (7-9) — не позднее, чем за 3 временные единицы до события 9.

Так как

то поздний срок наступления события 7 равен наименьшей из разностей:

Если событие 7 наступит позднее, то работа (7-8) не закончится па 13-й временной единице и это вызовет задержку наступления события 8.

Аналогичным образом определяется для рис. 4.10 в):

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

Характеристики работы

• Раннее начало работы — . Оно определяется как продолжительность пути наибольшей длины от начального события до предшествующего

Раннее начало работ, выходящих из первого события, равно нулю.

• Раннее окончание работы — :

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

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

• Позднее окончание работы —

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

Для работы (8-9) (рис. 4.11)

В общем случае

• позднее окончание определяется минимальной разностью позднего окончания и продолжительности последующих работ.

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

• Полный общий запас времени представляет собой время, на которое можно перенести начало работы

Например, для графа, показанного па рис. 4.11 для работы (5-9)

• Свободный ( независимый) запас времени рассчитывается для одной или нескольких работ графика и определяется по формуле

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