Основные теоретические положения симплексного метода решения ЗЛП

ОГЛАВЛЕНИЕ

ВВЕДЕНИЕ

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

Большинство объектов, изучаемых экономической наукой, может быть охарактеризовано кибернетическим понятием – сложная система.

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

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

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

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

2.

ПОСТАНОВКА ЗАДАЧИ

Основные теоретические положения симплексного метода решения ЗЛП

 

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

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

Решить подобную задачу бывает непросто, особенно при наличии большого числа вариантов. Время и затраты при выборе оптимума не всегда оправданны: издержки поиска и перебора вариантов могут превысить достигнутый выигрыш. Как показывает практика, опыт и интуиция оказываются недостаточными для обоснования оптимального решения. Более надежный и эффективный способ — использование математических (количественных) подходов и расчетов. Однако математические подходы и обоснования длительное время игнорировались теоретиками, делавшими “погоду” в экономической науке. Многие важные работы были заморожены, публикации экономистов-математиков тормозились и ограничивались. И все же в тот период математические изыскания продолжались, даже в условиях гонения на математиков были достигнуты блестящие результаты. Одним из наиболее значительных и ярких достижений в области экономико-математических исследований было открытие Леонидом Витальевичем Канторовичем (1912—1986) Метода линейного программирования.

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

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

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

Общий вид задач линейного программирования

 

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

F(X)=c₁x₁+c₂x₂+…+c_nx_n→ max(min)

a₁₁x₁+a₁₂x₂+…+a_1nx_n=b₁,

…………………………

a_i1x₁+a_i2x₂+…+a_inx_n=b_i,

 

a_(i+1)1x₁+a_(i+1)2x₂+…+a_(i+1)nx_n≤b_i+1

………………………..

a_m1x₁+a_m2x₂+…+a_mnx_n≤b_m

 

x_j≥0, j=1,2,…,t; t≤n

 

Данная запись означает следующее: найти экстремум целевой функции (1.1) и соответствующие ему переменные X=(X₁, X₂,...,X_n) при условии, что эти переменные удовлетворяют системе ограничений (1.2) и условиям неотрицательности (1.3).

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

Множество допустимых решений (планов) задачи образует область допустимых решений(ОДР).

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

 

Приведение общей задачи линейного программирования к канонической форме.

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

Возьмем линейное неравенство a₁x₁+a₂x₂+...+a_nx_n≤b и прибавим.

Это может быть сделано следующим образом: к его левой части некоторую величину x_n+1, такую, что неравенство превратилось в равенство a₁x₁+a₂x₂+...+a_nx_n+x_n+1=b. При этом данная величина x_n+1 является неотрицательной.

 

МЕТОДЫ РЕШЕНИЯ

Примеры использования симплекс-метода в экономике

 

Задачи ЛП нашли широкое применение в экономике. Рассмотрим это на примерах:

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

Пример 2. Группа истребителей поднимается в воздух для перехвата одиночного самолёта противника. Цель операции - сбить самолёт. Показатель эффективности - вероятность поражения цели.

Пример 3. Ремонтная мастерская занимается обслуживанием машин; её рентабельность определяется количеством машин, обслуженных в течение дня. Показатель эффективности - среднее число машин, обслуженных за день.

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

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

Пример 6. Проводится борьба за экономию средств при производстве определённого вида товара. Показатель эффективности - количество сэкономленных средств.

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

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

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

 

ПРИМЕР РЕШЕНИЯ

Идея симплекс-метода относительно проста. Пусть в задаче линейного программирования имеется п переменных и т независимых линейных ограничений, заданных в форме уравнений. Мы знаем, что оптимальное решение (если оно существует) достигается в одной из опорных точек (вершин ОДР), где по крайней мере k = n - m из переменных равны нулю. Выберем какие-то к переменных в качестве свободных и выразим через них остальные т базисных переменных. Пусть, например, в качестве свободных выбраны первые k = n - m переменныхx₁, x₂,…,x_k,а, остальные m выражены через них(формула 2.1):

x_k+1=α_k+1.1x₁+α_k+1.2x₂+ +α_k+1.kx_k+β_k+1;

