ЛАБОРАТОРНАЯ РАБОТА 3 ПРИМЕНЕНИЕ МЕТОДОВ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ ДЛЯ МОДЕЛИРОВАНИЯ И РЕШЕНИЯ ПРОИЗВОДСТВЕННЫХ ЗАДАЧ

Цельработы

Изучить теорию и методы решения задач линейного программирования; приобрести навыки построения моделей линейного программирования и решения задач линейного программирования на ЭВМ.

Краткиетеоретическиесведения

Методы линейного программирования (ЛП) оказались весьма эффективными для решения задач из различных областей человеческой деятельности. Слово «программирование» понимается как планирование, и это определяет характер рассматриваемых приложений. Основные идеи линейного программирования возникли во время Второй мировой войны в связи с поиском оптимальных стратегий при ведении военных операций. С тех пор они нашли широкое применение в промышленности, торговле и в управлении как в местных, так и в государственных масштабах. Этими методами можно решить многие задачи, связанные с эффективным использованием ограниченных ресурсов.

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

Фирма производит две модели (А и В) сборных книжных полок. Их производство ограничено наличием сырья (высококачественных досок) и временем машинной обработки. Для каждого изделия модели А требуется 3 м2 досок, а для изделия модели В – 4 м2. Фирма может получить от своих поставщиков до 1 700 м2 досок в неделю. Для каждого изделия модели А требуется 12 мин машинного времени, а для изделия модели В – 30 мин. В неделю можно использовать 160 ч машинного времени.

Сколько изделий каждой модели следует фирме выпускать в неделю, если каждое изделие модели А приносит 2 дол. прибыли, а каждое изделие модели В – 4 дол. прибыли?

Чтобы сформулировать эту задачу математически, обозначим через x1 количество выпущенных за неделю полок модели A, а через x2 – количество выпущенных полок модели В. Задача состоит в том, чтобы найти наилучшие значения x1 и x2. Очевидно, наилучшими для данной задачи являются

Моделирование процессов и объектов в металлургии. Лаб. практикум

-37-

ЛАБ. Р. 3. ПРИМЕНЕНИЕ МЕТОДОВ ЛИНЕЙНОГО ПРОГР-Я ДЛЯ МОДЕЛИРОВАНИЯ И РЕШ-Я ПРОИЗВОДСТВЕННЫХ ЗАДАЧ

Краткие теоретические сведения

такие значения, которые максимизируют еженедельную прибыль. Ежене-

дельная прибыль составляет Р = 2x1 + 4x2.

Поскольку x и x2 выражают еженедельный объем выпускаемых изделий, то они не могут быть отрицательны, т.е.

x1 ≥ 0, x2 ≥ 0.

(3.1)

Теперь ограничения на наличие досок и машинное время могут быть записаны следующим образом:

для досок –

3 x1 + 4x2 ≤ 1 700,

(3.2)

для машинного времени –

2x1 + 5x2 ≤ 1 600.

(3.3)

Следовательно, задача состоит в том, чтобы найти значения x1 и x2, удовлетворяющие условиям неотрицательности (3.1) и ограничениям типа неравенства (3.2), (3.3) и максимизирующие функцию Р.

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

(рис. 3.1).

Условия неотрицательности позволяют ограничиться рассмотрением положительного квадранта. Границы определяются прямыми

3x1 + 4x2 = 1 700,

2x1 + 5x2 = 1 600.

Моделирование процессов и объектов в металлургии. Лаб. практикум

-38-

ЛАБ. Р. 3. ПРИМЕНЕНИЕ МЕТОДОВ ЛИНЕЙНОГО ПРОГР-Я ДЛЯ МОДЕЛИРОВАНИЯ И РЕШ-Я ПРОИЗВОДСТВЕННЫХ ЗАДАЧ

Краткие теоретические сведения

Рис. 3.1. Геометрическая интерпретация задачи ЛП

Стрелка на каждой границе указывает, с какой стороны прямой выполняется ограничение. Заштрихованная область OАВС, содержащая точки, для которых соблюдены условия (3.2) и (3.3), является допустимой. Задача состоит в том, чтобы найти точку максимума функции Р.

Штриховыми линиями изображены две линии уровня функции Р со значениями, соответственно, 0 и 800, обозначенные a и b. Ясно, что значение функции Р возрастает по мере того, как линии уровня удаляются от начала координат в положительном квадранте. Действительно, вектор градиента

		∂P		∂P
	grad P =		,			, т.е. вектор с компонентами (2, 4), указывающий направ-
		∂x1		∂x2

ление возрастания функции Р, перпендикулярен линиям уровня и направлен в сторону, противоположную началу координат.

Линией уровня с наибольшим значением функции Р, имеющей хотя бы одну точку с допустимой областью, является прямая c, проходящая через вершину В; на ней Р принимает значение 1 400. Точка В, в которой x1 = 300, x2 = 200, соответствует оптимальному решению задачи. На данном примере показано, как возникают задачи линейного программирования на практике и как их можно решить, используя графический метод.

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

Моделирование процессов и объектов в металлургии. Лаб. практикум

-39-

ЛАБ. Р. 3. ПРИМЕНЕНИЕ МЕТОДОВ ЛИНЕЙНОГО ПРОГР-Я ДЛЯ МОДЕЛИРОВАНИЯ И РЕШ-Я ПРОИЗВОДСТВЕННЫХ ЗАДАЧ

