Примеры моделей линейного программирования

3.2.1. Задача оптимального распределения ресурсов при планировании выпуска продукции на предприятии (задача об ассортименте)[12].

Предположим, что предприятие выпускает n различных изделий. Для их производства требуются m различных видов ресурсов (сырья, вспомогательных материалов, рабочего и машинного времени). Эти ресурсы ограничены и составляют в планируемый период b₁, b₂, ¼, b_m условных единиц. Известны также технологические коэффициенты a_ij, которые указывают, сколько единиц i-го ресурса требуется для производства изделия j-го вида ( ; ). Пусть прибыль, получаемая предприятием при реализации единицы изделия j-го вида, равна c_j. В планируемый период все показатели a_ij, b_i, c_j предполагаются постоянными.

Требуется составить такой план выпуска продукции, при реализации которого прибыль предприятия была бы наибольшей. Другими словами требуется составить оптимальный план работы предприятия `Х = (x₁, x₂, …, х_n), т.е. найти такие значения переменных x₁, x₂, …, х_n (объем выпуска продукции каждого вида), чтобы обеспечить предприятию получение максимальной прибыли от реализации всей продукции и чтобы на ее производство хватило имеющихся в распоряжении ресурсов.

Экономико-математическая модель задачи

,

;

.

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

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

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

В этом случае свобода выбора значительно снижается.

3.2.2. Задача о смесях (рационе, диете)[13]

К группе задач о смесях относят задачи по отысканию наиболее дешевого набора из определенных исходных материалов, обеспечивающих получение смеси с заданными свойствами. Получаемые смеси должны иметь в своем составе n различных компонентов в определенных количествах, а сами компоненты являются составными частями m исходных материалов.

Введем следующие обозначения: x_j – количество материала j-го вида, входящего в смесь; c_j – цена материала j-го вида; b_i – минимально необходимое содержание i-го компонента в смеси. Коэффициенты a_ij показывают удельный вес j-го компонента в единице j-го материала.

Экономико-математическая модель задачи

,

;

.

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

3.2.3. Транспортная задача[14]

Пусть некоторый однородный продукт, сосредоточенный у m поставщиков А_i в количестве a_i единиц ( ), необходимо доставить n потребителям В_j в количестве b_j единиц ( ). Известна стоимость с_ij перевозки единицы груза от поставщика А_i к потребителю В_j.

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

Обозначим через x_ij количество единиц груза, запланированных к перевозке от i-го поставщика к j-му потребителю. Так как от поставщика А_i к потребителю В_j запланировано перевести x_ij единиц груза, то стоимость перевозки составит с_ij x_ij.

Экономико-математическая модель задачи

,

,

,

.

Целевая функция представляет собой стоимость всего плана перевозок. Первое функциональное ограничение отражает требование, что все грузы должны быть перевезены, второе – все потребности должны быть удовлетворены.

Транспортная задача имеет n + m уравнений с неизвестными. Матрица перевозок X = (x_ij)_mn , удовлетворяющая всем ограничениям, называется планом перевозок транспортной задачи, а x_ij – перевозками.

План Х^*, при котором целевая функция обращается в минимум, называется оптимальным планом перевозок.