Тема 4. игровые модели принятия решений

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

Таким образом, всякий конфликт можно представить в виде системы

,

где N = – множество игроков, – множество чистых стратегий игрока i, – выигрыш i-го игрока в ситуации , где .

Такая система называется игрой.

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

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

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

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

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

Антагонистическая игра, в которой каждый игрок имеет конечное множество стратегий, называется матричной игрой.

Это название объясняется следующей возможностью описания игр такого рода. Пусть 1-й и 2-й игроки располагают конечным множеством стратегий X = , соответственно. Составим прямоугольную таблицу, в которой строки соответствуют стратегиям первого игрока, столбцы – стратегиям второго, а клетки таблицы, стоящие на пересечении строк и столбцов, соответствуют ситуациям игры. Если в каждую клетку (i, j), соответствующую ситуации (x_i, у_j), , , поставить выигрыш первого игрока в данной ситуации H(x_i, у_j) = a_ij,то получим описание игры в виде некоторой матрицы А.

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

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

Число , равное нижнему выигрышу игрока 1 , называется нижним значением (нижней ценой) игры. Строка матрицы, соответствующая числу , называется максиминной стратегией игрока1.

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

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

В случае = одностороннее отклонение от минимаксной (максиминной) стратегии невыгодно.

Оптимальные стратегии будем обозначать через i^*, j^*. Пара оптимальных стратегий (i^*, j^*) составляет седловую точку функции выигрыша, то есть верно неравенство ,для любых , .

Значение игры n в чистых стратегиях есть выигрыш игрока 1 в седловой точке:

.

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

Пример 4.1.

Седловой точкой является пара (i_о = 3; j_о = 1), при которой n = 2.

Заметим, что хотя выигрыш в ситуации (3;3) также равен
2 = = , она не является седловой точкой, так как этот выигрыш не является максимальным среди выигрышей третьего столбца.

Свойства решений матричной игры:

Стратегия u¹ игрока 1 доминирует (строго доминирует) над стратегией u², если А (u¹, w) ³ А (u²,w)(А (u¹, w) > А (u²,w)), w Î W.

Стратегия w¹ игрока 2 доминирует (строго доминирует) над стратегией w², если А (u, w¹) £ А (u, w²) (А (u,w¹) < А (u,w²)), u Î U.

При этом стратегии u² и w² называются доминируемыми (строго доминируемыми).

Пример 4.2. Рассмотрим игру:

(Здесь стрелками указаны доминируемые стратегии).Получим игру 2×2, в которой все стратегии недоминируемые.

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

1/3

2/3

Здесь вторая строка доминируется выпуклой линейной комбинацией первой и третьей строк, так как

Следовательно, вторую стратегию можно исключить и рассматривать игру:

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

Решение 2 2–игры. В общем случае игра 2×2 определяется матрицей

.

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

Пусть U = (x,1 - x) – оптимальная стратегия игрока 1. Тогда

; .

Аналогично, если W = (h, 1 – h) – оптимальная стратегия игрока 2, то

.

Графоаналитический метод решения игр 2´n и m×2. Рассмотрим игру 2´n:

Задача игрока 1 состоит в максимизации функции .

Так как , мы имеем .

Таким образом, v является минимумом n линейных функций одной переменной ; можно вычертитьграфики этих функций и затем максимизировать их минимум g( ) графическими методами. Покажем на примере игры 2×3.

Пример 4.3.Рассмотрим игру, заданную матрицей.

На плоскости хОy введём систему координат и на оси Ох отложим отрезок единичной длины С₁С₂, каждой точке которого поставим в соответствие некоторую смешанную стратегию игрока 1 (u, 1- u). В частности, точке С₁(0; 0) отвечает стратегия С₁, точке С₂(1; 0) – стратегия С₂ и т.д.

В точках С₁ и С₂ восстановим перпендикуляр и на полученных прямых будем откладывать выигрыш игроков. На первом перпендикуляре (в данном случае он совпадает с осью Оy) отложим выигрыш игрока 1 при стратегии С₁, а на втором – при стратегии С₂. Если игрок 1 применит стратегию С₁, то выиграет при стратегии В₁ игрока 2 – 2, при стратегии В₂ – 3, а при стратегии В₃ – 11. Числам 2, 3, 11 на оси Ох соответствуют точки В₁, В₂ и В₃.

