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

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

8.1. Определения. Примеры задач линейного программирования

Линейное программирование − математическая дисциплина, посвященная теории и методам решения задач об экстремумах линейных функций на множествах, задаваемых системами линейных неравенств и равенств. Линейное программирование стало развиваться в первую очередь в связи с решением задач экономики, с поиском способов оптимального распределения и использования ресурсов. Оно послужило основой широкого использования математических методов в этой сфере. Следует подчеркнуть, что в реальных экономических задачах число независимых переменных обычно бывает очень большим (тысячи, десятки тысяч). Поэтому практическая реализация алгоритмов их решения принципиально невозможна без современной вычислительной техники. Пример 8.1 . Для изготовления трех видов сплавов A , B и C используется медь, олово и цинк. Данные о сплавах приведены в табл. 8.1. В ней же указано общее количество метала каждого типа, а так же стоимость реализации одного кг сплава каждого типа.

Процентное содержание и общая масса компонентов					Таблица 8.1.
Компоненты сплава	Общая масса данной
A	B	C	компоненты сплава, т.
Медь	20	10	30	120
Олово	10	80	60	280
Цинк	70	10	10	240
Стоимость 1кг.	10	14	12	−

Требуется определить, какое количество сплавов каждого вида следует изготовить предприятию, чтобы стоимость продукции была максимальной. □ Предположим, что будет изготовлено x 1 кг сплава A , x 2 кг сплава B и x 3 кг сплава C . Тогда для производства такого количества сплавов потребуется затратить 20 x 1 + 10 x 2 + 30 x 3 кг меди.
Так как общая масса меди не может превышать 120 т, то должно выполняться неравенство 20 x 1 + 10 x 2 + 30 x 3 ≤ 120000 . Аналогичные рассуждения относительно возможности использования олова и цинка приведут к неравенствам 10 x 1 + 80 x 2 + 60 x 3 ≤ 280000, 70 x 1 + 10 x 2 + 10 x 3 ≤ 240000. При этом, так как масса сплавов не может быть отрицательной, то

x 1	≥ 0, x 2 ≥ 0, x 3 ≥ 0.	(8.1)
Если будет изготовлено	x 1 кг сплава A , x 2 кг сплава B	и x 3 кг сплава C , то

стоимость продукции составит F = 10 x 1 + 14 x 2 + 12 x 3 . Таким образом, приходим к следующей математической задаче. Дана система

20 x		+ 40 x	2	+ 50 x	3	≤ 120000
1	≤ 280000
10 x 1 + 80 x 2				+ 60 x 3		(8.2)
+ 10 x 2		+ 10 x 3		≤ 240000
					70 x 1

из четырех линейных неравенств (8.1) − (8.2) с тремя неизвестными и линейная функция относительно этих же переменных

F = 10 x 1 + 14 x 2 + 12 x 3 .

(8.3)

Требуется среди всех неотрицательных решений системы неравенств (8.2) найти такое, при котором функция (8.3) принимает максимальное значение. Так как функция (8.3) линейная, а система (8.2) содержит только линейные неравенства, то задача (8.1)−(8.3) является задачей линейного программирования. ■ Пример 8.2 . Продукцией молочного завода являются молоко, кефир и сметана. На производство 1 т молока, кефира и сметаны требуется соответственно 1010, 1010 и 9450 кг молока. При этом затраты рабочего времени при разливе 1 т молока и кефира составляют 0,18 и 0,19 машино-часов. На расфасовке 1 т сметаны заняты специальные автоматы, работающие в течение 3,25 ч. Всего для производства цельномолочной продукции завод может использовать 136 т молока. Основное оборудование может быть занято в течение 21,4 машино-часа, а автоматы по расфасовке сметаны − в течение 16,25 ч. Прибыль от реализации 1 т молока,
кефира и сметаны соответственно равна 30000, 26000 и 150000 руб. Завод должен ежедневно производить не менее 100 т молока, расфасованного в пакеты. Требуется определить, какую продукцию и в каком количестве следует ежедневно изготовлять заводу, чтобы прибыль от ее реализации была максимальной. □ Предположим, что молочный завод будет ежедневно производить x 1 тонн молока, x 2 тонн кефира и x 3 тонн сметаны. Тогда для производства этой продукции необходимо 1010 x 1 + 1010 x 2 + 9450 x 3 кг молока. Так как завод может использовать ежедневно не более 136000 кг молока, то должно выполняться неравенство 1010 x 1 + 1010 x 2 + 9450 x 3 ≤ 136000. Аналогичные рассуждения, проведенные относительно возможного использования линий разлива цельномолочной продукции и автоматов по расфасовке сметаны, позволяют записать неравенства 0,18 x 1 + 0,19 x 2 ≤ 21,4 3,25 x 3 ≤ 16,25. Так как ежедневно должно вырабатываться не менее 100т молока, то x 1 ≥ 100. По своему экономическому смыслу переменные x 2 и x 3 могут принимать лишь

