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

В задаче линейного программирования (ЗЛП) требуется найти экстремум (максимум или минимум) линейной целевой функции f( ):

max (min) f( ) = c₁x₁ + c₂x₂ + … + c_nx_n (9)

при ограничениях (условиях):

a₁₁x₁ + a₁₂x₂ + … + a_1nx_n { ,=, } b₁,

a₂₁x₁ + a₂₂x₂ + … + a_2nx_n { ,=, } b₂, (10)

……………………………………

a_m1x₁ + a_m2x₂ + … + a_mnx_n { ,=, } b_m,

x_j 0, j= , (11)

где а_ij, b_i, c_j (i = ; j = ) – заданные постоянные величины.

Систему ограничений (10) называют функциональными ограничениями ЗЛП, а ограничения (11) – прямыми.

Вектор = (x₁, x₂, …, х_n), удовлетворяющий системе ограничений (10), (11), называется допустимым решением, или планом задачи линейного программирования, т.е. ограничения (10), (11) определяют область допустимых решений, или планов задачи линейного программирования (область определения ЗЛП).

План (допустимое решение), который доставляет максимум или минимум целевой функции (9), называется оптимальным планом (оптимальным решением) ЗЛП.

Канонической формой записи задачи линейного программирования

(КЗЛП) называют задачу вида (запись с использованием знаков суммирования):

Найти

max f ( ) = (12)

при ограничениях

, (13)

х_j 0, b_i 0, i= , j= . (14)

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

Найти

max f ( ) =

при ограничениях

₁x₁ + ₂x₂ + … + _nx_n = ,

0,

где = (с₁, с₂, … с_n), = ( х₁, х₂,…х_n),

– скалярное произведение векторов , ;

_i и – вектор – столбцы:

₁ = , ₂= , … , _n= , = .

Матричная форма записи КЗЛП:

max

при условиях

А =В, 0

Здесь = (c₁, с₂,..., с_п) – вектор-строка; А = (а_ij) – матрица размерности (m n), столбцами которой являются вектор-столбцы _j,

- вектор – столбец, - вектор – столбец.

Приведение ЗЛП к каноническому виду осуществляется введением в левую часть соответствующего ограничения вида (10) k-й дополнительной переменной x_n+k со знаком (-) в случае ограничения типа и знаком (+) в случае ограничения типа .

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

Задача о смесях. Октановое число автомобильного бензина А-76 должно быть не ниже 76, а содержание серы в нем – не более 0,3%. Для производства такого бензина используется четыре компонента. Данные о ресурсах компонентов, их себестоимости, октановом числе и содержании серы приведены в таблице 1.

Таблица 1 – Исходные данные для задачи о смесях

Найти, сколько тонн каждого компонента следует использовать для получения 1000 т автомобильного бензина А-76, чтобы его себестоимость была минимальной.

Решение. Сформулируем экономико-математическую модель задачи. Обозначения: пусть X_j (j = 1,2,3,4) – количество в смеси компонента с номером j. Критерий оптимальности – «минимум себестоимости»:

min f( )=40x₁+45x₂+60x₃+90x₄,

x₁+x₂+x₃+x₄,=1000, (1а)

68x₁+72x₂+80x₃+90x₄, 76 1000, (2а)

0,35x₁+0,35x₂+0,3x₃+0,2x₄, 0,3 1000, (3а)

x₁ 700,

x₂ 600,

x₃ 500,

x₄ 300,

x_j 0, j=1,2,3,4.

Функциональное ограничение (1а) отражает необходимость получения заданного количества смеси (1 000 т), (2а) и (3а) – ограничения по октановому числу и содержанию серы в смеси, остальные – ограничения на имеющиеся объемы соответствующих ресурсов.

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

Т,

Подставляя найденное решение в целую функцию, находим минимальную себестоимость:

=40 571+45 0+60 143+90 286=57 160,0 (ден. ед.),

Использование ограниченных ресурсов.

На строящуюся дорогу необходимо вывезти 20 000 м³ каменных материалов. Имеется три карьера с запасами 8 000 м³, 9 000 м³ и 10 000 м³. Для погрузки материалов используются экскаваторы, имеющие производительность 250 м³ в смену в карьерах 1 и 2 и 500 м³ в смену в карьере 3. На погрузку материалов для экскаваторов выделен общий лимит 60 машино-смен.

Для перевозки 10 000 м³ материалов из карьера 1 требуется 1 000 автомобиле-смен, из карьера 2 – 1 350, из карьера 3 – 1 700 автомобиле-смен. Требуется найти оптимальный план перевозок по критерию минимума транспортных затрат.

