Особенности экономико-математической модели транспортной задачи

1. Система ограничений сразу имеет вид уравнений, поэтому отпадает необходимость вводить добавочные переменные.

x ₁₁ + x ₁₂ +… + x₁ = M₁

x ₂₁ + x ₂₂ + … + x₂ = M₂

…………………………

x_i1 + x_i2 + … + x_i = M _i

………………………..

x_k1 + x_k2 + … + x_k = M _k

 

 

x ₁₁ + x ₁₂ +… + x_k1 = N₁

x ₂₁ + x ₂₂ + … + x_k2 = N₂

…………………………

x_1j + x_{2 j}+ … + x_kj = N _j

………………………..

x₁ + x₂ + … + x_k = N (1)

2. Матрица коэффициентов при переменных в системе ограничений (1) состоит только из 1 и 0.

3. Система ограничений (1) включает k уравнений, связывающих поставки i-го поставщика с мощностью M _i и i =1,2,..., k, и уравнений, связывающих поставки j-ому потребителю со спросом N и j=1,2,…, этого потребителя. Заметим, что число k равно числу строк исходной таблицы, а число равно числу столбцов. Число переменных x_ij, входящих в целевую функцию и в систему ограничений (1), равно произведению k и , т.е. числу клеток таблицы.

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

Открытые задачи обязательно приводят к закрытому виду путем введения фиктивного поставщика (или потребителя), мощность которого равна . А тарифы перевода у фиктивного все равны нулю.

Особенности ЭММ:

1) каждая переменная входит в систему ограничений дважды, поэтому число основных (или базисных) элементов будет равно k + –1 (‘nj условие базисности решения);

2) в любой ТЗ значение z(x) min;

3) решение ТЗ оформляется на каждом шаге в виде таблиц, в которых должны быть заполнены k + –1 клеток, в ходе решения происходит переход от одной таблицы к другой, от 1-го поставщика к другому, пока не будет найдено оптимальное распределение поставок.

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

Заполнение таблицы ТЗ начинается с левого верхнего угла, состоящее из ряда однотипных шагов. На каждом шаге, исходя из запасов очередного поставщика и запросов потребителя, заполняется только одна клетка, и соответственно исключается из рассмотрения один поставщик или потребитель. При этом нулевые перевозки принято заносить в таблицу только в том случае, когда они попадают в клетку (ij), подлежащую заполнению. Остальные клетки с нулевыми перевозками остаются пустыми. Во избежание ошибок после построения начального опорного решения необходимо проверить, что число занятых клеток равно k + –1 и вектора условий, соответствующие этим клеткам, линейно независимы.

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

Метод минимальной стоимости позволяет построить опорное решение, которое достаточно близко к оптимальному, т.к. исп-ют матрицу стоимости ТЗ: C = (C_ij), где i=1,2,…,m; а j=1,2,…,n. Как и метод северо-западного угла он состоит из ряда однотипных шагов, на каждом их которых заполняется только 1 клетка таблицы, соответствующая минимальной стоимости (min(C_ij)) и исключается из рассмотрения только 1 строка (поставщик) или 1 столбец (потребитель). Очередную клетку, соответствующую (min(C_ij)), заполняют по тем же правилам, что и в методе северо-западного угла.

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

Для проверки линейной независимости векторов условий соответствующих координатов допустимого решения исп-ют циклы. Циклом наз-ся такая последовательность клеток таблицы ТЗ (i₁,j₁), (i₂,j₂), …, (i_k,j ), в которой две и только две соседние клетки расположены в одной строке или столбце, причем 1-е и последние также находятся в одной строке или одном столбце. Циклом ТЗ называется несколько клеток, соединенных замкнутой ломанной линией так, чтобы 2 соседние вершины ломанной были расположены либо в 1 строке, либо в 1 столбце. Ломанная может иметь точки самопересечения, но не в клетках цикла.

 

 

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

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

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

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

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

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

 

 

Теория игр и принятие решений. Постановка задач и основные понятия

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

· определенность

· риск

· неопределенность

· конфликт

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

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

· математическое ожидание прибыли

· математическое ожидание чистого дохода

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

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

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

 

 

Платежная матрица

Пусть имеем парную конечную игру размерности mxn, т.е. игрок А может принять стратегии А₁, А₂, …, А_n, а игрок B может принять стратегии B₁, B₂, …, B_m. В результате выбора ими любой пары стратегии A_iB_j однозначно будет определен исход (a_ij). Пусть значение (a_ij) известны для всех пар стратегий.

Bj Ai	B1	B2	…	Bn
А1	a11	a12	…	a1n
А2	a21	a22	…	a2n
…	…	…	…	…
Аm	am1	am2	…	amn

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

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

 

 

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

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

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

2) добавочные переменные взять в качестве остальных, выразить основные переменные через свободные, найти базисные решения; если полученное базисное решение будет положительным, то переходят к пункту 4, а если недопустимое – к пункту 3;

3) от полученного недопустимого базисного решения задачи переходят к допустимому или устанавливают, что система ограничений противоречива;

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

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

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

7) выражают новые основные переменные и целевую функцию через свободные переменные, начиная с выделенного уравнения;

8) повторяют пункты 5-7, пока не будет достигнут критерий оптимальности, после этого выписывают компоненты оптимального решения и находят оптимум целевой функции.

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

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