Задача о выборе оптимальных технологий

Типовой расчет

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

Задача №1. Построение математических моделей задач линейного программирования

Задача о выборе оптимальных технологий

Продукция в цехе может производиться n различными способами T_j (n =3). Для производства продукции могут использоваться ресурсы: рабочая сила, сырьё (сталь, древесина, цветные металлы), электроэнергия. Обозначения:

x _j – время использования технологического способа T_j при производстве продукции (j =1,2,3);

b _i – объем ресурса R _i (i =1,2,3);

a _ij – расход ресурса R_i за единицу времени по технологии T_j;

A – годовое плановое задание по выработке продукции (ден. ед.);

c_j – производительность технологии T_j (в денежных единицах за единицу времени работы по данной технологии);

l _j – затраты на изготовление продукции в единицу времени по технологии T_j (денежных единицах).

Налагаются ограничения по объемам b _i ресурсов (вида £) и по плановому выпуску A продукции (вида ³).

Возможны три критерия f ₁, f ₂, f ₃ оптимальности плана X =(x ₁,…, x_n) применения каждого технологического способа:

а) f ₁ – наибольший объем выпускаемой продукции по всем технологиям (ден. ед.);

б) f ₂ – наименьшие затраты на выполнение планового задания (ден. ед.);

в) f ₃ – наибольшая конечная прибыль от выпуска продукции с учетом затрат на изготовление продукции (ден. ед.).

В табл. 1 представлены объемы b i ресурсов R i, их расход a_ij в единицу времени для каждой технологии, плановое задание A, производительности c j технологий T _j и затраты l _j.

Задание

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

2. Дать математические постановки задач.

3. Привести полученные три математические модели к каноническому виду. Указать экономический смысл дополнительных (балансовых) переменных.

Таблица 1.

Решение

а) Пусть требуется реализовать первый критерий f ₁ оптимальности плана X =(x ₁,…, x_n), т.е. объем выпускаемой продукции по всем технологиям должен быть наибольшими. Поскольку x ₁, x ₂, x ₃ время использования технологического способа T ₁, T ₂, T ₃, соответственно, то объем использования каждого ресурса в соответствии с таблицей будет равен:

При этом потребление каждого ресурса не должно превышать их объемов, т.е. 350, 850, 720, соответственно. Таким образом, связь между потреблением ресурсов и их объемами выражается следующей системой неравенств:

(1)

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

(2)

Добавляя сюда условия неотрицательности

(3)

можно дать формулировку математической модели задачи:

Требуется найти такой план использования технологических способов X =(x₁, x₂, x₃), удовлетворяющий системе (1) и условиям (3), при которых целевая функция (2) принимает максимальное значение.

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

(4)

Новые переменные имеют следующий смысл: x ₄ – количество неиспользуемой рабочей силы, x ₅ – количество неиспользуемого сырья, x ₆ – количество неиспользуемой электроэнергии.

б) Пусть требуется реализовать второй критерий f ₂ оптимальности плана X =(x ₁,…, x_n), т.е. затраты на выполнение планового задания должны быть наименьшими. В отличие от выше рассмотренной задачи, здесь добавляется дополнительное условие, т.е. кроме ограничений по объемам ресурсов налагаются условия по плановому выпуску продукции. Учитывая производительность каждого технологического способа и годовое плановое задание по выработке продукции, по данным табл. 1 получим ограничение . Таким образом, система ограничений будет иметь вид

(5)

(6)

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

(7)

Дадим теперь формулировку математической модели задачи:

Требуется найти такой план использования технологических способов X =(x₁, x₂, x₃), удовлетворяющий системе (5) и условиям (6), при которых целевая функция (7) принимает минимальное значение.

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

(8)

Новые переменные имеют следующий смысл: x ₄ – количество неиспользуемой рабочей силы, x ₅ – количество неиспользуемого сырья, x ₆ – количество неиспользуемой электроэнергии, x ₇ – количество продукции, выработанной сверх плана.

в) Пусть требуется реализовать третий критерий f ₃ оптимальности плана X =(x ₁,…, x_n), т.е. конечная прибыль от выпуска продукции с учетом затрат на изготовление продукции должна быть наибольшей. В отличие от случая а), целевая функция будет иметь вид

,

или, учитывая данные таблицы,

. (9)

Тогда математическая модель задачиформулируется следующим образом:

Требуется найти такой план использования технологических способов X =(x₁, x₂, x₃), удовлетворяющий системе (1) и условиям (3), при которых целевая функция (9) принимает максимальное значение.

В каноническом виде задача формулируется следующим образом: найти максимум целевой функции (9) при ограничениях

(10)

Новые переменные имеют следующий смысл: x ₄ – количество неиспользуемой рабочей силы, x ₅ – количество неиспользуемого сырья, x ₆ – количество неиспользуемой электроэнергии.

Задача №2. Графическое решение задачи линейного программирования