16. Злп: задача планирования производства

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

1.на производство всех видов продукции используется m видов ресурсов, причем запасы каждого из них ограничены, и пусть b_i(i=1,2,…,m) – это количество ресурса i-го вида, которое имеется в наличии;

2.известна величина a_ij – количество i-го ресурса (i=1,2,…,m), которое затрачивается на производство одной единицы j-го продукта (j=1,2,…,n);

3.известна стоимость c_j (j=1,2,…,n) реализации одной единицы j-го продукта.

Требуется составить оптимальный план производства продукции, то есть такой план, который максимизирует суммарную прибыль от реализации всей произведенной продукции и при этом не происходит перерасхода ресурсов. ^ Строим экономико-математическую модель задачи. 1.Выбираем управляемые переменные, то есть такие переменные, на которые вы можете воздействовать и значения которых собираетесь искать в вашей задаче. Имеющиеся данные, на значения которых вы не можете влиять, называются константами или параметрами.

Введем переменную x_j (j=1,2,…n) – количество выпускаемой продукции j-го вида. 2.Построим функцию цели, отражающую эффективность решения задачи. Ее значения зависят от значений управляющих переменных, и она дает возможность сравнивать варианты решений по эффективности.

В нашем случае такой функцией является суммарная прибыль .  (1) Мы будем максимизировать функцию цели. 3.Введем ограничения на управляемые переменные – количество ресурсов каждого вида ограничено величиной b_i (i=1,2,…,m).

 (2) К системе (2) также должны быть добавлены естественные ограничения на неотрицательность компонентов плана производства:  x_j  0, j=1,2,…,n (3) ^ Решить задачу – значит найти такой вектор ,который будет удовлетворять всем ограничениям (2), (3) и максимизировать функцию цели.   Легко заметить, что функция - линейная, так как все переменные используются в ней только в первой степени. Ограничения (2) представляют собой систему линейных неравенств, (3) – также линейное неравенство. Такую задачу называютзадачей линейного программирования (ЗЛП). Несмотря на явную условность рассматриваемой ситуации и кажущуюся простоту задачи (1)-(3), ее решение является далеко не тривиальным и во многом стало практически возможным только после разработки специального математического аппарата. Существенным достоинством используемых здесь методов решения является их универсальность, поскольку к модели (1)-(3) могут быть сведены очень многие как экономические, так и неэкономические проблемы.

17.Злп: задача о диете

Имеется n видов продуктов питания и m химических элементов, необходимых для суточного потребления. a_ij – содержание i-го (i=1,2,…,m) химического элемента в одной единице j-го (j=1,2,…,n) продукта питания. b_i – минимальное суточное потребление i-го химического элемента. c_j – стоимость одной единицы j-го продукта питания. Требуется составить суточный рацион питания – сколько продуктов каждого вида нужно приобрести, чтобы рацион имел минимальную стоимость, и питание было разнообразным. В задаче о диете стоимость можно заменить на калорийность продуктов питания, и сформулировать задачу в следующем виде: питание должно быть низкокалорийным, но содержать все необходимые для суточного потребления химические элементы. ^ Строим экономико-математическую модель. Управляемая переменная x_j – количество продукта j-го вида, которое будем приобретать (j=1,2,…,n). Функция цели – суммарная стоимость продуктов питания (1)

Ограничения  (2) x_j  0, j=1,2,…,n (3) Решить задачу – значит найти вектор , такой, что при условиях (2) и (3). Эта задача также является задачей линейного программирования. Можно формально свести эту задачу к предыдущей, если вместо минимизации функции рассматривать максимизацию функции , а ограничение вида свести к ограничению вида .