неотрицательные значения		x 2	≥ 0, x 3 ≥ 0.		Общая прибыль от реализации x 1 тонн
молока, x 2 тонн кефира и		x 3	тонн сметаны равна 30000 x 1 + 22000 x 2 + 150000 x 3 руб.
Таким образом, приходим к следующей задаче.
Дана система
1010 x 1 + 1010 x 2				+ 9450 x 3		≤ 136000
0,18 x 1	+	0,19 x 2	≤ 21,4
				(8.4)
3,25 x 3	≤ 16,25
			x 1 ≥ 100, x 2 ≥ 0,				x 3	≥ 0.

из четырех линейных неравенств и линейная функция относительно переменных, x 1 , x 2 и x 3

F = 30000 x 1 + 22000 x 2 + 150000 x 3 .

(8.5)

Так как система (8.4) представляет собой систему линейных неравенств и функция (8.5) линейная, то эта задача является задачей линейного программирования. ■

8.2. Общая и каноническая задачи линейного программирования

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

n	(8.6)
F = ∑ c j x j
j = 1
при выполнении условий	(8.7)
n
∑ a ij x j ≤ b i ( i = 1. k )
j = 1	(8.8)
n
∑ a ij x j = b i ( i = k + 1. m )
j = 1
x j ≥ 0 ( j = 1. l ; l ≤ n )	(8.9)

где a ij , b i и c j − заданные постоянные величины и k ≤ m . Определение . Функция (8.6) называется целевой функцией задачи (8.6) − (8.9), а условия (8.7) − (8.9) − ограничениями данной задачи. Определение. Канонической задачей линейного программирования называется задача, которая состоит в определении максимального значения функции (8.6) при выполнении условий (8.8) и (8.9), где k = 0 и l = n .

Определение.	Вектор	X = ( x 1 , x 2 , … , x n ) T ,	удовлетворяющий ограничениям
задачи (8.7) − (8.9), называется допустимым решением , или планом .
Определение .	План	X = ( x 1 , x 2 , … , x n ) T ,	при котором целевая функция

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

неравенств к ограничениям-равенствам; в-третьих, заменять переменные, которые не подчинены условиям неотрицательности. В том случае, когда требуется найти минимум функции F = с 1 x 1 + с 2 x 2 +…+ с n x n , можно перейти к нахождению максимума функции F 1 = − F = − с 1 x 1 − с 2 x 2 −…− с n x n , поскольку min F = max( − F ) . Нестрогое ограничение-неравенство общей задачи линейного программирования можно преобразовать в ограничение-равенство добавлением к его левой части дополнительной неотрицательной переменной. Таким образом, ограничение-неравенство a i 1 x 1 + a i 2 x 2 +…+ a in x n ≤ b i преобразуется в ограничение-равенство a i 1 x 1 + a i 2 x 2 +…+ a in x n + x n + 1 = b i , x n + 1 ≥ 0, а ограничение-неравенство a i 1 x 1 + a i 2 x 2 +…+ a in x n ≥ b i преобразуется в ограничение-равенство a i 1 x 1 + a i 2 x 2 +…+ a in x n − x n + 1 = b i , x n + 1 ≥ 0. Вводимые дополнительные переменные имеют вполне определенный смысл в рамках решения экономических задач. Так, если в ограничениях исходной задачи линейного программирования отражается расход и наличие производственных ресурсов, то числовое значение дополнительной переменной в плане задачи, как это будет показано в дальнейших примерах, равно объему неиспользуемого соответствующего ресурса. Наконец, если переменная x k по условию задачи отрицательна, то ее следует заменить двумя неотрицательными переменными u k и v k , приняв x k = u k − v k . Пример 8.3. Записать в форме канонической задачи линейного программирования задачу нахождения максимума функции F = 3 x 1 − 2 x 2 − 5 x 4 + x 5 при условиях 2 x 1 + x 3 − x 4 + x 5 ≤ 2, x 1 − x 3 + 2 x 4 + x 5 ≤ 3,2 x 1 + x 3 − x 4 + 2 x 5 ≤ 6, x 1 + x 4 + 5 x 5 ≥ 8, x 1 , x 2 , x 3 , x 4 , x 5 ≥ 0

