Главная Случайная страница


Категории:

ДомЗдоровьеЗоологияИнформатикаИскусствоИскусствоКомпьютерыКулинарияМаркетингМатематикаМедицинаМенеджментОбразованиеПедагогикаПитомцыПрограммированиеПроизводствоПромышленностьПсихологияРазноеРелигияСоциологияСпортСтатистикаТранспортФизикаФилософияФинансыХимияХоббиЭкологияЭкономикаЭлектроника






Замкнутая модель транспортной задачи.

Пусть в пунктах A1,…,Am производится некоторый продукт в количествах a1,…,am > 0. Этот продукт перевозится в пункты B1,…,Bn, где он полностью потребляется в количествах b1,…,bn > 0. Для каждой пары индексов i,j задана стоимость cij 0 перевозок единицы продукта из пункта производства Ai в пункт потребления Bj. Необходимо перевезти весь произведенный продукт из пунктов A1,…,Am в пункты потребления B1,…,Bn. При этом требуется, чтобы потребности каждого из пунктов B1,…,Bn полностью удовлетворялись.

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

Назовем планом перевозок неотрицательную матрицу X = (xij) размера m×n, в которой число xij ≥ 0 указывает количество продукта, перевозимого из пункта Ai в пункт Bj, 1 ≤ i m, 1 ≤ jn.

Стоимость z(X) перевозок является линейной функцией от X, именно, z(X) = ∑i,j cijxij, xij ≥ 0.

В задаче требуется найти такой план перевозок X, чтобы его стоимость была бы минимальной, причем весь продукт был бы вывезен из пунктов производства, доставлен в пункты потребления, и все потребности были бы полностью удовлетворены. Отсюда следует, что транспортная задача является задачей линейного программирования. Действительно то, что весь продукт, производимый в Ai вывозится записывается в виде уравнения

j xij = ai , ( i = 1, …, m )

Аналогично, условие того, что потребности пункта Bj полностью удовлетворены, записывается в виде уравнения

i xij = bj, ( j = 1, …, n ).

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

(1)

xij ≥ 0;

z(X) = ∑i,j cijxij → min.

Сформулированная в (1) транспортная задача называется замкнутой моделью.

Другие модели транспортной задачи будут рассмотрены позднее.

Назовем план перевозок X допустимым, если выполнены все ограничения из (1). Укажем способ построения допустимого решения методом минимального элемента.

Этот способ возможен, если ∑i ai = ∑j bj. Для этого выберем клетку с индексами (i,j), в которой стоит минимальное из чисел cij. В эту клетку помещаем число xij = min(ai ,bj ). Если ai < bj, то все остальные элементы i-ой строки полагаем равными нулю, число bj заменяем на bjai, а ai на 0. Если же aibj, то все остальные элементы j-ого столбца полагаем равными нулю, число ai заменяем на aibj, а bj на 0. В результате число пустых строк или столбцов уменьшается на единицу. Продолжая этот процесс, получаем первоначальный план.

Продемонстрируем этот метод на конкретном примере. Пусть a1 = 18, a2 = 10, a3 = 12, b1 = 16, b2 = 9, b3 = 15, а матрица C имеет вид

 

 

Построим вспомогательную таблицу

  b1 = 16 b2 = 9 b3 = 15
a1 = 18   с11=1   с12=3   с13=4
     
a3 = 10   с21=2   с22=5   с23=3
     
a3 = 12   c31=6   c32=7   c33=5
     

 

Минимальный элемент с11=1. В клетку (1,1) помещаем min(18,16)=16. В соответствии с изложенным правилом получаем таблицу

  b1 = 0 b2 = 9 b3 = 15
a1 = 2   с11=1   с12=3   с13=4
     
a3 = 10   с21=2   с22=5   с23=3
     
a3 = 12   c31=6   c32=7   c33=5
     

 

Далее из всех незаполненных клеток, находящихся в двух последних столбцах выбираем ту, в которой число cij минимально. Это, например, с23=3. Применяя общее правило, получаем новую таблицу

  b1 = 0 b2 = 9 b3 = 5
a1 = 2   с11=1   с12=3   с13=4
     
a3 = 0   с21=2   с22=5   с23=3
     
a3 = 12   c31=6   c32=7   c33=5
     

 

Далее выбираем клетку (1,2) с с12=3. Получаем новую таблицу

  b1 = 0 b2 = 7 b3 = 5
A1 = 0   с11=1   с12=3   с13=4
     
A3 = 0   с21=2   с22=5   с23=3
     
A3 = 12   c31=6   c32=7   c33=5
     

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

  с11=1   с12=3   с13=4
     
  с21=2   с22=5   с23=3
     
  c31=6   c32=7   c33=5
     

 

Теорема 1.Транспортная задача (1) имеет решение тогда и только тогда, когда

i ai = ∑j bj.

Доказательство.Пусть решение X существует. Тогда из (1) вытекает, что

i ai = ∑ij xij = ∑ji xij = ∑j bj.

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