Если же игрок 1 применит стратегию С₂, то его выигрыш при стратегии В₁ равен 7, при В₂ – 5, а при В₃ – 2. Эти числа определяют точки В₁¢, В₂¢, В₃¢ на перпендикуляре, восстановленном в точке С₂. Соединяя между собой точки В₁ и В¢₁, В₂ и В¢₂, В₃ и В¢₃ получим три прямые, расстояние до которых от оси Ох определяет средний выигрыш при любом сочетании соответствующих стратегий.

P 02YFIuAU/sPwh8/oUDDT0V3IeNEqeE45yHK0AMF2msY8HFlP5gnIIpe3DxS/AAAA//8DAFBLAQIt ABQABgAIAAAAIQC2gziS/gAAAOEBAAATAAAAAAAAAAAAAAAAAAAAAABbQ29udGVudF9UeXBlc10u eG1sUEsBAi0AFAAGAAgAAAAhADj9If/WAAAAlAEAAAsAAAAAAAAAAAAAAAAALwEAAF9yZWxzLy5y ZWxzUEsBAi0AFAAGAAgAAAAhAMBg7t7wBwAAwFYAAA4AAAAAAAAAAAAAAAAALgIAAGRycy9lMm9E b2MueG1sUEsBAi0AFAAGAAgAAAAhADhKVm/fAAAACAEAAA8AAAAAAAAAAAAAAAAASgoAAGRycy9k b3ducmV2LnhtbFBLBQYAAAAABAAEAPMAAABWCwAAAAA= " o:allowincell="f">

B¢1

B¢2

B¢3

B3

B2

B1

х

2 2

y

Рис. 5.

Таким образом, ординаты точек, принадлежащих ломаной В₁MNВ¢₃, определяют минимальный выигрыш игрока 1 при применении им любых смешанных стратегий. Эта минимальная величина является максимальной в точке N; следовательно, этой точке соответствует оптимальная стратегия u* = (u, 1 - u), а её ордината равна цене игры v. Координаты точки N находим как точку пересечения прямых В₂B¢₂ и В₃B¢₃.

Соответствующие два уравнения имеют вид

.

Следовательно, u^*= при цене игры v= . Таким образом, мы можем найти оптимальную стратегию при помощи матрицы

.

Оптимальные стратегии для игрока 2 можно найти из системы

и, следовательно, w^*= . (Из рисунка видно, что стратегия B₁ не войдёт в оптимальную стратегию).

Укажем основные этапы нахождения решения игры 2n (m2):

1. Строим прямые, соответствующие стратегиям второго (первого) игрока.

2. Определяем нижнюю (верхнюю) огибающую графиков, соответствующих столбцам (строкам).

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

4. Определяем цену игры и оптимальные стратегии.

Задания для контрольной работы

Задание №1. Составить математическую модель задачи принятия решения.

Вариант 1.

Текстильный комбинат производит 2 вида ткани: вид А состоит из 80% шерсти и 20% синтетического волокна, вид В состоит из 20% шерсти и 80% синтетики.

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

Для производства ткани вида А ткацкий станок использует 4 ед. шерстяной пряжи и 1 ед. синтетических волокон. Для производства ткани вида В – 1 ед. синтетического волокна и 4 ед. шерстяного волокна. В сутки станок расходует 36 ед. синтетического волокна и 24 ед. шерстяного волокна.

Стоимость 1 рулона ткани вида А – $ 2000, ткани вида В – $ 1000.

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

Вариант 2.

Необходимо распределить площадь пашни между двумя культурами по следующим данным:

Культура	Урожайность (ц/га)	Затраты тракторо-смен на 1 га	Цена (руб. за 1 ц)	Затраты (человеко-дней на 1 га)
А		0,1
В		0,24

Кроме того, заданы ресурсы производства:

земли – не более 1800 га

затраты тракторосмен – не более 300

затраты труда человеко-дней – не более 8000

потребности в культуре А – 10 000 ц; В – 7 500 ц

Критерий оптимальности – максимальная прибыль от реализации.

Вариант 3.

Завод производит продукцию двух видов А и В, используя сырье, запас которого составляет 570 т. Согласно плану выпуск продукции А должен составлять не менее 60% от общего объема выпуска. Расход сырья на изготовление 1 т продукции А и В составляет соответственно 10 и 70 т. стоимость 1 т продукции А и В соответственно 3 и 8 тыс. руб.