x_k+2= α_k+2.1x₁+α_k+2.2x₂+ +α_k+2.kx_k+β_k+2;(2.1)

……………………………………

x_n= α_n1x₁+α_n2x₂+ +α_nkx_k+β_n.

Предположим, что все свободные переменныеx₁, x₂,…,x_k равны нулю.

При этом мы получим:

x_k+1=β_k+1;

x_k+2=β_k+2;

…….. (2.2)

X_n=β_n

 

Это решение может быть допустимым или недопустимым. Оно допустимо, если все свободные членыβ_k+1, β_k+2,…,β_n(2.2)неотрицательны. Предположим, что это условие выполнено. Тогда мы получили опорное решение. Но является ли оно оптимальным? Чтобы проверить это, выразим целевую функцию Z через свободные переменныеx₁, x₂,…,x_k.

Z=γ₀+γ₁x₁+γ₂x₂+…+γ_kx_k (2.3)

Очевидно, что приx₁=x₂=…=x_k=0, Z=γ₀. Проверим, может ли быть улучшено решение, т. е. получено уменьшение функции Z c увеличением каких-нибудь из переменныхx₁, x₂,…, x_k(2.2) (уменьшать их мы не можем, так как все они равны нулю, а отрицательные значения переменных недопустимы). Если все коэффициентыγ₁,γ₂,…,γ_kв (2.3) положительны, то увеличение каких-либо из переменныхx₁,x₂,…,x_k(2.2) не может уменьшить Z; следовательно, найденное опорное решение является оптимальным. Если же среди коэффициентовγ₁,γ₂,…,γ_k есть отрицательные, то, увеличивая некоторые из переменныхx₁,x₂,…,x_k(те, коэффициенты при которых отрицательны), мы можем улучшить решение.

Пусть, например, коэффициентγ₁в (2.3) отрицателен. Значит, есть смысл увеличитьx₁, т. е. перейти от данного опорного решения к другому, где переменнаяx₁не равна нулю, а вместо нее равна нулю какая-то другая. Однако увеличиватьx₁следует с осторожностью, так чтобы не стали отрицательными другие переменныеx_k+1, x_k+2,…,x_n выраженные через свободные переменные, в частности черезx₁формулами (2.2).

Например, если коэффициент приx₁в соответствующем x_j уравнении (2.2) отрицателен, то увеличениеx₁может сделать x_j отрицательным. Наоборот, если среди уравнений (2.2) нет уравнения с отрицательным коэффициентом приx₁то величинуx₁можно увеличивать беспредельно, а, значит, линейная функция Z не ограничена снизу и оптимального решения ОЗ не существует.

Допустим, что это не так и что среди уравнений (2.2) есть такие, в которых коэффициент приx₁отрицателен. Для переменных, стоящих в левых частях этих уравнений, увеличениеx₁опасно — оно может сделать их отрицательными.

Возьмем одну из таких переменных x_l и посмотрим, до какой степени можно увеличитьx₁, пока переменная x_l не станет отрицательной. Выпишем l-e уравнение из системы (2.2):

x_l=α_l1x₁+α_l2x₂+…+α_lkx_k+β_l (2.4)

Здесь свободный членβ_l≥0, а коэффициентα_l1отрицателен.

Легко понять, что если мы оставимx₂=x₃=…=x_k=0, тоx_kможно увеличивать только до значения, равного–β_l/α_l1,а при дальнейшем увеличенииx₁переменнаяx₁станет отрицательной.

Выберем ту из переменныхx_k+1,x_k+2,…,x_n, которая раньше всех обратится в нуль при увеличении x₁, т. е. ту, для которой величина–β_l/α_l1наименьшая. Пусть это будетx_r. Тогда имеет смысл разрешить систему уравнений (2.2) относительно других базисных переменных, исключаяиз числа свободных переменныхx₁и переводя вместо нее в группу свободных переменныхx_r. Действительно, мы хотим перейти от опорного решения, задаваемого равенствамиx₁=x₂=…=x_n=0 к опорному решению, в котором ужеx₁≠0, аx₂=…=x_k=x_r=0. Первое опорное решение мы получили, положив равными нулю все прежние свободные переменныеx₁,x₂,…,x_kвторое мы получим, если обратим в нуль все новые свободные переменныеx₂,x₃,…,x_k,x_r.