Из ограничений видно, что все элементы допустимой матрицы неотрицательны и потому ограничены. Следовательно, функция z(X) достигает минимума на некотором допустимом плане, т.е. транспортная задача всегда имеет решение.

Рассмотрим двойственную задачу линейного программирования к транспортной задаче (1). В соответствии с общим правилом запишем (1) в виде

j xij ai , i = 1, …, m;

- ∑j xij ≤ - ai , i = 1, …, m;

i xijbj, j = 1, …, n; (2)

- ∑i xij ≤ - bj, j = 1, …, n

xij ≥ 0;

- z(X) = - ∑i,j cijxij → max.

Тогда двойственная задача имеет вид

ai’ - ai’’ + βj’ - βj’’ ≥ - cij , i = 1, …, m, j = 1, …, n;

ai’,ai’’,βj’, βj’’ ≥ 0, i = 1, …, m, j = 1, …, n; (3)

T’= a1a1 – a1’’a1 + … + amam – am’’am + β1b1 – β1’’b1 + … + βmbm – βm’’bm → min

Положим T = -T’ и ai = ai’’ - ai’, βj = βj’’ - βj’, i = 1, …, m, j = 1, …, n.

Тогда (3) имеет вид

ai + βjcij , i = 1, …, m, j = 1, …, n; (4)

T = a1a1 + … + amam + β1b1 + … + βmbm → max.

Теорема 2.Для того, чтобы допустимый план перевозок X был оптимальным необходимо и достаточно, чтобы существовали такие числа (потенциалы) a1, … , am1, … , βn, для которых

1) ai + βjcij при всех i,j;

2) ai + βj = cij, если xij > 0.

Доказательство.Проверим достаточность. Пусть задан допустимый план X = (xij), и a1, … , am1, … , βn из условий теоремы. Предположим, что Y = (yij) - произвольный допустимый план. В силу ограничений (1) и свойств 1), 2) из условия теоремы получаем

z(Y) = ∑i,j cijyij ≥ ∑i,j (ai + βj)yij = ∑i aij yij + ∑j βji yij = ∑i ai ai + ∑j βj bj = ∑i aij xij + ∑j βji xij = ∑i,j (ai + βj)xij = ∑i,j cijxij = z(X).

Проверим теперь необходимость. Пусть X 0= (xij0) – оптимальный план и a1, … , am1, … , βn – оптимальное решение двойственной задачи. По (4) выполнено неравенство 1) из условия теоремы. Кроме того, по теореме о равновесии получаем (ai+ βj - cij) xij0 = 0. Поэтому если xij0 > 0, то выполнено равенство 2) из условия теоремы.

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

G Í {1, … ,m }, H Í {1, … ,n},

что одно из них собственное и

åi Î G ai = åj Î H bj

Другими словами, суммарный запас продукта в пунктах Ai, i Î G, совпадает с потреблением в пунктах Bj, j Î H.

Далее мы будет предполагать, что рассматриваемая транспортная задача невырождена. Изложим метод потенциалов решения невырожденной транспортной задачи, опирающийся на теорему 2. Мы уже имеем допустимый первоначальный план, построенный методом минимального элемента. Из этого построения видно, что число ненулевых элементов в первоначальном плане равно n + m – 1. Найдем первоначальную систему потенциалов. Для этого в соответствии с условием 2) из теоремы 2 составим систему из n + m – 1 линейного уравнения

ai + βj = cij.

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

Положим a1 = 0. Тогда β1 = 1, β2 = 3. Далее a3 = 4, β3 = 1, a2 = 2.

Для полученной системы потенциалов проверяем выполняется ли условие 1) из теоремы 2. Для этого составляем вспомогательную матрицу D, в которой на месте (i,j) стоит dij = ai + βj . Если dij £ cij для всех (i,j), то построенный план по теореме 2 является оптимальным. Далее вычисляем значение целевой функции z(X) для этого плана. В нашем примере

Мы видим, что условие 1) нарушается в клетке (1,2).

Опишем основной шаг алгоритма, состоящий в улучшении плана. Выберем клетку (p,q), в которой ap + βq > cpq. По построению xpq = 0. Нам потребуется

Предложение.Пусть план X = (xij) допустим, и xpq = 0 для некоторой пары индексов (p,q). Тогда существует и единственная такая последовательность различных строк p = i(0), i(1), … , i(k) и различных столбцов j(1), … , j(k-1), j(k) = q в матрице X, что элементы этой матрицы, стоящие в клетках (i(0), j(1)), (i(1), j(1)), (i(1), j(2)), (i(2), j(2)), … , (i(k), j(k-1)), (i(k), j(k)), отличны от нуля.

Заметим, что если мы начнем движение по матрице X с клетки (p,q), двигаясь далее по клеткам (i(0), j(1)), (i(1), j(1)), (i(1), j(2)), (i(2), j(2)), … , (i(k), j(k-1)), (i(k), j(k)) из предложения, то мы сначала идем по строке, далее по столбцу, затем снова по строке и т. д. На последнем шаге мы идем по строке и попадаем в исходный столбец с номером q.

