1.3 Задачи для самостоятельной работы

1. Найти решение задач целочисленного линейного программирования методом Гомори.

а) б)

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

Тип изделия	Необходимое времы (час./ед.)	Необходимое сырье (фунт/ед.)
1	3	4
2	4	3
3	5	6
Наличный Дневной объем	100	100

Доходы от производства единицы каждого из трех изделий равны 25, 30 и 45 долл. соответственно. Если будет производиться изделие типа 3, то его ежедневный объем производства должен быть не менее 5 единиц. Сформулируйте задачу в виде задачи целочисленного программирования, чтобы найти оптимальное решение.

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

Проект	Расход (млн. долл./год)			Прибыль (млн. долл)
	1-й год	2-й год	3-й год
1	5	1	8	20
2	4	7	10	40
3	3	9	2	20
4	7	4	1	15
5	8	6	10	30
Доступный капитал (млн. долл.)	25	25	25

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

4. Решить задачи методом ветвей и границ.

а) б)

в)

2. Теория игр

2.1. Основные положения теории игр

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

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

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

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

В экономической практике нередко приходится формализовать (моделировать) ситуации, придавая им игровую схему, в которых один из участников безразличен к результатам игры. Такие игры называют играми с природой, понимая под термином «природа» всю совокупность внешних обстоятельств, в которых сознательному игроку (его называют статистиком, а соответствующую игру – статистической) приходится принимать решение. Например, определение объема выпуска сезонной продукции в ожидании наиболее выгодного для ее реализации уровня спроса; формирование пакета ценных бумаг в расчете на высокие дивиденды и т.п. Здесь в качестве второго игрока выступает: в первом примере – уровень спроса; во втором – размер ожидаемой прибыли.

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

1) варианты действий игроков;

2) объем информации каждого игрока о поведении партнеров;

3) выигрыш, к которому приводит каждая совокупность действий.

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

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

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

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

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

Целью теории игр является определение оптимальной стратегии для каждого игрока.