Определить план выпуска продукции А и В, при котором стоимость выпуска продукции будет максимальной.

Вариант 4.

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

Вид заготовки	Количество заготовок (шт.) при раскрое по способу
I
II
III
Величина отходов (см3)

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

Вариант 5.

Хозяйству требуется приобрести два вида азотных удобрений: А – аммиачную селитру, В – сульфат аммония. Удобрения вида А необходимо иметь не более 15 т, а удобрения вида В не более 10 т.

Содержание действующего вещества для А и для В соответственно 35% и 25 %. Отпускная оптовая цена удобрения А –53 руб., В – 35 руб за тонну.

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

Вариант 6.

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

Питательные вещества	Корма	Дневная норма
I	II
А
В
С
ЦЕНА кормов

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

Вариант 7.

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

Ресурсы	Нормы затрат ресурсов на одно изделие	Общее кол-во ресурсов
стол	шкаф
Древесина (м3) I вида II вида	0,2 0,1	0,1 0,3
Трудоемкость (чел.-ч)	1,2	1,5	371,4
Прибыль от реализации одного изделия (руб.)

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

Вариант 8.

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

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

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

Вариант 9.

Завод производит продукцию двух видов А и В, используя сырье, запас которого составляет 700 т. Согласно плану выпуск продукции А должен составлять не менее 80% от общего объема выпуска. Расход сырья на изготовление 1 т продукции А и В составляет соответственно 5 и 7 т. стоимость 1 т продукции А и В соответственно 2 и 4 тыс. руб.

Определить план выпуска продукции А и В, при котором стоимость выпуска продукции будет максимальной.

Вариант 10.

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

Вид корма	Количество единиц корма, которое ежедневно должны получать	Общее кол-во корма
лисица	песец
I
II
III
Прибыль от реализации одной шкурки (руб.)

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

Вариант 11.

Фирма "Лесная пилорама" столкнулась с проблемой наиболее рационального использования ресурсов лесоматериалов, имеющихся в одном из принадлежащих этой фирме лесных массивов. В районе данного массива имеется лесопильный завод и фабрика, на которой изготовляется фанера. Таким образом, лесоматериалы можно использовать как для производства пиломатериалов, так и для изготовления фанеры.

Чтобы получить 2,5 м³ коммерчески реализуемых комплектов пиломатериалов, необходимо израсходовать 2,5 м³ еловых и 7,5 м³ пихтовых лесоматериалов. Для приготовления 100 м³ фанеры требуется 5 м³ еловых и 10 м³ пихтовых лесоматериалов. Лесной массив содержит 80 м³ еловых и 180 м³ пихтовых лесоматериалов.

Согласно условиям поставок, в течение планируемого периода необходимо произвести, по крайней мере, 10 м³ пиломатериалов и 1200 м³ фанеры. Доход с 1 м³ пиломатериалов составляет 16 долл., а со 100 м³ фанеры – 60 долл.

Вариант 12.

Фирме «Иерихонская сталь» предстоит решить, какое количество x₁ чистой стали и какое количество х₂ металлолома следует использовать для приготовления (из соответствующею сплава) литья для одного, из своих заказчиков. Пусть производственные затраты в расчете на 1 т чистой стали равняются 3 усл. ед., а затраты на 1 т металлолома – 5 усл. ед. (последняя цифра больше предыдущей, так как использование металлолома сопряжено с его предварительной очисткой). Заказ предусматривает поставку не менее 5т литья; при этом заказчик готов купить и большее количество литья, если фирма «Иерихонская сталь» поставит перед ним такие условия.

Предположим, что запасы чистой стали ограничены и не превышают 4 т, a запасы металлолома не превышают 6 т. Отношение веса металлолома к весу чистой стали в процессе получения сплава не должно превышать 7 : 8. Производственно-технологические, условия таковы, что на процессы плавки и литья не может быть отведено более 18 ч; при этом на 1 т стали уходит 3 ч, а на 1 т металлолома – 1 ч производственного времени.

Вариант 13.

Фирмой «Супертранзистор» выпускаются радиоприемники трех различных моделей: модель А, модель В и модель С. Каждое изделие указанных моделей приносит доход в размере 8, 15 и 25 соответственно. Необходимо, чтобы фирма выпускала за неделю не менее 100 приемников модели А, 150 моделей приемников модели В и 75 приемников модели С.