Базисными переменными при этом будутx_l,x_k+1,x_k+2,…,x_r-1, x_r-1,…,x_r.

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

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

-5x₁-x₂+2x₃≤2;

-x₁+x₃+x₄≤5; (2.5)

-3x₁+5x₄≤7.

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

Z=5x₁-2x₃

Приводя неравенства к стандартному виду (≥0) и вводя добавочные переменныеy₁,y₂,y₃переходим к условиям-равенствам:

y₁=5x₁+x₂-2x₃+2

y₂=x₁-x₃-x₄+5 (2.5)

y₃=3x₁-5x₄+7

Число переменных (n = 7) на 4 превышает число уравнений (т = 3). Значит, четыре переменные могут быть выбраны в качестве свободных.

 

Пусть в качестве свободных переменных выступаютx₁,x₂,x₃,x₄. Положим их равными нулю и получим опорное решение:

x₁=x₂=x₃=x₄=0;

y₁=2, y₂=5, y₃=7.

При этих значениях переменных Z= 0.

Это решение не оптимально, поскольку в линейной функции Z коэффициент приx₃отрицателен. Значит, увеличиваяx₃можно уменьшить Z.

Попробуем увеличиватьx₃.Из выражений (2.5) видно, что вy₁и y₂переменнаяx₃входит с отрицательным коэффициентом, значит, при увеличенииx₃соответствующие переменные могут стать отрицательными.

Определим, какая из этих переменных (y₁илиy₂)раньше обратится в нуль при увеличенииx₃Очевидно, что этоy₁она станет равной нулю приx₃=1, а величинаy₂— только приx₃= 5.

Выбирается переменная у, и вводится в число свободных вместоx₃Чтобы разрешить систему (2.5) относительноx₃, y₂, y₃поступим следующим образом. Разрешим первое уравнение (2.5) относительно новой базисной переменной x₃:

x₃=5/2*x₁+1/2*x₂-1/2*y₁+1

Это выражение подставляется вместоx₃во второе уравнение:

x₃=5/2*x₁+1/2*x₂-1/2y₁+1;

y₂=-3/2*x₁-1/2*x₂+1/2*y₁-x₄+4; (2.6)

y₃=3x₁-5x₄+7.

Что касается третьего уравнения, то оно, как не содержащееx₃не изменится. Система (2.2) приведена к виду со свободными переменнымиx₁, x₂, y₁, x₄и базиснымиx₃, y₂, y₃.

Положим теперь свободные переменные равными нулю. Функция приобретает значение Z=-2, что меньше (лучше), чем прежнее значение Z= 0.

Это решение все еще не оптимально, так как коэффициент приx₂в выражении (2.7) отрицателен, и переменнаяx₂может быть увеличена. Это увеличение, как это видно из системы (2.6), может сделать отрицательнойy₂(в первое уравнениеx₂входит с положительным коэффициентом, а в третьем — отсутствует).

Поменяем местами переменныеx₂ и y₂— первую исключим

из числа свободных, а вторую — включим. Для этого разрешим второе уравнение (2.6) относительноx₂и подставимx₂в первое уравнение. Получим следующий вид системы (2.5):

x₃=x₁-y₂-x₄+5

y₂=-3x₁-2y₂+y₁-2x₄+8 (2.7)

y₃=3x₁-5x₄+7

Выразим Z через новые свободные переменные:

Z=3x₁+2y₂-y₁+2x₄-8+y₁-2=3x₁+2y₂+2x₄-10 (2.8)

Полагаяx₁=y₁=y₂=x₄=0, получим Z = -10.

Это решение является оптимальным, так как коэффициенты при всех свободных переменных в выражении (2.8) неотрицательны. Итак, оптимальное решение ОЗ найдено (2.9):

x₁^*=0, x₂^*=8, x₃^*=5, x₄^*=0, y₁^*=0, y₂^*=0, y₃^*=7. (2.9)

При таких значениях переменных линейная функция Z принимает минимальное значение (2.10):