Источник

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

Общая задача. Найти максимальное значение линейной целевой функции. z = c₁x₁+ c₂x₂+ … + c_nx_n при линейных ограничениях x_j>= 0,j= 1,n= n> Определение 1.1. Совокупность чисел х = (х₁, х₂. х_n), удовлетворяющих ограничениям (1.2), называется допустимым решением или планом. Определение 1.2. План х* =(х₁ * , х₂ * . х_n*), при котором целевая функция (1.1) принимает свое максимальное значение, называется оптимальным.Каноническая форма. Задачу линейного программирова­ния будем считать приведенной к каноническому виду, если 1) требуется найти максимум целевой функции; 2) система ограничений (1.2) содержи! только равенства; 3) правые части системы ограничений неотрицательны. Переход от общей формы к канонической: 1) если в задаче требуется найти минимум целевой функции, то вводим новую целевую функцию z₁ = -z, тогда max z₁ = -min z; 2) чтобы перейти от неравенства к равенству в системе огра­ничений, необходимо прибавить (вычесть) дополнительную не­отрицательную переменную к левой части неравенства; 3) если в правой части системы ограничений имеются отрица­тельные числа, то необходимо умножить на «-1» обе части равен­ства, в котором в правой части стоит отрицательное число. Задачу линейного программирования в канонической фор­ме называют основной задачей.

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

Свойства задач линейного программирования. Рассмотрим следующую основную задачу линейного про­граммирования: z = c₁x₁+ c₂x₂+ …+c_nx_nmax при ограничениях , Перепишем ограничения этой задачи к немирной форме: x₁Р,+х₂Р₂+. + х_nР_n,(1.3) где Р₁, . Р_nи Р₀ — k-мерные вектор-столбцы, составленные из коэффициентов при неизвестных и свободных членах системы ограничений основной задачи: Определение 1. План х = (x₁,х₂. х_n) называется опорным планом основной задачи линейного программирования, если его положительные коэффициенты (х_j >0) стоят при линейно независимых векторах Р_j. Так как векторы Р: являются k-мерными, то из определения опорного плана следует, что число его положительных компо­нент не может быть больше числа К. Определение 2. Опорный план называется невырож­денным, если он содержит ровно k положительных компонент, в противном случае он называется вырожденным. Свойства задач линейного программирования тесным обра­зом связаны со свойствами выпуклых множеств. Определение 3. Пусть х(|). х(m) — произвольные точ­ки евклидова пространства Rn . Выпуклой линейной комбинацией этих точек называется сумма: а,х(|) + . + а_mх(m) , где а_i; -про­извольные неотрицательные числа, сумма которых равна 1. Определение 4. Множество называется выпуклым, ес­ли вместе с любыми двумя своими точками оно содержит и отре­зок прямой, соединяющий эти точки. Определение 5. Точка х выпуклого множества назы­вается угловой, если она не может быть представлена в виде вы­пуклой линейной комбинации каких-нибудь двух других различ­ных точек данного множества. Сформулируем первое свойство задач ЛП. Теорема 1.1. Множество планов любой задачи линейного программирования является выпуклым (если оно не пусто). Определение 7. Непустое множество планов задачи линейного программирования называется многогранником реше­ний, а всякая угловая точка многогранника решений — вершиной. Сформулируем второе свойство задач ЛП. Теорема 1.2. Если задача линейного программирования имеет оптимальный план, то экстремальное значение целевая функция задачи принимает в одной из вершин многогранника решений. Если экстремальное значение целевая функция прини­мает более чем в одной вершине, то она принимает его на ребре (грани), содержащем эти вершины. Теорема 1.3. Если система векторов Р₁. Р_m() ли­нейно независима и такова, что х₁Р₁₊. + х_mР_m=Р₀, где все х_j>= 0, то точка х = (х,, х₂. х_т,0. 0) является верши­ной многогранника решений. Теорема 1.4. Если х = (х,,х₂. х_п) — вершина многогран­ника решений, то векторы Р_j , соответствующие положительным х_j > 0, линейно независимы.

Источник