Каждая модель характеризуется определенным временем, необходимым для изготовления соответствующих деталей, сборки изделия и его упаковки. Так, в частности, в расчете на 10 приемников модели А требуется 3 ч для изготовления соответствующих деталей, 4 ч на сборку и 1 ч на упаковку. Соответствующие показатели в расчете на 10 приемников модели В равняются 3.5, 5 и 1.5ч, а на 10 приемников модели С – 5, 8 и 3. В течение ближайшей недели фирма может израсходовать на производство радиодеталей 150 ч, на сборку 200 ч и на упаковку 60 ч.

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

Вариант 14.

Авиакомпания «Небесный грузовик», обслуживающая периферийные районы страны, располагает 8 самолетами типа 1, 15 самолетами типа 2, 12 самолетами типа 3, которые она может использовать для выполнения рейсов в течение ближайших суток. Грузоподъемность (в тысячах тонн) известна: 45 для самолетов типа 1, 7 для самолетов типа 2, 4 для самолетов типа 3.

Авиакомпания обслуживает города А и В. Городу А требуется тоннаж в 20000 т, а городу В – в 30000 т. Избыточный тоннаж не оплачивается. Каждый самолет в течение дня может выполнить только один рейс.

Расходы, связанные с перелетом самолетов по маршруту «Центральный аэродром – пункт назначения», указаны в приведенной ниже таблице:

	тип 1	тип 2	тип 3
город А			1,4
город В			3,8

Обозначим через x_i (i = 1, 2, 3) число самолетов i-го Типа, отправленных в город А, а через y_j (j = 1, 2, 3) число самолетов j-го типа, отправленных в город В. Построить модель оптимальных перевозок.

Вариант 15.

Авиакомпании «Ночной полет» необходимо решить, какое количество топлива для реактивных самолетов следует закупить у фирм поставщиков, если число последних равно трем и имеют место следующие требования и ограничения:

Заправка самолетов производится регулярно в четырех аэропортах.

Нефтяные компании констатируют следующие возможности поставки топлива в течение ближайшего месяца: а) 2500000 л – нефтяная компания 1; б) 5000000 л – нефтяная компания 2; в) 6000000 л – нефтяная компания 3.

Авиакомпании требуется следующее количество топлива: а) 1000000 л в аэропорту 1; б) 2000000 л в аэропорту 2; в) 3000000 л в аэропорту 3; г) 4000000 л в аэропорту 4.

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

	компания 1	компания 2	компания 3
Аэропорт 1
Аэропорт 2
Аэропорт 3
Аэропорт 4

Построить модель оптимизации управляющего решения.

Вариант 16.

Фирма «Нитроткань» производит определенного типа мелкие детали для промышленных изделий и продает их через своих посредников-оптовиков по фиксированной поставочной цене 2,50 долл. за штуку. Число посредников-оптовиков равняется пяти. Коммерческие прогнозы указывают на то, что объем месячных поставок, составит: посреднику 1 – 3000 штук, посреднику 2 – 3000 штук, посреднику 3 – 10 000 штук, посреднику 4 – 5000 штук, посреднику 5 – 4000 штук.

Фирма располагает следующими производственными мощностями: завод 1 – 5000 деталей в месяц, завод 2 – 10000 деталей в месяц, завод 3 – 12500 деталей в месяц. Себестоимость одной детали, изготовленной на заводе 1, равняется 1 долл., на заводе 2 – 0,90 долл., на заводе 3 – 0,80 долл.

Транспортные расходы (в долларах), связанные с доставкой одной детали в точки оптовой продажи, приведены ниже:

	Компания 1	Компания 2	Компания 3	Компания 4	Компания 5
Завод 1	0,05	0,07	0,10	0,15	0,15
Завод 2	0,08	0,06	0,09	0,12	0,14
Завод 3	0,10	0,09	0,08	0,10	0,15

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

Вариант 17.

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

	Кварталы кварталы
холодильники
газовые плиты
кухонные раковины

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

В течение квартала фирма может израсходовать не более 8000 «приведенных часов» (п. ч.) рабочего времени. На изготовление холодильника требуется 0,5 п. ч., газовой плиты – 2 п. ч., а кухонной раковины – 1,5 п. ч. В четвертом квартале холодильники не могут изготовляться, так как фирма планирует произвести в это время частичное переоборудование предприятия в связи с введением в действие новой конвейерной линии.

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

