Матричные антагонистические игры с нулевой суммой в чистых стратегиях (стр. 14 из 16)

(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.