Краткие теоретические сведения

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

Задача линейного программирования (ЗЛП) в общей постановке состоит в отыскании точек минимума или максимума линейной функции

z = c1x1 + c2x2 + . . . + cnxn

от n вещественных переменных x1, x2, …, xn на допустимом множестве Х Rn точек, удовлетворяющих условиям

a11 x1 + a12 x2 + ... + a1n xn ≥ b1,

a21 x1 + a22 x2 + ... + a2 n xn ≥ b2,

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . (3.4)

al1 x1 + al 2 x2 + ... + al n xn ≥ bl,

al +1,1 x1 + al +1,2 x2 + ... + al +1,n xn = bl+1,

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

am1 x1 + am 2 x2 + ... + am n xn = bm (m ≥ l),

и условиям неотрицательности

xs ≥ 0,	xs	≥ 0, …,	xs	≥ 0	(1 ≤ k ≤ n).	(3.5)
1		2		k

Значения bi, cj, aij предполагаются известными. Каждая точка допустимого множества X называется допустимой точкой или допустимым ре-

шением.

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

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

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

z = c1x1 + c2x2 + . . .

+ cnxn

(3.6)

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

Моделирование процессов и объектов в металлургии. Лаб. практикум

-40-

ЛАБ. Р. 3. ПРИМЕНЕНИЕ МЕТОДОВ ЛИНЕЙНОГО ПРОГР-Я ДЛЯ МОДЕЛИРОВАНИЯ И РЕШ-Я ПРОИЗВОДСТВЕННЫХ ЗАДАЧ

Краткие теоретические сведения

a11x1 + a12 x2 +…+ a1n xn = b1,

a21x1 + a22 x2 +…+ a2n xn = b2 ,
…………………………………..	(3.7)
am1x1 + am2 x2 +…+ amn xn = bm ,
x1 ≥ 0, x2 ≥ 0, …, xn ≥ 0.	(3.8)

Эти ограничения можно записать в матричной форме:

Ax = b , x ≥ 0 ,

где A − матрица ранга m, m < n; b − вектор правых частей; x − вектор переменных;

a

a

…

a

b1

x

11

12

1n

1

a21

a22

… a2n

b2

x2

A =

b =

,

x =

…… …… …… …

,

.

am1

am2

… amn

bm

xm

При приведении задачи к канонической форме используют следующие правила.

1.Максимизация целевой функции z равносильна минимизации целевой функции −z.

2.Ограничение в виде неравенства преобразуется в равенство добавлением новой неотрицательной переменной к левой части неравенства. Новая переменная x5 неотрицательна.

3.Если переменная xk может принимать значения любого знака, то

она заменяется разностью двух неотрицательных переменных: xk = x'k − x"k ,

где x'k ≥ 0, x"k ≥ 0.

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

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

Допустимое множество Х общей ЗЛП образует так называемое многогранное множество. Каждое из равенств (3.4), (3.5) задает гиперплоскость в Rn, а каждое из неравенств определяет полупространство в Rn, ограниченное соответствующей гиперплоскостью. Если множество X непусто, то оно выпукло т.е. оно содержит отрезок прямой, соединяющей две его любые точки.

Моделирование процессов и объектов в металлургии. Лаб. практикум

-41-

ЛАБ. Р. 3. ПРИМЕНЕНИЕ МЕТОДОВ ЛИНЕЙНОГО ПРОГР-Я ДЛЯ МОДЕЛИРОВАНИЯ И РЕШ-Я ПРОИЗВОДСТВЕННЫХ ЗАДАЧ

Краткие теоретические сведения

Другими словами, из того, что х X и у X, следует, что λ х + (1 − λ)х X для любого λ, 0 ≤ λ ≤ 1.

Ограниченное многогранное множество называют многогранником. Точка х0 выпуклого многогранного множества М называется его угловой

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

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

граммирования.

Обозначая через A1 , …, An столбцы матрицы А, т.е.

a1 j

a

A

j

=

2 j

,

j =1, 2, …, n,

a

mj

систему (3.7) можно записать в виде

(3.9)

A1 x1 + A2 x2 + … + An xn = b .

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

(m ≤ n). Действительно, если это не так, то либо система уравнений Ах = b несовместна (и, значит, множество Х пусто), либо содержит избыточные (линейно зависимые) уравнения. Соотношение (3.9) является разложением век-

тора b по векторам Ai , i = 1, 2, …, n, а xi – коэффициентами этого разложе-

ния. Такое разложение получило название второй геометрической интер-

претации ЗЛП.

Точка x(0) = (x1(0), …, xn(0)) называется опорной точкой допустимого множества Х (базисным решением), если существуют номера j1, …, jm, 1 ≤ jk

≤ n, такие, что система векторов Aj1, …, Ajm линейно независима и

Aj1 x(0)j1 + Aj2 x(0)j2 +…+ Ajm x(0)jm = b ,

xjk(0) ≥ 0, k = 1, 2, …, m, xs(0) = 0, если s ≠ jk .

Система векторов { Aj1, …, Ajm} называется базисом опорной точки (х(0)), а переменные xj1, …, xjm – базисными переменными. Переменные, которые не входят в список базисных переменных, называются небазисными или свобод-

ными.

Моделирование процессов и объектов в металлургии. Лаб. практикум

-42-