Вариант 18.

Фирма «Всякая всячина», выпускающая лезвия для бритв, объявила о переходе к производству совершенно новых лезвий улучшенного качества. Реакция потребителей на проведенную фирмой рекламную кампанию оказалась вполне удовлетворительной. Фирма имеет два предприятия и три оптовых склада, размещенных в различных географических пунктах. Лезвия на склады доставляются по железной дороге партиями. Выпуск лезвий в течение одного месяца на предприятиях 1 и 2 составляет S₁ = 100 и S₂ = 200 соответственно. Возможности сбыта на складах 1, 2 и 3 в течение этого месяца равны соответственно D₁=150, D₂=200 и D₃ = 250. Как видно, возможный сбыт, т.е. спрос, значительно превышает поставки, вследствие чего часть потребностей останется неудовлетворенной.

Предположим, что транспортные расходы на доставку одного вагона лезвий с предприятия i на склад j равны tij и что доход от сбыта этого вагона на складе j равен рj. (Фирма может продавать свои лезвия по различным ценам в различных пунктах страны).

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

Вариант 19.

Задача о доставке грузов (задача о покрытии). Фирма «Автопегас» должна доставить грузы пяти своим клиентам в течение рассматриваемого дня. Клиенту А нужно доставить груз весом в 1 единицу, клиенту В – в 2 единицы, клиенту С – в 3 единицы, клиенту D – в 5 единиц и клиенту Е – в 8 единиц. Фирма располагает четырьмя автомашинами следующей грузоподъемности: машина 1 – 2 единицы, машина 2 – 6 единиц, машина 3 – 8 единиц, машина 4 – 8 единиц. Стоимость эксплуатации автомашины j составляет cj. Предположим, что одна машина не может доставлять груз обоим клиентам А и С, аналогично одна машина не может использоваться для доставки груза обоим клиентам B и D.

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

Вариант 20.

Текстильный комбинат производит 2 вида ткани: вид А состоит из 70% шерсти и 30% синтетического волокна, вид В состоит из 10% шерсти и 90% синтетики.

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

Для производства ткани вида А ткацкий станок использует 3 ед. шерстяной пряжи и 1 ед. синтетических волокон. Для производства ткани вида В – 1 ед. синтетического волокна и 4 ед. шерстяного волокна. В сутки станок расходует 36 ед. синтетического волокна и 24 ед. шерстяного волокна. Стоимость 1 рулона ткани вида А – $ 2200, ткани вида В – $ 1500.

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

Вариант 21.

Необходимо распределить площадь пашни между двумя культурами по следующим данным:

Культура	Урожайность (ц/га)	Затраты тракторо-смен на 1 га	Цена (руб. за 1 ц)	Затраты (человеко-дней на 1 га)
А		0,15		3,5
В		0,25

Кроме того, заданы ресурсы производства:

земли – не более 1750 га

затраты тракторосмен – не более 300

затраты труда человеко-дней – не более 8500

потребности в культуре А – 10 000 ц; В – 7500 ц

Критерий оптимальности – максимальная прибыль от реализации.

Вариант 22.

Завод производит продукцию двух видов А и В, используя сырье, запас которого составляет 570 т. Согласно плану выпуск продукции А должен составлять не менее 65% от общего объема выпуска. Расход сырья на изготовление 1 т продукции А и В составляет соответственно 12 и 75 т. стоимость 1 т продукции А и В соответственно 13 и 9 тыс. руб.

Определить план выпуска продукции А и В, при котором стоимость выпуска продукции будет максимальной.

Вариант 23.

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

Вид заготовки	Количество заготовок (шт.) при раскрое по способу
I
II
III
Величина отходов (см3)

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

Вариант 24.

Хозяйству требуется приобрести два вида азотных удобрений: А – аммиачную селитру, В – сульфат аммония. Удобрения вида А необходимо иметь не более 150 т, а удобрения вида В не более 100 т.

Содержание действующего вещества для А и для В соответственно 45% и 35 %. Отпускная оптовая цена удобрения А – 530 руб., В – 305 руб за тонну.

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

Вариант 25.

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

Питательные вещества	Корма	Дневная норма
I	II
А