МОДЕЛИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

Общий вид задачи оптимального распределения ресурсов

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

Пронумеруем все виды ресурсов числами от 1 до m, буквой i будем обозначать номер вида ресурса. Таким образом, i удовлетворяет неравенству 1 £ i £ m. Заметим, что ресурсы разных видов могут измеряться в различных единицах (тоннах, кубометрах, человеко-часах, рублях, штуках и др.).

В течение планового периода предприятие обладает некоторыми доступными объемами ресурса каждого вида. Объем ресурса i-го вида, измеренный в единицах соответствующих данному виду ресурса, обозначим посредством b_i. Индекс i около буквы b указывает, что доступные объемы ресурсов разных видов могут быть различными.

Из этих ресурсов предприятие способно изготавливать различную продукцию (в нашей ситуации – Печенье и Бисквиты). Обозначим буквой n общее число видов продукции, которые может выпустить предприятие из имеющихся ресурсов. Занумеруем все виды продукции числами от 1 до n. Буквой j будем обозначать номер вида продукции, так что выполняется неравенство 1 £ j £ n. Продукция, как и ресурсы, может измеряться в различных единицах.

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

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

  Построим математическую модель задачи. Сначала введем переменные. Посредством x_j обозначим искомый объем выпуска продукции j-го вида. Математическую модель можно теперь записать в следующей форме:

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

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

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

Всякий набор значений переменных (x₁, x₂, ... , x_n ) называется планом задачи. Те планы, которые удовлетворяют системе ограничений, называются допустимыми планами. Оптимальным планом называется тот из допустимых планов, который дает наибольшее значение целевой функции среди всех ее значений на допустимых планах. Само это наибольшее значение целевой функции, то есть значение целевой функции на оптимальном плане, называется оптимумом задачи.