.МОДЕЛИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
Построение математической модели
Построим математическую модель задачи. Составление модели начинается с введения переменных. Переменные являются элементами языка, на котором будет сформирован производственный план. Такой план в данном случае - это пара величин, соответствующих объемам производства (количеству килограммов) продукции одного и другого вида. Обозначим посредством x1 - объем производства Печенья, посредством x2 - объем производства Бисквитов. Следует найти наилучший (оптимальный) производственный план.
Переменные, которые мы ввели, позволяют выразить ограниченность ресурсов в математической форме. Данные в Табл. 1.1 , Табл. 1.2 , Табл. 1.3 показывают расход ресурсов на изготовление продукции и доступные объемы ресурсов. Каждая строка является основной для формирования неравенства по своему виду ресурса.
.
Это неравенство выражает, что суммарные расходы муки на Печенье в количестве x1 кг и на Бисквиты в количестве x2 кг (левая часть неравенства) не должны превосходить доступных запасов Муки (правая часть неравенства). Аналогичные неравенства можно написать для Масла, Яйца и Сахара:
,
,
.
Трудовые ресурсы содержательно отличаются от сырья, но в математической модели они выступают на тех же основаниях. Ограниченность этих ресурсов (пока без учета возможных сверхурочных работ) выражается неравенством:
.
Ограниченность производственных мощностей может быть выражена в форме неравенств:
,
.
Ограниченность спроса характеризуется неравенствами
Кроме того, объем произведенной продукции не может быть отрицательной величиной, то есть
Таким образом, в целом мы получаем систему неравенств, характеризующих в математической форме условия составления плана производства продукции.
Такая система неравенств носит
название системы
ограничений задачи. Любая пара
значений переменных, то есть вектор (x1, x2),
называется планом задачи. Те пары значений,
которые удовлетворяют всем неравенствам
системы, то есть те планы, которые
удовлетворяют системе ограничений,
называются допустимыми
планами.
Сосредоточим внимание на допустимых планах. Каждому из них соответствует свой размер выручки. Например, для плана (500; 1000) выручка составит:
z = 32 ´ 500 + 27 ´ 1000 = 43000 (руб.)
В общем случае формулу для определения выручки z можно представить в следующем виде:
z = 32x1 + 27x2.
Мы хотим определить тот из допустимых планов, для которого выручка является максимальной. Выражение для выручки представляет собой математическую запись нашей цели при решении задачи. Такое выражение называется целевой функцией задачи. Мы хотим найти наибольшее значение целевой функции на множестве допустимых планов задачи.
Математическая запись цели и условий (ограничений) задачи выглядит теперь следующим образом.
Такая запись носит название математической модели задачи. Она представляет собой соединение целевой функции (с указанием отыскиваемого вида экстремума) и системы ограничений.
Построение математической модели приносит двоякую пользу. Во-первых, оно позволяет сформулировать задачу в ясной, отчетливой форме. Такая форма дает возможность быстро распознать допустимые и недопустимые планы, рассчитать соответствующую выручку. Во-вторых, построение модели позволяет превратить содержательную экономическую задачу (в нашем примере - задачу о составлении производственного плана) в чисто математическую задачу о поиске максимального значения функции при условии, что переменные подчинены определенной системе ограничений. При решении этой математической задачи можно не знать ничего о смысле входящих в нее переменных и выражений, забыть, что речь идет о продуктах питания, ресурсах и выручке. Это позволяет использовать при ее решении универсальные математические методы, привлечь для решения вычислительную технику и программные средства.
