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

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

Понятие линейного программирования

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

Особенностью задач линейного программирования является то, что экстремума целевая функция достигает на границе области допустимых решений. Классические же методы дифференциального исчисления связаны с нахождением экстремумов функции во внутренней точке области допустимых значений. Отсюда — необходимость разработки новых методов.

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

Задача о наилучшем использовании ресурсов

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

Предприятие при производстве этих видов продукции должно ограничиваться имеющимися видами ресурсов, технологий, других производственных факторов (сырья, полуфабрикатов, рабочей силы, оборудования, электроэнергии и т. д.). Все эти виды ограничивающих факторов называют ингредиентами R_i. Пусть их число равно m; припишем им индекс i (i= ). Они ограничены, и их количества равны соответственно b₁ ,.., b_i, .., b_m условных единиц. Таким образом, b=(b₁ ; ..; b_i; .. ; b_m)—вектор ресурсов.

Известна экономическая выгода (мера полезности) производства продукции каждого вида, исчисляемая, скажем, по отпускной цене товара, его прибыльности, издержкам производства, степени удовлетворения потребностей и т. д. Примем в качестве такой меры, например, цену реализации с_j (j= ), т.е. с = (c₁; с₂; ...; c_j; ...; с_n) — вектор цен.

Известны также технологические коэффициенты а_ij, которые указывают, сколько единиц i-горесурса требуется для производства единицы продукции j-го вида. Матрицу коэффициентов а_ij называют технологической и обозначают буквой А. Имеем А= .

Обозначим через х=(x₁; ...; х_j; ...; х_п) план производства, показывающий, какие виды товаров П₁, …,П_j, …,П_n нужно производить и в каких количествах, чтобы обеспечить предприятию максимум объема реализации при имеющихся ресурсах.

Так как с_j — цена реализации единицы j-й продукции, цена реализованных х_j единиц будет равна c_jx_j, а общий объем реализации

Z=c₁x₁+…+c_nx_n

Это выражение — целевая функция, которую нужно максимизировать.

Так как a_ijx_j — расход i-го ресурса на производство х_j единиц j-й продукции, то, просуммировав расход i-го ресурса на выпуск всех n видов продукции, получим общий расход этого ресурса, который не должен превосходить b_i (i= ) единиц:

a_i1x₁+…+a_ijx_j+…+a_inx_n ≤ b_i.

Чтобы искомый план х = (x₁; x₂; …; x_j; …; x_n) был реален, наряду с ограничениями на ресурсы нужно наложить условие неотрицательности на объемы х_j выпуска продукции:

x_j ≥0(j= ).

Таким образом, модель задачи о наилучшем использовании ресурсов примет вид: найти

max Z= (1)

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

(2)

x_j ≥ 0 (j= ) (3)

Так как переменные x_j входят в функцию z(х) и систему ограничений только в первой степени, а показатели а_ij, b_i, с_j являются постоянными в планируемый период, то (1) — (З) —задача линейного программирования.

Транспортная задача

Рассмотрим простейший вариант модели транспортной задачи, когда речь идет о рациональной перевозке некоторого однородного продукта от производителей к потребителям; при этом имеется баланс между суммарным спросом потребителей и возможностями поставщиков по их удовлетворению. Причем потребителям безразлично, из каких пунктов производства будет поступать продукция, лишь бы их заявки были полностью удовлетворены. Так как от схемы прикрепления потребителей к поставщикам существенно зависит объем транспортной работы, возникает задача о наиболее рациональном прикреплении, правильном направлении перевозок грузов, при котором потребности полностью удовлетворяются, вся продукция от поставщиков вывозится, а затраты на транспортировку минимальны.

Задача формулируется так. Имеется m пунктов производства с запасами единиц однородного продукта. Этот продукт нужно доставить n потребителям с потребностями единиц. Причем .

Известны величины c_ij — затраты на перевозку единицы продукта из i-го пункта производства в j-й пункт потребления, где . Обозначим через x_ij количество продукта, перевозимое из i-го пункта производства в j-й пункт потребления. Матрица называется матрицей тарифов, — матрицей перевозок.

С целью удобства построения математической модели матрицы тарифов и перевозок совмещают в одну, именуемую макетом транспортной задачи (см. лекцию №3).

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

Z= (1)

минимизируется при ограничениях:

на возможности поставщиков — весь продукт из пунктов производства должен быть вывезен:

(i=1,…,m) ( 2)

на спрос потребителей, который должен быть удовлетворен:

(j=1,…,n) (3)

при условии неотрицательности переменных, исключающем обратные перевозки:

x_ij =0 (i=1,…,m; j=1,…,n) (4).

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

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

F= . (1)

при условиях

, (2)

(3)

( ), (4)

где a_ij, b_i, c_j — заданные постоянные величины и k≤m.

Определение. Функция (1) называется целевой функцией (или линейной формой) задачи (1) — (4), а условия (2) — (4) — ограничениями данной задачи.

