Общая постановка задачи линейного программирования

Технико-экономические коэффициенты затрат и выхода продукции зависят от конкретных условий производства. Поэтому в обобщенной записи условий задачи линейного программирования все числовые величины заменим буквенными символами. Представим общую постановку задачи линейного программирования:

1. Заданы переменные задачи х₁,х₂, …x_j…x_n (j=1..n), где j – порядковый номер переменной.

2. Известны ресурсы производства в количествах b₁, b₂, …b_i,…b_m (i=1..m), где i - порядковый номер ресурса.

3. Заданы технико-экономические коэффициенты затрат каждого вида ресурса на единицу каждой переменной, которые обозначаются a_ij, а – величина коэффициента, i – порядковый номер ресурса, j- порядковый номер переменной. Например, а21 – означает затраты второго вида ресурса (труда) на единицу первой переменной (на 1 га зерновых).

4. Известны показатели выхода продукции на единицу переменной (с 1 га площади). Они обозначаются cj. Так в нашем примере, стоимость валовой продукции с 1 га зерновых с1= 400 тыс. руб, а с 1 га картофеля с2=1000 тыс.руб.

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

C=c₁x₁+c₂x₂+…+c_nx_nmax(min)

при соблюдении следующих линейных ограничивающих условий:

1. Ограничение по использованию 1-го вида ресурса

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

2. Ограничение по использованию 2-го вида ресурса

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

3. Ограничение по использованию m-го вида ресурса

a_m1x₁+a_m2x₂+…+a_mnx_nb_m

4. Ограничения по не отрицательности неизвестных величин:

x₁0, x₂0, x_n0

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

Три формы записи задачи линейного программирования.

Основная задача планирования производства может быть задана в 3-х формах записи:

• стандартная

• каноническая

• общая

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

В каноническом виде – только равенства.

В общем виде присутствуют как равенства, так и неравенства.

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

Запишем математически формы записи основной задачи планирования производства.

1. Стандартная форма записи

2. Каноническая форма записи

3. Общая форма