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

Принцип оптимальности в планировании и управлении, общая задача оптимального программирования

Линейное программирование

Слово “программирование” используется в значении “планирование”, не имеет отношения к компьютерному программированию.

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

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

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

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

Таким образом, реализовать на практике принцип опти­мальности в планировании и управлении — это значит ре­шить экстремальную задачу вида:

max(min) f( ),	(2.1)
ÎD,	(2.2)

где f( ) — математическая запись критерия оптималь­ности — целевая функция. Задачу условной оптимизации (2.1), (2.2) обычно записывают в виде:

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

f( )=f(х1, х2,..., xп),

(2.3)

при ограничениях j₁ =(х₁, х₂,..., x_п){}b₁,

j2 =(х1, х2,..., xп) {}b2,	(2.4)
….
jm =(х1, х2,..., xп) {}bm,
xj0, j =	(2.5)

Условие (2.5) необязательно, но его всегда при необходи­мости можно добиться. Обозначение {} говорит о том, что в конкретном ограничении возможен один из знаков: . Более компактная запись:

max(min) f(х1, х2,..., xп),	(2.6)
ji =(х1, х2,..., xп) {}bi, i=	(2.7)
xj0, j =	(2.8)

Задача (2.6)-(2.8) — общая задача оптимального (мате­матического) программирования, иначе — математическая модель задачи оптимального программирования, в основе построения (разработки) которой лежат принципы опти­мальности и системности.

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

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

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

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

а) линейные (все функциональные связи в системе ограни­чений и функция цели — линейные функции),

б) нелинейные (наличие не­линейности хотя бы в одном из упомянутых элементов).

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

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

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

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

а) статические (моделирование и принятие решений осуще­ствляются в предположении о независимости от времени элементов модели в течение периода времени, на который принимается планово-управленческое решение),

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

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

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

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

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

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

а) простые, однокритериальные задачи (экономически приемлемо использование одного критерия оптимальности или удается специальными процедурами (например, «взвешиванием приоритетов») свести многокритериальный поиск к однокритериальному),

б) сложные, многокритериальные задачи.

Сочетание признаков 1—5 позволяет группировать (клас­сифицировать) в самом общем виде задачи и методы оптимального программирования, например: 1а)2а)3а)4а)5а) — задачи и методы линейного программирования,1б)2а)3а)4a)5a) — задачи и методы нелинейного программирования, 1а)2б)3а)4а)5а) — задачи и методы целочисленного (дис­кретного) линейного программирования и т.д.

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

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

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

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

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

max(min) f( )=c1x1+c2x2+…+ cnxn,

(2.9)

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

a11x1+a12x2+…+ a1nxn {}b1,
a21x1+a22x2+…+ a2nxn {}b2,	(2.10)
………
am1x1+am2x2+…+ amnxn {}bm,
xj0, j =	(2.11)

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

Так записывается общая задача линейного программиро­вания в развернутой форме; знак {} означает, что в конкретной ЗЛП возможно ограничение типа равенства или неравенства (в ту или иную сторону).

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

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

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

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

Найти

max f( )=

(2.12)

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

	(2.13)
, j =.	(2.14)

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

Найти max f( )=CX

при ограничениях A₁x₁+A₂x₂+…+ A_nx_n, = В,

где С=(c₁, c₂,..., c_n), Х = (x₁, x₂,..., x_n),

СХ — скалярное произведение векторов С,Х,

A_j и В — вектор-столбцы:

, , …, , .

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

max f( )=CX

при условиях AX = B, X0.

Здесь С = (c₁, c₂,…, c_n,) — вектор-строка; А=(а_ij) — матри­ца размерности т x п, столбцами которой являются вектор-столбцы A_j,

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

Расширенная матрица этой системы будет иметь вид:

=

Иногда используется стандартная форма записи ЗЛП:

max(min) f( )=CX,

AXB, X 0.

При этом запись X 0 понимают как вектор (или век­тор-столбец в зависимости от контекста), у которого все ком­поненты (элементы) неотрицательны.

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

▼

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

max f( )=c₁x₁+c₂x₂,

a₁₁x₁+a₁₂x₂b₁,

a₂₁x₁+a₂₂x₂b₂,

x_j0, j =

Представим ее в канонической форме

max f( )=c₁x₁+c₂x₂+0x₃+0x₄,

a₁₁x₁+a₁₂x₂+x₃=b₁,

a₂₁x₁+a₂₂x₂+x₄=b₂,

x_j0, j =

Расширенная матрица будет иметь вид:

В ее составе присутствует единичная матрица.

▲

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

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

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

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