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

Задача линейного программирования

Линейное программирование является частным разделом математического программирования. Математическое программирование – направление прикладной математики, в котором изучаются задачи условной оптимизации. В экономике такие задачи возникают при практической реализации принципа оптимальности в планировании и управлении.

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

Суть принципа оптимальности состоит в стремлении выбрать планово-управленческое решение, заданное вектором = (х₁, х₂,…х_n), где х_j (j =) – его компоненты, которое наиболее адекватно отражает внутренние возможности и внешние условия производственной деятельности хозяйствующего субъекта.

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

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

Принципу оптимальности в планировании и управлении отвечает решение экстремальной задачи вида:

max (min) f (), (1)

(2)

где f () – математическая запись критерия оптимальности – целевая функция.

Задачу условной оптимизации (1) - (2) обычно записывают в виде:

Найти максимум или минимум функции

f () = f (х₁, х₂,…х_n) (3)

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

(х₁, х₂,…х_n) {<,=,>}b₁ (4)

(х₁, х₂,…х_n) {<,=,>}b₂

............................................

(х₁, х₂,…х_n) {<,=,>}b_m

x_j0, j=. (5)

Обозначение {<,=,>} говорит о том, что в конкретном ограничении возможен один из знаков: <,= или >. Более компактная запись:

max (min) f (х₁, х₂,…х_n), (6)

(х₁, х₂,…х_n) {<,=,>} b_i, i=, (7)

x_j0, j=. (8)

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

Вектор (набор управляющих переменных x_j, (j = ) называется допустимым решением, или планом задачи математического программирования, если он удовлетворяет системе ограничений. Допустимый план Х, который позволяет достичь максимум или минимум целевой функции f(x₁, х₂,..., х_n), называется оптимальным планом (оптимальным вариантом, или просто решением) задачи оптимального программирования.

Выбор оптимального управленческого решения в конкретной производственной ситуации связан с проведением с позиций системности и оптимальности экономико-математического моделирования и решением задачи оптимального программирования.

Задачи математического программирования классифицируют по следующим признакам.

1. По характеру взаимосвязи между переменными:

а) линейные – все соотношения заданы линейными функциями;

б) нелинейные – наличие нелинейных функций.

2. По характеру изменения переменных:

а) непрерывные, область допустимых значений образуют действительные числа;

б) дискретные – требование целочисленности некоторых переменных.

3. По учету фактора времени:

а) статические,

б) динамические.

4. По наличию информации о переменных:

а) задачи в условиях полной определенности (детерминированные),

б) задачи в условиях неполной информации,

в) задачи в условиях неопределенности.

5. По числу критериев оценки альтернатив:

а) однокритериальные задачи,

б) задачи с использованием многокритериального комплекса.

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

В задаче линейного программирования (ЗЛП) требуется найти экстремум (максимум или минимум) линейной целевой функции 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_j0, j=, (11)

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

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

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

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

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

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

Найти

max f () = (12)

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

, (13)

х_j0, b_i0, i=, j=. (14)

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

Найти

max f () =

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

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

0,

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

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

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

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

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

max

при условиях

А=В, 0

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

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

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

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

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

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

Характеристика	Компонент автомобильного бензина
№ 1	№ 2	№ 3	№ 4
Октановое число
Содержание серы, %	0,35	0,35	0,3	0,2
Ресурсы, т
Себестоимость, ден.ед./т

Найти, сколько тонн каждого компонента следует использовать для получения 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₄,761000, (2а)

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

x₁700,

x₂600,

x₃500,

x₄300,

x_j0, j=1,2,3,4.

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

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

Т,

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

=40571+450+60143+90286=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а)

0x₁0,8; (3а)

0x₂0,9; (4а)

0x₃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 - Нормы затрат и выхода продукции в хозяйстве

Культура	Затраты ресурсов на 1 га посева	Выход валовой продукции с 1 га, тыс. руб.
труда, чел.-дн.	пашни, га
Зерновые культуры (х1)
Сахарная свекла (х2)

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

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

Исходя из ло­гических рассуждений можно предложить, что всю площадь необходимо занять той культурой, которая обеспечивает наибольший выход валовой про­дукции с 1 га (в данном случае сахарной свеклой). Но для возделывания 5 га сахарной свеклы потребовалось бы 5150=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 га пашни.

Дата добавления: 2014-01-05