Решение. Сформулируем экономико-математическую модель задачи. Примем за единицу измерения количества материалов 10 000 м³.

Пусть х₁ - объем добычи материалов в карьере 1, х₂ – в карьере 2,

х₃ – в карьере 3. Минимизировать транспортные затраты:

min f( )=1000x₁+1350x₂+1700x₃,

при ограничениях

x₁+x₂+x₃,=2,0; (1а)

40x₁+40x₂+20x₃ 60; (2а)

0 x₁ 0,8; (3а)

0 x₂ 0,9; (4а)

0 x₃ 1,0. (5а)

Условие (1а) отражает потребность в материалах, (2а) – ограничение по балансу ресурса «фонд рабочего времени экскаваторов». Условия (3а)-(5а) отражают ограниченность запасов материалов в соответствующих карьерах. Получена задача ЛП; решение ее симплекс-методом позволит найти оптимальный план:

=0,8 (8000 м³)

=0,2 (2000 м³); =1,0 (10000 м³).

Таким образом, из карьера 1 следует вывезти 8 000 м³ материалов, из карьера 2 – 2 000 м³, из карьера 3 – 10 000 м³ при минимальных транспортных затратах

f(X*) = 1 000 0,8 + 1350 0,2 + 1 700 1,0 = 2 770 (автомобиле-смен).

Экономическая постановка сельскохозяйственной задачи.

Фермерское хозяйство занимается возделыванием только двух культур (зерновых и сахарной свеклы), располагая следующими ресурсами: пашня - 5 га, труд - 300 чел. – дней. Цель производства - получение максимального объема валовой продукции в стоимостном выражении. Требуется найти оптимальное сочетание посевных площадей культур.

Нормы затрат ресурсов и выхода продукции приведены в таблице 2.

Таблица 2 - Нормы затрат и выхода продукции в хозяйстве

Критерием оптимальности (показателем оценки качества варианта решения) является макси­мум стоимости валовой продукции. Этот максимум дол­жен достигаться при использовании ограниченных ре­сурсов пашни и труда. Ука­занные ресурсы выступают в качестве ограничивающих условий задачи, а показатели, приведенные в таблице 2, являются технико-экономическими коэффициентами (коэффициентами затрат и выпуска продукции). Задача является многовариантной, поскольку имеется множество допустимых вариантов сочетаний посевных площадей двух культур.

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

Исходя из ло­гических рассуждений можно предложить, что всю площадь необходимо занять той культурой, которая обеспечивает наибольший выход валовой про­дукции с 1 га (в данном случае сахарной свеклой). Но для возделывания 5 га сахарной свеклы потребовалось бы 5 150=750 чел. – дн., что значительно превы­шает наличные ресурсы труда. Необходимость одно­временного учета всех ресурсов еще более усложняет задачу.

Для нахождения оптимального варианта решения методами линейного программирования необходимо математически формули­ровать (описать) условия и ограничения задачи.

Математическая формулировка задачи линейного программирования.

В нашем примере неизвестными ве­личинами являются посевные площади зерновых культур и сахарной свеклы в гектарах (х₁ и х₂). Критерий оптимальности - стоимость валовой продукции - оп­ределяется как сумма произведений стоимости продук­ции с 1 га на посевные площади (тыс. руб.):

Z_max=4x₁+10x₂.

Максимум целевой функции должен быть достиг­нут при соблюдении следующих условий:

1. Общая площадь зерновых культур и сахарной свеклы не должна превышать площади пашни, га:

x₁+x₂ 5.

2. Затраты труда не долж­ны быть больше наличных ресурсов (чел. – дн.):

30x₁+150x₂ 300.

3. Площади не могут быть отрицательными величи­нами:

х₁ 0, х₂ 0.

Таким образом, условия задачи выражаются в виде следующей системы неравенств:

x₁+x₂ 5;

30x₁+150x₂ 300;

x₁ 0; x₂ 0.

Целевая функции: Z_max=4x₁+10x₂.

Приведенные неравенства называют ограничениями экстремальной задачи линейного программирования.Число ограничений в задачах может быть очень боль­шим – от десятков до многих сотен и тысяч.

В целевую функцию и систему ограни­чений переменные х₁ и х₂ входят только в первой степе­ни, то есть все математические соотношения являются линейными. Таким образом, рассматриваемый пример относится к задачам линейного программирования.

При формулировке ограничений в задаче не должно быть противоречивых условий. На­пример, если одновременно ввести условия: площадь зерновых культур не менее 3 га и сахарной свеклы не менее 4 га, то задача станет неразрешимой, так как име­ется лишь 5 га пашни.