Расставим во всех выбранных клетках чередующиеся метки +, - , начиная с + в начальной выбранной клетке (p,q). Пусть q - минимальный среди элементов xij, стоящих в выбранных клетках с меткой -. В клетках с меткой + число xij увеличиваем на q, а в клетках с меткой - уменьшаем на q. Все остальные элементы матрицы X не меняем. Получаем новый допустимый план X’ = (xij’). Сравним значения целевых функций для планов X и X’. Имеем

z(X') - z(X) = åi,j cij(x'ij - xij) = ås=0k-1 ci(s)j(s)(x'i(s)j(s) - xi(s)j(s) ) +

ås=0k ci(s)j(s+1)(x'i(s)j(s+1) - xi(s)j(s+1) ) = ås=0k-1 ci(s)j(s)q - ås=0k ci(s)j(s+1)q = q[ ci(0)j(0) + (ai(1) + bj(1)) + ¼ + (ai(k-1) + bj(k-1)) - (ai(0) + bj(1)) - … - (ai(k-1) + bj(k))] = q[ ci(0)j(0) - (ai(0 + bj(k))] < 0.

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

Продемонстрируем работу этого алгоритма на рассмотренному выше примере. Мы выбрали клетку (2,1). Выбираем путь (2,3), (3,4), (3,2), (1,2), (1,1). Расставляем метки + для клеток (2,1), (3,4), (1,2), и метки – для клеток (2,3), (3,2), (1,1). Минимальный элемент q стоящий в клетках с меткой – равен 7. Изменяем матрицу и получаем новую таблицу

 

 

  с11=1   с12=3   с13=4
     
  с21=2   с22=5   с23=3
     
  c31=6   c32=7   c33=5
     

 

Для новой таблицы пишем систему уравнений для нахождения потенциалов:

Полагаем a1 = 0. Тогда β1 = 1, и поэтому β2 = 3, a2 = 1. Далее β3 = 2, a3 = 3. Таким образом, матрица D имеет вид

В соответствии с теоремой 2 построенный план

оптимален. Поэтому ответом является

z(X) = 9´1 + 9´3 + 7´2 + 3´3 + 12´5 = 9 + 27 + 14 + 9 + 60 =119.

2.2. Другие модели транспортной задачи.

 

1. Открытая модель. Пусть производится больше продукта, чем потребляется, т. е. ∑i ai > ∑j bj. Тогда вводится фиктивный пункт Bn+1, с потреблением bn+1= ∑i ai - ∑j bj, причем стоимость перевозки в него всегда равна 0. Тогда возникает замкнутая модель и ее решение будет оптимальным решением для исходной модели.

Аналогично, если ∑i ai < ∑j bj, то вводится фиктивный производитель An+1, с производством an+1= ∑j bj - ∑i ai, причем стоимость перевозки из него нулевая. Тогда снова возникает замкнутая модель и ее решение будет оптимальным решением для исходной модели.

2. Блокирование перевозок.Если по пути (i,j) перевозки запрещены, то полагаем, что cij = M – достаточно большое число, которое «не меняется при всех наших преобразованиях», т. е. при прибавлении к нему конечных чисел. Тогда перевозки по этому пути не могут быть осуществлены ввиду большой их стоимости.

3. Фиксированные перевозки. Пусть по пути (i,j) перевозки имеют фиксированное значение rij. В этом случае из ai и bj вычитается rij. Далее применяется модель с запретом перевозки по этому пути.

4. Дополнительные требования.Пусть по пути (i,j) перевозки должны иметь значение xij ³ rij. Тогда из ai и bj вычитается rij и далее решается обычная транспортная задача. Если же дано ограничение xij £ rij,то заявку bj заменяется на rij и вводится новый потребитель с потреблением bj - rij. Тарифы перевозок в новый пункт те же, что и в Bj, за исключением тарифа из Ai, который становится равным достаточно большому числу M.

Глава III. Игровые методы и модели.

 

Понятие об игровых моделях.

 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

В игре могут сталкиваться интересы двух или более игроков.

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

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

В зависимости от числа возможных стратегий игры делятся на конечные и бесконечные.

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

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

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

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

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

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

1. В чем состоит оптимальность поведения каждого из игроков в игре?

2. Существуют ли стратегии игроков, которые обладали бы атрибутами оптимальности?

3. Если существуют оптимальные стратегии, то как их найти?

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

Постановка игровых задач.

 

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

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

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

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

Каждый исход a Î A является функцией двух аргументов: , где x Î X, y Î Y. Функция F называется функцией реализации и она сопоставляется исход по каждой паре - «альтернатива - состояние среды».

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

y1 ... yj ... ym

x1 F(x1, y1) ... F(x1, yj) ... F(x1, ym)

... ... ... ... ... ...

xi F(xi, y1) ... F(xi, yj) ... F(xi, ym)

... ... ... ... ... ...

xn F(xn, y1) ... F(xn, yj) ... F(xn, ym)

 

Последнее изменение этой страницы: 2016-08-11

lectmania.ru. Все права принадлежат авторам данных материалов. В случае нарушения авторского права напишите нам сюда...