Матричные антагонистические игры с нулевой суммой в чистых стратегиях
В чем состоит цель, для достижения которой из всех допустимых значений переменных нужно выбрать те, которые будут соответствовать оптимальному (наилучшему) решению задачи?
Отвечая на поставленные вопросы, сформулируем суть проблемы. Фирме требуется определить объемы производства (в тоннах) каждой из красок, который максимизирует доход (в тысячах долларов) от реализации продукции, с учетом ограничений на спрос и расход исходных продуктов.
Введем переменные: так как нужно определить объемы производства каждого вида краски, то переменными в модели являются
xE - суточный объем производства краски Е (в тоннах)
xI - суточный объем производства краски I (в тоннах).
Так как стоимость 1 т краски Е равна 3 тыс. долл., суточный доход от ее продажи составит 3 xE тыс. долл. Аналогично доход от реализации xI тонн краски I составит 2 xI тыс. долл. в сутки. При допущении независимости объемов сбыта каждой из красок можно дать следующую математическую формулировку целевой функции: определить (допустимые) значения xЕ и xI, максимизирующие величину общего дохода Ограничения: При решении рассматриваемой задачи должны быть учтены ограничения на расход исходных продуктов и спрос на изготовляемые краски. Ограничение на расход исходных продуктов можно записать следующим образом:
Это
приводит к
следующим двум
ограничениям:
(для А)
(для В) Ограничения
на величину
спроса красок
имеют вид
Эти
ограничения
имеют вид:
(соотношение
величин спроса
на краску I и
краску Е),
(максимальная
величина спроса
на краску I).
Переменные
xI и xE не могут
принимать
отрицательных
значений:
(объем производства
краски I),
(объем производства
краски Е). Итак,
математическую
модель можно
записать следующим
образом. Определить
суточные объемы
производства
(xI и xE ) краски I и
краски Е (в тоннах),
при которых
достигается
(целевая функция)
при ограничениях:
Что определяет линейный характер построенной модели? С формальных позиций данная модель является линейной потому, что все входящие в нее функции (ограничения и целевая функция) линейны. Линейность предполагает наличие двух свойств - пропорциональности и аддитивности.
Пропорциональность означает, что вклад каждой переменной хЕ и хI в целевую функцию прямо пропорционален этим переменным.
Аддитивность заключается в том, что целевая функция представляет собой сумму вкладов от различных переменных. Однако если фирма производит два конкурирующих вида продукции, увеличение сбыта одного из которых отрицательно сказывается на объеме реализации другого, то такая модель не обладает свойством аддитивности.
Задача о пищевом рационе.
Пусть
имеется 4 вида
продуктов:
.
Стоимость
единицы каждого
продукта
.
Согласно этим
условиям, требуется
составить
пищевой рацион,
в котором должны
содержаться
белки, в количестве
не менее
единиц, углеводов
– не менее
единиц, жиров
– не менее
единиц.
Составим таблицу.
-
продукт элементы продукт элементы Белки углеводы Жиры Белки углеводы Жиры 















(
)
– какие то
определённые
числа. Первый
индекс указывает
номер продукта,
второй – номер
элемента (белки,
жиры углеводы).
Требуется
составить
пищевой рацион
таким образом,
чтобы условия
по белкам, жирам
и углеводам
были выполнены.
Математическая
модель будет
выглядеть
следующим
образом:
- количества
продукции
входящих в
рацион. Показатель
эффективности
L – стоимость
рациона (эту
величину требуется
минимизировать).
Запишем линейную
зависимость
.
Учитывая, что
в одной единице
продукта
содержится
единиц белка,
в
единицах -
![]()
единиц белка,
в
единицах продукта
содержится
![]()
единиц белка
и т.д. получим
три неравенства:
эти линейные
неравенства
представляют
собой ограничения,
накладываемые
на элементы
решения
.
Таким образом
задача сводится
к следующей:
найти такие
неотрицательные
значения переменных
,
чтобы они
удовлетворяли
ограничениям
– неравенствам
и одновременно
обращали в
минимум линейную
функцию этих
переменных:
![]()
2.4 Математический аппарат теории игр и его применение к решению прикладных задач
Транспортная задача. Подобная задача возникает в своем простейшем варианте, когда речь идет о рациональной перевозке некоторого однородного продукта от производителей к потребителю. Поэтому здесь естественно возникает задача о наиболее рациональном прикреплении транспорта, правильном направлении перевозок груза, при котором полностью удовлетворяются потребности при минимальных затратах на транспортировку. Итак, задача формулируется следующим образом.
Имеется
m пунктов
производства
с объемами
производства
в единицу времени
аi, i=
и n пунктов
потребления
bi,
i=
,
естественно,
что потребление
не должно превышать
возможностей
производства
ai
bi,
затраты на
перевозку
единицы продукции
из i-го
пункта производства
в j-й пункт
потребления
составляют
Сij,
а количество
перевезенного
продукта xij.
Требуется
составить такой
план перевозок,
при котором
суммарные
затраты на них
были бы минимальны
min
![]()
Cij
xij при
условиях, что
в каждый пункт
потребления
завозится
требуемое
количество
продукта
xij
bj, j =
,
из каждого
пункта производства
вывозится не
более произведенного
количества
продукта
xij
ai, =
и перевозимый
объем продукта
не может быть
отрицательным
xij
0, i =
,
j =
.
Рассмотрим далее транспортную задачу в частной постановке.
На двух станциях
отправления
и
сосредоточено
соответственно
и
единиц некоторого
однородного
груза. Этот
груз следует
доставить в
три пункта
назначения
,
,
,
причём в каждый
из них должно
быть завезено
соответственно
,
,
единиц этого
груза. Стоимость
перевозки
единицы груза
из пункта
в пункт
(равную
),
считаем заданной.
Все данные
полезно представить
в виде таблицы
2.2.
Таблица 2.2
|
Пункты назначения Пункты отправления |
Пункты назначения | Запасы груза | ||
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
| Потребность в грузе |
|
|
|
|
Естественно считать, что общий запас грузов на станциях отправления равен суммарной потребности в этом грузе всех станций назначения. Следовательно
(1)
Требуется составить такой план перевозок, при котором их общая стоимость была бы наименьшей.
Обозначим
через
количество
единиц груза,
предназначенного
к отправке из
пункта
в пункт
.
Тогда количество
груза, который
планируется
к доставке в
пункт
из пунктов
и
составит
.
Но так как
потребность
в грузе в пункте
равна
,
то должно выполняться
равенство
.
Аналогичные рассуждения приводят к равенствам
,
.
С другой
стороны, общее
количество
груза, отправленного
со станции
,
выражается
суммой
,
которая, очевидно,
обязана совпадать
с запасом груза
,
сосредоточенным
на этой станции,
т.е.
.
Подобно этому
.
Полученные
соотношения
легче запомнить,
если все величины
свести в таблицу
2 (матрицу перевозок).
Тогда легко
проверить, что
сумма всех
,
расположенных
в
-ой
строке, равна
запасу
в пункте назначения
.
Сумма же всех
из столбца
равна потребности
пункта назначения
.
Таблица 2.3
|
Пункты назначения Пункты отправления |
Пункты назначения | Запасы груза | ||
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
| Потребности |
|
|
|
|
Из условий
задачи с очевидностью
вытекает, что
общая стоимость
всех перевозок
![]()
Таким образом, математическая формулировка транспортной задачи (по критерию стоимости перевозок) такова.
Задана система
(2)
пяти линейных алгебраических уравнений с шестью переменными и линейная целевая функция
(3)
Требуется
среди всех
неотрицательных
решений
системы (2) выбрать
такое, при котором
целевая функция
минимизируется
(достигает
наименьшего
значения).
Необходимо отметить, что при решении транспортной задачи следует учитывать важное соотношение
(4)
вытекающего из самого условия задачи.
Впрочем, возможны и иные постановки транспортной задачи, когда условие (1а) не выполнено.
Задача о выборе производственной программы. Эта задача была одной из первых практических задач линейного программирования, решенная в 1939 году известным русским математиком Л.В.Канторовичем.
На
m предприятиях
нужно произвести
n продуктов
в заданном
ассортименте
l1, l2,..., ln.
Если xij,
i =
,
j =
– рабочее время
i-го предприятия,
отводимое под
j-й продукт,
аij – производительность
i-го предприятия
в единицу времени
по выпуску j-го
продукта, то
задача о выборе
производственной
программы для
случая, когда
продукция
дефицитна,
производственные
мощности ограничены
и должны использоваться
максимально
полно, ставится
следующим
образом.
Требуется
составить
программу
работы предприятий
– указать время
хij,
отведенное
на производство
каждого вида
продукции на
данном предприятии
таким образом,
чтобы получить
максимальный
суммарный объем
продукции в
заданном ассортименте
в единицу времени,
т.е. необходимо
найти xij
из условий, что
время не может
быть отрицательным
xij
> 0, сумма всех
временных долей
не превосходит
полного времени
работы предприятия
xij
1, количество
ассортиментных
наборов продуктов
максимально.
Задача
об использовании
сырья. Предположим,
что изготовление
продукции двух
видов
и
требует использования
четырех видов
сырья
,
,
,
.
Запасы сырья
каждого вида
ограничены
и составляют
соответственно
,
,
,
условных единиц.
Количество
единиц сырья,
необходимое
для изготовления
единицы каждого
из видов продукции,
известно и
задаётся таблицей
2.4.
Таблица 2.4
| Виды сырья | Запасы сырья | Виды продукции | |
|
|
|
||
|
|
|
|
|
| Доход |
| ||