Z_min=-10 (2.10)

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

 

Двойственная задача

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

 

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

Максимизировать:

L(x) = сумма от j=1 до n (сj xj)

При условиях:

сумма от j=1 до n (аjXj)=bv, (v=1,2,....m)

или:

сумма от j=1 до n (АjXj)=b, xj>=0, j=1,2,...n

 

Составим двойственную задачу по условиям прямой задачи и определим области допустимых решений ДП:

maxZ=x₁-3x₃-3x₄-MR₁-MR₂

y₁: x₁+2x₃-2x₄+x₅=4

y₂: 3x₁-4x₃+4x₄+R₁=11

y₃: x₁+x₃-x₄-x₆+R₂=0

minW=4y₁+12y₂

x₁: y₁+3y₂+y₃≥1

x₃: 2y₁-4y₂+y₃≥-3

 

-2y₁+4y₂-y₃≤3(1)

X₄: -2y₁+4y₂-y₃≥3 (2)

X₅: y₁≥0

X₆: -y₃≥0 => y₃≤0

R₁: y₂≥-M

R₂:y₃≥-M

Итак, получено: y₁≥0,y₂≤≥0,y₃≤0.

Приведём запись двойственной задачи к канонической форме. На основании полученных ОДР двойственных переменных введём необходимые подстановки:

y₂=y₄-y₅; y₃=-ỹ_3; ỹ₃,y₄,y₅≥0

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

minW=4y₁+12y₄-12y₅+MR₁+MR₂

y₁+3y₄-3y₅-ỹ₃-y₆+R₁=1 (3)

-2y₁+4y₄-4y₅+ỹ₃+R₂=3 (4)

 

Решим ДЗ симплекс методом:

Из (3) выразим:

R₁=1-y₁-3y₄+3y₅+ỹ₃+y₆

Из (4) выразим:

R₂=3+2y₁-4y₄+4y₅-ỹ₃

W+y₁(-4-M)+y₄(-12+7M)+y₅(12-7M)-My₆=4M

ЗАКЛЮЧЕНИЕ

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

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

Задачи линейного программирования решаются несколькими методами:

1. графический метод;

2. симплекс-метод;

3. двойственный симплекс-метод.

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

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

СПИСОК ЛИТЕРАТУРЫ

 

1. И.К. Волков, Е.А. Загоруйко. «Исследование операций», Издательство МГТУ им Н.Э. Баумана, Москва 2002.

2. А.В. Аттетков и др., «Методы оптимизации», Издательство МГТУ им Н.Э. Баумана, Москва 2003.

3. О.А. Косоруков, А.В. Мищенко «Исследование операций», Издательство «Экзамен», Москва 2003.

4. О.И. Ларичев, «Теория и методы принятия решений», Физматкнига, Москва 2006.

5. Вапник В.Н., Червоненкис А.Я., «Теория распознавания образов», издательство «Высшая школа», Москва 1974.

6. Хэмди А. Таха, «Введение в исследование операций», издательский дом «Вильямс», Москва 2001.

7. И.Л. Акулич «Математическое программирование в примерах и задачах», издательство «Высшая школа», Москва 1986.

 

ПРИЛОЖЕНИЕ 1

 

Найти минимум функции методом множителей Лагранжа:

F(x,y)=x²+y²+ax+by+c→ min

dx+ey+r=0

a
b	-4
c
d	-4
e	-4
r	-4

 

1. Записывается функция Лагранжа:

min(x²+y²+2x-4y+5)

-4x-4y-4=0

f(x,y)= x²+y²+2x-4y+5

g₁(x,y)=0

g₁(x,y)= -4x-4y-4

Λ=(x,y, λ)= x²+y²+2x-4y+5+λ(-4x-4y-4)

 

2. Приравнять к нулю градиент функции Лагранжа и найти стационарные точки:

 

 

 

ПРИЛОЖЕНИЕ 2

Задание 1.

 

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

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

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

Чистой стратегией игрока I является выбор одной из n строк матрицы выигрышей А, а чистой стратегией игрока II является выбор одного из столбцов этой же матрицы.

1. Проверяем, имеет ли платежная матрица седловую точку.

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

 

