Лекция 3. Решение злп со многими переменными графическим методом

 

Оглавление

 

§ 1. Область применения графического метода решения ЗЛП

Решение ЗЛП графическим методом в трехмерном пространстве

ЗЛП со многими переменными, сводимые к задаче с двумя переменными

 

§ 2. Алгоритм решения ЗЛП со многими переменными графическим методом

Описание алгоритма

Пример

 

§ 1. Область применения графического метода решения ЗЛП

 

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

Графический метод можно использовать и при решении ЗЛП в трехмерном пространстве. Пусть, например задача линейного программирования имеет вид:

F=c ₁ x ₁ +c ₂ x ₂ +c ₃ x ₃ max

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

a ₁₁ x ₁ +a ₁₂ x ₂ +a ₁₃ x ₃ b ₁

a ₂₁ x ₁ +a ₂₂ x ₂ +a ₂₃ x ₃ b ₂

и при условии

x ₁ 0, x ₂ 0, x ₃ 0.

В пространстве любое линейное уравнение задает некоторую плоскость, а линейное неравенство – часть пространства с какой-либо стороны от граничной плоскости. Таким образом, множество допустимых решений ЗЛП в трехмерном пространстве образует пространственный многогранник R (Рис.1).

Линии уровня целевой функции также являются плоскостями, которые пересекают многогранник R.

F 0

Рис.1.

Перемещая нулевую линию уровня параллельно себе по направлению вектора-градиента с координатами (c ₁, c ₂, c ₃) до последней точки многогранника решений, мы находим оптимальное решение.

Однако графическое представление ЗЛП уже в трехмерном пространстве затруднительно, а в пространствах размерности больше трех изобразить графически ЗЛП вообще невозможно.

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

 

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

Для того, чтобы задачу линейного программирования со многими переменными можно было бы свести к задаче с двумя переменными, необходимо, чтобы ее система ограничений содержала не только неравенства, но и уравнения. При этом, число линейно независимых уравнений l должно быть на 2 меньше, чем число неизвестных n, т.е. n – l = 2.

Если ЗЛП записана в каноническом виде (т.е. ее система ограничений состоит только из уравнений), то ее можно решить графическим методом при том же условии: если число неизвестных n и число линейно независимых уравнений m связаны соотношением: n – m = 2.

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

и

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

Таким образом, если в системе ограничений ЗЛП число линейно независимых уравнений на 2 меньше, чем число неизвестных, то ее можно решить графически.

§2. Алгоритм решения ЗЛП со многими переменными графическим методом

 

Допустим, что задачу линейного программирования со многими переменными можно свести к задаче с двумя переменными, т.е в ее системе ограничений число линейно независимых уравнений на 2 меньше, чем число неизвестных. Тогда, придерживаемся следующей схемы действий:

1) преобразовывая эти линейно независимые уравнения, выражаем п –2 переменные через какие-то две, например х ₁ и х ₂;

2) полученные выражения подставляем во все остальные ограничения системы, в условия неотрицательности и в целевую функцию – получаем ЗЛП с двумя переменными (х ₁ и х ₂);

3) решаем задачу графическим методом и находим оптимальный план Х = (х ₁*, х ₂*);

4) подставляем найденные значения оптимального плана х ₁* и х ₂* в выражения для остальных переменных и получаем окончательное решение.

Рассмотрим применение этого алгоритма на примере.

 

Пример. Двум погрузчикам разной мощности за 24 часа нужно погрузить на первой площадке 230 т., на второй 168 т. Первый погрузчик на первой площадке может погрузить 10 т. в час, на второй – 12 т. Второй – на каждой площадке может погрузить по 13 т. в час. Стоимость работ, связанных с погрузкой 1 т. первым погрузчиком на первой площадке составляет 8 р., на второй площадке – 7 р. Стоимость погрузки вторым погрузчиком на первой площадке составляет 12 р., на второй – 13 р.

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

Решение.

Для начала составим математическую модель данной задачи.

Обозначим:

х ₁ – объем работ (в тоннах) 1-го погрузчика на первой площадке;

х ₂ – объем работ (в тоннах) 1-го погрузчика на второй площадке;

х ₃ – объем работ (в тоннах) 2-го погрузчика на первой площадке;

х ₄ – объем работ (в тоннах) 2-го погрузчика на второй площадке.

Тогда, из условия, что «первый погрузчик на первой площадке может погрузить 10 т. в час, на второй – 12 т. в час» время его работы на первой площадке равно часов, на второй площадке – равно часов; из условия, что «второй погрузчик на каждой площадке может погрузить по 13 т. в час» время работы второго погрузчика на первой площадке равно часов, на второй площадке – равно часов.

Часть условий задачи перенесем в таблицу (Таблица 1).

Таблица 1.

	Первая площадка	Вторая площадка	Ограничение по времени
Объем работ, тонны	Время, часы	Объем работ, тонны	Время, часы
1-й погрузчик	х 1		х 2		не более 24 часов
2-й погрузчик	х 3		х 4		не более 24 часов
Задание

 

По условию, погрузчики работают 24 часа, т.е. для каждого погрузчика сумма времени его работы на обеих площадках не превосходит 24 часов, тогда можно записать ограничения:

Из условия, что «первый погрузчик на второй площадке должен работать не более 16 часов», получим следующее ограничение:

Кроме того, по условию «нужно погрузить на первой площадке 230 т., на второй 168 т.», следовательно:

Целевую функцию запишем на основании условия задачи, что «стоимость работ, связанных с погрузкой 1 т. первым погрузчиком на первой площадке составляет 8 р., на второй площадке – 7 р. Стоимость погрузки вторым погрузчиком на первой площадке составляет 12 р., на второй – 13 р.»:

К этому необходимо добавить условие неотрицательности:

 

Итак, математическая модель задачи имеет вид:

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

В системе ограничений есть l = 2 линейно независимых уравнения и n = 4 переменных, тогда n – l = 4 – 2 = 2, следовательно, эту задачу можно решить графическим методом.

1. Из уравнения выразим х ₃:

Из уравнения выразим х ₄:

2. Подставим эти выражения в систему ограничений:

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

в целевую функцию:

После арифметических преобразований, исключения избыточных условий и замены целевой функции Z = – F получим ЗЛП с двумя переменными:

3. Графическое решение задачи представлено на рисунке (Рис.2).

Оптимальный план – точка пересечения 1-ой и 4-ой прямых, т.е.

,

откуда Х _опт. = (100, 168), Z _max = – 3536.

4. Для определения остальных переменных, подставим значения и в уравнения: и , получим:

.

Таким образом, оптимальный план задачи равен Х _опт. = (100, 168, 130, 0).

Для определения значения F _min воспользуемся свойством

min F = – max (– F).

В нашем случае – F = Z, следовательно F _min= – Z_max = – (–3536) = 3536.

Рис.2.

 

Итак, по оптимальному плану первый погрузчик должен погрузить 100 т. на первой площадке и 168 т. на второй, второму погрузчику надлежит погрузить 130 т. на первой площадке. Стоимость всех работ составит 3536 р.

 

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