Экономико-математические модели задач лп эмм планирования производства (задача о наилучшем использовании ресурсов)

Дано:

• предприятие выпускает n различных видов продукции (j=1,2,…,n);

• оно располагает для этого m видами ресурсов (i=1,2,…,m) (например, рабочая сила, площади, сырьё, энергия и пр.);

• ресурсы ограничены и составляют условных единиц;

• цена реализации j-го продукта равна , то есть задан вектор цен ;

• технологические коэффициенты a_ij : сколько единиц i- го ресурса расходуется для производства единицы j- го вида продукции.

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

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

Теперь составим баланс расхода по каждому ресурсу. Скажем, расход i- го ресурса складывается из затрат на производство 1-го изделия, то есть a_i1x₁, расхода на производство 2-го изделия a_i2x₂,…, расхода на производство n-го изделия a_inx_n. С другой стороны, этот суммарный расход не может превысить общего количества этого ресурса, то есть b_i. Таким образом, запишем аналогичные ограничения для каждого из ресурсов, получим систему неравенств:

Чтобы план был реален, он должен состоять из неотрицательных компонент:

Запишем ЗЛП о наилучшем использовании ресурсов в компактном виде: найти при ограничениях

;

.

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

Рассмотрим на примере задачи о диете: получить кормовой рацион с заданными свойствами (содержанием питательных веществ) при наименьших затратах на исходные сырьевые материалы.

Дано:

• n видов исходных продуктов (сено, силос и пр. для животноводства);

• они содержат m видов питательных веществ (белки, жиры, углеводы, соли и т.д);

• для жизнедеятельности надо потреблять не менее b_i единиц i-го питательного вещества;

• c_j – стоимость единицы исходного продукта j – го вида;

• a_ij – содержание i-го питательного вещества в единице j-го вида корма.

Составим ЭММ задачи. Обозначим через x_j количества кормов j-го вида. Тогда суммарная стоимость всего набора кормосмесей равна . Эта стоимость должна быть минимальной, то есть целевая функция задачи выглядит так:

.

Теперь составим баланс по каждому питательному веществу в кормовом рационе. Для i-го питательного вещества: содержание i-го питательного вещества в кормосмеси первого вида равно a_i1x₁, в кормосмеси второго вида равно a_i2x₂,…, в кормосмеси n-го вида равно a_inx_n. Общее количество i-го питательного вещества должно быть не меньше, чем b_i. Это задаёт вид неравенства, и в результате запишем систему ограничений для всех питательных веществ:

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

Формы записи злп

Симметричная или стандартная форма записи ЗЛП. Она состоит в определении максимального значения функции (4) при выполнении условий (5) и (8) общей ЗЛП, где k=m и t=n.

Каноническая форма записи ЗЛП: это задача на максимум

,

все нетривиаальные ограничения заданы в виде равенств

а тривиальные ограничения распространяются на все переменные

Матричная форма. Введём обозначения:

матрица системы ограничений;

вектор-строка коэффициентов целевой функции;

вектор-столбец неизвестных (штрих, обозначающий транспонирование, позволяет нам столбцовый вектор записать как строку для удобства);

вектор-столбец свободных членов системы нетривиальных ограничений задачи.

Запишем каноническую форму в матричном виде:

Веторная форма. Рассмотрим только одну из векторных форм. Обозначим

, .

Задача принимает вид:

(здесь скалярное произведение векторов)

Однородная форма. Однородной называется такая модель ЗЛП, в которой все ограничения (нетривиальные и тривиальные) заданы в виде неравенств:

Эта форма удобна при графическом методе решения ЗЛП. Обратите внимание, что здесь переменные не обязательно неотрицательны.