Основная задача линейного программирования и ее модель в различных формах записи

Постановка задачи.

Пусть некоторое предприятие имеет m видов производственных ресурсов. Порядковый номер ресурсов — i, т. е. i=1, 2,…, m.

Наличие каждого вида ресурсов известно и обозначается b_i.

Предположим, что предприятие может производить n видов продукции. Порядковый номер продукции — j, т. е. j=1, 2, …, n.

Необходимо определить какое количество единиц продукции каждого вида надо производить (x_j), чтобы получить максимум этой продукции в стоимостном выражении, если известны затраты на производство единицы продукции каждого вида ресурса (a_ij) и цена реализации (c_j).

Развернутая форма записи модели.

I. Целевая функция — описывает выход продукции в стоимостном выражении:

Z=c₁x₁+c₂x₂+…+c_nx_nmax.

II. Система основных ограничений — описывает с помощью математической зависимости тот факт, что расходы производственных ресурсов не должны превышать их наличие:

a₁₁x₁+a₁₂x₂+…+a_1nx_n b₁;

a₂₁x₁+a₂₂x₂+…+a_2nx_n b₂;

…

a_m1x₁+a_m2x₂+…+a_mnx_n b_m.

III. Условие неотрицательности переменных величин:

x₁0, x₂0, …, x_n0.

Замечание: в постановке с выбором другого критерия оптимальности целевая функция может стремиться к минимуму. Кроме того система ограничений может быть смешанной, т. е. содержать не только неравенства (,), но и равенства.

Структурная форма записи модели.

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

I. max.

II., i=1,2,…,m.

III. x_j0, j=1,2,…,n.

Замечание: одной формулой можно описать ограничения, имеющие одинаковую структуру и тип и включающие в себя одни и те же переменные.

Существуют также векторная, матричная и табличная формы записи модели.