Определение. Стандартной (или симметричной) задачей линейного программирования называется задача, которая состоит в определении максимального значения функции (1) при выполнении условий (2) и (4), где k=m и i=n.

Определение. Канонической (или основной) задачейлинейного программирования называется задача, которая состоит в определении максимального значения функции (1) при выполнении условий (3) и (4), где k=0 и i=n.

Определение. Совокупность чисел X=(x₁, x₂, ...., x_n), удовлетворяющих ограничениям задачи (2) — (4), называется допустимым решением (или планом).

Определение. План X*=(x*₁, x*₂, ...., x*_n), при котором целевая функция задачи (1) принимает свое максимальное (минимальное) значение, называется оптимальным.

Значение целевой функции (1) при плане X будем обозначать через F(X). Следовательно, X*— оптимальный план задачи, если для любого X выполняется неравенство F(X) ≤ F (X*) [соответственно F(X)≥F (X*)].

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

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

В том случае, когда требуется найти минимум функции F = c₁x₁+c₂x₂+…+c_nx_n, можно перейти к нахождению максимума функции F₁= -F= =-c₁x₁-c₂x₂-…-c_nx_n, поскольку min F=-max(-F).

Ограничение-неравенство исходной задачи линейного программирования, имеющее вид « ≤», можно преобразовать в ограничение-равенство добавлением к его левой части дополнительной неотрицательной переменной, а ограничение-неравенство вида « ≥» — в ограничение-равенство вычитанием из его левой части дополнительной неотрицательной переменной. Таким образом, ограничение-неравенство

a_i1x₁+a_i2x₂+…+a_inx_n ≤ b_i

преобразуется в ограничение-равенство

a_i1x₁+a_i2x₂+…+a_inx_n +x_n+1= b_i (x_n+1≥0),(5)

а ограничение-неравенство

a_i1x₁+a_i2x₂+…+a_inx_n ≥ b_i

— в ограничение-равенство

a_i1x₁+a_i2x₂+…+a_inx_n -x_n+1= b_i (x_n+1≥0). (6)

В то же время каждое уравнение системы ограничений

a_i1x₁+a_i2x₂+…+a_inx_n =b_i

можно записать в виде неравенств:

(7)

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

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

Отметим, наконец, что если переменная x_k не подчинена условию неотрицательности, то ее следует заменить двумя неотрицательными переменными u_k и v_k, приняв x_k = u_k - v_k.

Задача. Записать в форме основной задачи линейного программирования следующую задачу: найти максимум функции F = 3х₁—2x₂—5x₄+ x₅ при условиях

x₁, x₂, x₃, x₄, x₅ ≥ 0.

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

x₁, x₂, …, x₉ ≥ 0.

Следовательно, данная задача может быть записана в фор­ме основной задачи таким образом: максимизировать функцию F = 3х₁—2x₂—5x₄+ x₅ при условиях

x₁, x₂, …, x₉ ≥ 0.

Задача.Записать задачу, состоящую в минимизации функции F = -x₁+2x₂-x₃+x₄ при условиях

x₁, x₂, x₃, x₄ ≥ 0.

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

Решение. В данной задаче требуется найти минимум целевой функции, а система ограничений содержит три неравенства. Следовательно, чтобы записать ее в форме основной задачи, вместо нахождения минимума функции F нужно найти максимум функции F=—F при ограничениях, получающихся из ограничений исходной задачи добавлением к левым частям каждого из ограничений-неравенств вида «≤» дополнительной неотрицательной переменной и вычитанием дополнительных переменных из левых частей каждого из ограничений-неравенств вида «≥».

Следовательно, исходная задача может быть записана в форме основной задачи линейного программирования так: найти максимум функции F₁= x₁— 2x₂ + x₃ — x₄ при условиях

x₁, x₂, …, x₇ ≥ 0.

Задача.Записать в форме стандартной задачи линейного программирования следующую задачу: найти максимум функции F = 6,5x₁ — 7,5x₃+ 23,5x₄ — 5x₅ при условиях

x₁, x₂, …, x₅ ≥ 0.

Решение. Методом последовательного исключения неизвестных сведем данную задачу к следующей: найти максимум функции F = 6,5x₁ — 7,5x₃+ 23,5x₄ — 5x₅ при условиях

x₁, x₂, …, x₅ ≥ 0.

Последняя задача записана в форме основной для задачи, состоящей в нахождении максимального значения функции F=x₃+2x₄ при условиях

x₃, x₄ ≥ 0

Целевая функция задачи преобразована с помощью подстановки вместо x₁ и x₅ их значений в соответствии с уравнениями системы ограничений задачи.

Библиография

1. Кузнецов Ю.Н., Кузубов В.И., Волощенко А.Б., Математическое программирование, М.: Высшая школа, 1980.

2. Акулич И.Л. Математическое программирование в примерах и задачах, М.: Высшая школа, 1986.

Не нашли, что искали? Воспользуйтесь поиском по сайту: