85776 (Матричные антагонистические игры с нулевой суммой в чистых стратегиях), страница 9

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

Составим таблицу.

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

2.4 Математический аппарат теории игр и его применение к решению прикладных задач

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

Имеется m пунктов производства с объемами производства в единицу времени а_i, i= и n пунктов потребления b_i, i= , естественно, что потребление не должно превышать возможностей производства a_i b_i, затраты на перевозку единицы продукции из i-го пункта производства в j-й пункт потребления составляют С_ij, а количество перевезенного продукта x_ij.

Требуется составить такой план перевозок, при котором суммарные затраты на них были бы минимальны min C_ij x_ij при условиях, что в каждый пункт потребления завозится требуемое количество продукта x_ij b_j, j = , из каждого пункта производства вывозится не более произведенного количества продукта x_ij a_i, = и перевозимый объем продукта не может быть отрицательным x_ij 0, i = , j = .

Рассмотрим далее транспортную задачу в частной постановке.

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

Таблица 2.2

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

(1)

Требуется составить такой план перевозок, при котором их общая стоимость была бы наименьшей.

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

.

Но так как потребность в грузе в пункте равна , то должно выполняться равенство .

Аналогичные рассуждения приводят к равенствам

, .

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

.

Подобно этому .

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

Таблица 2.3

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

Таким образом, математическая формулировка транспортной задачи (по критерию стоимости перевозок) такова.

Задана система

(2)

пяти линейных алгебраических уравнений с шестью переменными и линейная целевая функция

(3)

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

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

(4)

вытекающего из самого условия задачи.

Впрочем, возможны и иные постановки транспортной задачи, когда условие (1а) не выполнено.

Задача о выборе производственной программы. Эта задача была одной из первых практических задач линейного программирования, решенная в 1939 году известным русским математиком Л.В.Канторовичем.

На m предприятиях нужно произвести n продуктов в заданном ассортименте l₁, l₂,..., l_n. Если x_ij, i = , j = – рабочее время i-го предприятия, отводимое под j-й продукт, а_ij – производительность i-го предприятия в единицу времени по выпуску j-го продукта, то задача о выборе производственной программы для случая, когда продукция дефицитна, производственные мощности ограничены и должны использоваться максимально полно, ставится следующим образом.

Требуется составить программу работы предприятий – указать время х_ij, отведенное на производство каждого вида продукции на данном предприятии таким образом, чтобы получить максимальный суммарный объем продукции в заданном ассортименте в единицу времени, т.е. необходимо найти x_ij из условий, что время не может быть отрицательным x_ij > 0, сумма всех временных долей не превосходит полного времени работы предприятия x_ij 1, количество ассортиментных наборов продуктов максимально.

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

Таблица 2.4

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

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