Эквивалентные формы записи задач линейного программирования
Задачами линейного программирования могут быть задачи нахождения оптимального сочетания отраслей, оптимальной структуры производства, оптимального рациона кормления животных, оптимального состава машинно-тракторного парка, оптимального размещения производства и другие.
Математическая запись задачи линейного программирования содержит основные переменные (неизвестные), которые обозначаются Xj, где j =1, 2, ..., n (или j = 1 ÷ n). Переменные величины могут произвольно изменяться в условиях рассматриваемой задачи.
Задача математического программирования состоит из целевой функции, системы ограничений и условия неотрицательности переменных.
Целевой функцией называется математическое выражение, для которого требуется найти экстремальное (то есть максимальное или минимальное) значение, например,
max Z = 
, где Cj- коэффициент целевой функции.
Целевую функцию называют также функционалом, линеалом. Целевая функция математически записывает критерий оптимальности, критерий качества.
От задачи на максимум можно перейти к задаче на минимум, умножив целевую функцию на минус единицу (-1).
Ограничение - это математическое выражение, связывающее переменные в виде равенств или неравенств. Все ограничения образуют систему ограничений задачи. Ограничения бывают трех типов: равенства (=), неравенства типа меньше либо равно 
, неравенства типа больше или равно 
.
|
|
|
Например, при i = 1, 2,...m.
,
,
,
Коэффициенты при переменных обозначаются a ij, где индекс i - номер ограничения, индекс j- номер переменной, свободные члены обозначаются a i0 , индекс i - номер ограничения, индекс o - признак свободного члена.
Условия неотрицательности переменных записываются в виде
xj 0 , j = 1, 2, ..., n, (или j = 1 ÷ n).
Задача математического программирования является задачей линейного программирования, если целевая функция и система ограничений - линейные выражения:
max Z = C1*x1 + C2*x2 +...+ Cn*x n
a 11 x 1 + a 12 x 2 +...+ a 1n. x n = a 10
a 21 x 1 + a 22 x2 +...+ a 2n x n = a 20
......................................................................
a k1 x 1 + a k2 x 2 +...+ a k n xn ≤ a k 0
a k+1,1 x 1 + a k+1,2 x 2 +...+ a k+1,n x n ≤ a k+1,0
a k+2,1 x 1 + a k+2,2 x2 +...+ a k+2,n x n ≤ a k+2,0 (2.1)
........................................................
a r-1,1 x 1 + a r-1,2 x 2 +...+ a r-1,n x n ≤ a r-1,0
a r 1 x 1 + a r 2 x 2 +...+ a r n x n ≥ a r 0
a r+1,1x1 + a r+1,2 x2 +...+ a r+1,n xn ³ a r+1,0
.................................................................
a m 1 x 1 + a m 2 x2 +...+ a m n x n ≥ a m 0
x j ≥ 0 , j = 1¸ n.
Или maxZ = 
(2.1')
Задача линейного программирования имеет бесчисленное множество решений. Система (2.1'- система ограничений и условия неотрицательности переменных задачи) должна быть совместной и неопределенной, т. е. должна иметь бесчисленное множество решений. Определенная система имеет только одно решение, а несовместная система не имеет ни одного решения.
|
|
|
Если условие экономической задачи представлено в математической записи, содержащей целевую функцию, систему ограничений и условия неотрицательности, причем ограничения записаны как в виде равенств, так и в виде неравенств, то такая запись называется исходной формой записи задачи линейного программирования.
Например,
max Z = 75x1 + 32x2 + 18x3
Каноническая форма задачи линейного программирования характерна тем, что содержит целевую функцию, все ограничения равенства, все переменные неотрицательные. (2.2).
max Z = 
(2.2)
Например,
max Z = 3 x1 + 4 x2 + 0 x3 + 0 x4
Каноническая форма используется при решении задач линейного программирования симплексным методом, являющимся универсальным методом решения таких задач.
Однородная форма записи задач линейного программирования[1] характерна тем, что содержит целевую функцию, все ограничения неравенства типа меньше или равно ( ), все переменные неотрицательные (2.3).
max Z = 
(2.3)
max Z = 4 x1 + 3 x2 
3.х1+4.х2 £12
2.х1+3.х2 £6
x j ³ 0 j = 1, 2
Однородная форма записи задач линейного программирования используется при решении задач графическим методом.
|
|
|
Каноническая и однородная формы являются частными случаями исходной формы.
Дата добавления: 2018-04-05; просмотров: 712; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!