Игроки	B1	B2	B3	B4	B5	a = min(Ai)
A1					-4	-4
A2			-3	-1		-3
A3
A4	-3	-3		-4		-4
A5
b = max(Bi)

Находим гарантированный выигрыш, определяемый нижней ценой игры a = max(a_i) = 4, которая указывает на максимальную чистую стратегию A₃.

Верхняя цена игры b = min(b_j) = 4.

Седловая точка (3, 2) указывает решение на пару альтернатив (A3,B2). Цена игры равна 4.

 

Задание 2.

Игроки	B1	B2	B3	B4	a = min(Ai)
A1
A2
b = max(Bi)					­

 

Находим гарантированный выигрыш, определяемый нижней ценой игры a = max(ai) = 2, которая указывает на максимальную чистую стратегию A2.

Верхняя цена игры b = min(bj) = 4.

Что свидетельствует об отсутствии седловой точки, так как a ≠ b, тогда цена игры находится в пределах 2 <= y <= 4. Находим решение игры в смешанных стратегиях. Объясняется это тем, что игроки не могут объявить противнику свои чистые стратегии: им следует скрывать свои действия. Игру можно решить, если позволить игрокам выбирать свои стратегии случайным образом (смешивать чистые стратегии).

С позиции проигрышей игрока В стратегия B3 доминирует над стратегией B2 (все элементы столбца 3 больше элементов столбца 2), следовательно исключаем 3-й столбец матрицы. Вероятность q3 = 0.

 

 

 

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

1. В декартовой системе координат по оси абсцисс откладывается отрезок, длина которого равна 1. Левый конец отрезка (точка х = 0) соответствует стратегии A₁, правый - стратегии A₂ (x = 1). Промежуточные точки х соответствуют вероятностям некоторых смешанных стратегий S₁ = (p₁,p₂).

2. На левой оси ординат откладываются выигрыши стратегии A₁. На линии, параллельной оси ординат, из точки 1 откладываются выигрыши стратегии A₂.
Решение игры (2 x n) проводим с позиции игрока A, придерживающегося максиминной стратегии. Доминирующихся и дублирующих стратегий ни у одного из игроков нет.

Максиминной оптимальной стратегии игрока A соответствует точка N, лежащая на пересечении прямых B₂B₂ и B₃B₃, для которых можно записать следующую систему уравнений:

y = 3 + (4 - 3)p₂

y = 10 + (2 - 10)p₂

Откуда:

p₁ = ²/₉

p₂ = ⁷/₉

Цена игры, y = 3⁷/₉;

 

 

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

 

3q₂+10q₃ = y

4q₂+2q₃ = y

q₂+q₃ = 1

 

или

 

3q₂+10q₃ = 3⁷/₉

4q₂+2q₃ = 3⁷/₉

q₂+q₃ = 1

 

Решая эту систему методом обратной матрицы, находим:

 

q₂ = ⁸/₉

q₃ = ¹/₉

 

Поскольку из исходной матрицы были удалены и столбцы, то найденные векторы вероятности можно записать в виде: P(²/₉,⁷/₉); Q(0,⁸/₉,0,¹/₉);

 

Задание 3

Решение:

В каждом столбце матрицы A найдем максимальный элемент. Эти элементы подчеркнуты в матрице A. Их положение соответствует приемлемым ситуациям 1-го игрока, когда второй игрок выбрал стратегию j соответственно.
Затем в каждой строке матрицы B выберем наибольший элемент. Эти элементы подчеркнуты в матрице B. Их положение будет определять приемлемые ситуации 2-го игрока, когда первый игрок выбрал стратегию i соответственно.

Платежная матрица игрока А:

 

 

Платежная матрица игрока B:

 

-3

 

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

В равновесной ситуации (1,2) игрок 1 выигрывает 4 единиц, а игрок 2 - 4 единицы.

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

 

Итак, чтобы в биматричной игре: А=(a), В = (b) пара (p,q); определяемая равновесную ситуацию, необходимо и достаточно одновременное выполнение следующих неравенств:

(p–1)(Cq-α) >= 0, p(Cq-α) >= 0; 0 >= p >= 1

(q-1)(Dp-β) >= 0, q(Dp-β) >= 0; 0 >= q >= 1,

где

C = a₁₁ - a₁₂ - a₂₁ + a₂₂

α = a₂₂- a₁₂

D = b₁₁-b₁₂-b₂₁+b₂₂

β = b₂₂-b₂₁

 

Проводя необходимые вычисления:

C = 1 - 4 - 5 + 2 = -6

α = 2 - 4 = -2

D = -3 - 4 - 8 + 2 = -13

β = 2 - 8 = -6

 

и рассуждения

(p–1)(-6q+2) >= 0

p(-6q+2) >= 0

(q-1)(-13p+6) >= 0

q(-13p+6) >= 0

 

получаем, что:

 

1) p=1,q >= ¹/_3, p=0, q <= ¹/_3, 0 <= p <= 1, q=¹/₃

2) q=1,p >= ⁶/_13, q=0, p <= ⁶/_13, 0 <= q <= 1, p=⁶/₁₃

 

Цена игры:

H_a(⁶/₁₃;¹/₃) = 3, H_b(⁶/₁₃;¹/₃) = 2¹²/₁₃

Ответ: P* = (⁶/₁₃;⁷/₁₃); Q* = (¹/₃;²/₃).

 

Выигрыш игроков в равновесной ситуации: f(P*,Q*) = (3;2¹²/₁₃).

 

ПРИЛОЖЕНИЕ 3

 

1. Найти наикратчайший путь из узла (1) в узел (16).

2. Найти остов графа.

 

1. Пусть дан граф G{M,N}, где M – множество вершин, N – множество дуг, и таблица длин пути (Таблица 1).

Таблица 1:

(1, 2)
(2, 3)
(3, 4)
(1, 5)
(2, 6)
(3, 7)
(4, 8)
(5, 6)
(6, 7)
(7, 8)
(5, 9)
(6,10)
(7,11)
(8,12)
(9, 10)
(10, 11)
(11, 12)
(9, 13)
(10,14)
(11,15)
(12,16)
(13,14)
(14,15)
(15,16)

 

 

 

Для поиска кратчайшего пути используют алгоритм Дейкстры:

1. Выбирается начальный узел. Ему присваивается метка 0. Вершинам, связанным с начальной присваиваются метки, равные длине пути. Остальным присваивается метка ∞.

2. Среди всех временных вершин выбирается та, которая имеет наименьшее временное значений и переводится в постоянное.

3. Во всех вершинах j, связанных с i происходит пересчет метки:

V_i*=min(V_j*, V_i+C_ij),

где C_ij – расстояние между i и j, V_i, V_j – значения меток i и j;

4. Пункт 2 повторяется до тех пор, пока существуют временные метки.

5. Используя алгоритм «обратного хода», находятся наикратчайшие пути.

 

 

 

Решение.

 

39*

∞*

∞*

24*

∞*

∞*

∞*

∞*

∞*

∞*

∞*

∞*

∞*

∞*

∞*

39*

∞*

∞*

24i

∞*j

∞*

∞*

∞*j

∞*

∞*

∞*

∞*

∞*

∞*

∞*

 

V6*=min(∞*, 24+34)= min(∞*, 58)=58;

V9*=min(∞*, 24+37)= min(∞*,61)=61;

39*

∞*

∞*

58*

∞*

∞*

61*

∞*

∞*

∞*

∞*

∞*

∞*

∞*

39i

∞*j

∞*

58*j

∞*

∞*

61*

∞*

∞*

∞*

∞*

∞*

∞*

∞*

 

V3*=min(∞*, 39+25)= min(∞*, 64)=64;

V6*=min(58*, 39+11)= min(58*,50)=50;

 

64*

∞*

50*

∞*

∞*

61*

∞*

∞*

∞*

∞*

∞*

∞*

∞*

64*

∞*

50i

∞*j

∞*

61*

∞*j

∞*

∞*

∞*

∞*

∞*

∞*

 

V7*=min(∞*, 50+48)= min(∞*, 98)=98;

V10*=min(∞*, 50+44)= min(∞*,94)=94;