Задачи ЛП и методы их решения

249

3. ПРИМЕР ВЫПОЛНЕНИЯ КОНТРОЛЬНОЙ РАБОТЫ

СЫКТЫВКАРСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ФИНАНСОВО-ЭКОНОМИЧЕСКИЙ ФАКУЛЬТЕТ

Шифр 20005339 домашний адрес г. Сосногорск, -й микрорайон, д. , корпус , кв. .

Сыктывкар 2000

251

Структура всех трех ограничений одинакова:

Теперь остается выразить полный расход материала через выбранные неизвестные

х1 и х2. Так, расход материала первого сорта на производство изделия А составит 8х1 единиц, а на производство изделия В – 7х2 соответственно (см. первую строку таблицы). В сумме это даст полный расход материала первого сорта, и ограничение примет вид линейного неравенства

8х1 + 7х2 ≤ 417

Аналогично запишутся ограничения по второму и третьему сорту материала

14х1 + 8х2 ≤ 580

7х1 + х2 ≤ 591

Объединяя их в систему, получим

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

х1 ≥ 0, х2 ≥ 0

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

f (x1,x2) = 5x1 + 5 x2 → max

х1 ≥ 0, х2 ≥ 0

Решим задачу графическим способом.

Изобразим на плоскости систему координат и рассмотрим ограничения неотрицательности.

Неравенство х1 ≥ 0 – определяет полуплоскость, в которой все точки имеют неотрицательную первую координату. Неравенству х2 ≥ 0 соответствует полуплоскость, где вторая координата каждой точки неотрицательна. Таким образом, системе неравенств х1 ≥ 0, х2 ≥ 0

соответствует 1-я четверть.

252

Строим множество точек, соответствующее множеству решений системы ограничений, заменяя неравенства уравнениями и строя прямые, соответствующие этим уравнениям.

Решая первое уравнение, получим прямую (I) с точками пересечения осей А и В.

8х1 + 7х2 = 417

х1 = 0, х2 = 60 – точка А пересечения с осью ОХ2

х2 = 0, х1 = 52 – точка В пересечения с осью ОХ1

Построенная прямая разбивает плоскость на две полуплоскости. Для выбора плоскости, соответствующей нашему неравенству, возьмем на плоскости точку с известными координатами, не лежащую на прямой (пусть это будет точка (0,0) – начало координат). Подставим координаты этой точки в неравенство 8 0 + 7 0 ≤ 417, 0 ≤ 417. Получилось верное числовое неравенство. Значит, полуплоскость содержит выбранную для проверки точку.

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

Пересекая решение второго (точки С и D, прямая II) неравенства с предыдущим множеством, получаем четырехугольник OAMD.

Решив третье (точки E и F, прямая III) неравенство, приходим к выводу, что при пересечении с предыдущим множеством решений, четырехугольник OAMD целиком содержится в полуплоскости (III) 7x1 + x2 ≤ 591.

X2

E

C

A

M

253

Окончательно множество решений ЗЛП представляет собой четырехугольник OAMD.

X2

A

M

X1

O D

Найдем в множестве решений точку, которая доставляет максимум целевой функции f (x1,x2) = 5x1 + 5 x2 . Эта точка будет соответствовать оптимальному решению.

Для этого построим нормальный вектор N = (5,5). Если придать f какое-либо конкретное значение f0, то прямая f (x1,x2) = f0 будет проходить перпендикулярно N.

Перемещая прямую в направлении N (задача на MAX), по которому значение целевой функции возрастает, находим последнюю точку пересечения прямой и множества решений. Эта точка (A) и будет искомым оптимальным решением. Определяем ее компоненты как координаты точки пересечения 1-й прямой и оси ox2 .

Максимальная прибыль от реализации всей продукции видов А и В составит 297 6 7

первого сорта будут израсходованы полностью (первое ограничение выполняется как ра-

254

ЗАДАНИЕ 2

УСЛОВИЕ.

Имеются три пункта поставки однородного груза A1 , A2 , A3 и пять пунктов B1 , B2 ,

B3 , B4 , B5 потребления этого груза. На пунктах поставки находится груз соответственно в количестве a1 , a2 и a3 т. В пункты потребления B1 , B2 , B3 , B4 и B5 требуется доставить соответственно b1 , b2 , b3 , b4 и b5 т. груза. Цены перевозок (стоимости провоза еди-

ницы груза) между пунктами поставки и пунктами потребления приведены в следующей матрице-таблице:

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

Изобразить оптимальный план перевозок в виде графа.

РЕШЕНИЕ.

Построим математическую модель транспортной задачи (ТЗ) в виде задачи линейного программирования. Исходя из того, что план перевозок определяется указанием количества перевозимого груза по каждой коммуникации, обозначим через неизвестные хij количество перевозимой продукции от поставщика с номером i к потребителю с номером j

(объем перевозки). В нашем случае таких неизвестных будет 3 × 5 = 15 (х11, х12, х13, х14, х15,

х21, х22, х23, х24, х25, х31, х32, х33, х34, х35).

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

255

ножить на цену перевозки и просуммировать полученные величины по всем коммуника-

циям.

f = 20х11+10х12+13х13+13х14+18х15+27х21+19х22+20х23+16х24+22х25+26х31+17х32+19х33+21х34+32х35→min

Сформулируем ограничения.

1.Условия полного вывоза продукции от каждого поставщика (таких условий будет столько, сколько имеется поставщиков. У нас – 3).

2.Условия полного удовлетворения потребностей каждого потребителя (Число уравнений равно числу потребителей. У нас – 5). Таким образом, в ТЗ будет (m+n) ограничений (у нас 3+5=8).

Запишем ограничения первой группы:

х11 + х12 + х13 + х14 + х15 = 200

х21 + х22 + х23 + х24 + х25 = 300

х31 + х32 + х33 + х34 + х35 = 250

Ограничения второй группы можно сформулировать в виде:

х11 + х21 + х31 = 210

х12 + х22 + х32 = 150

Окончательно, учитывая ограничения неотрицательности

Запишем математическую постановку ТЗ в виде задачи линейного программирова-

ния:

f = 20х11+10х12+13х13+13х14+18х15+27х21+19х22+20х23+16х24+22х25+26х31+17х32+19х33+21х34+32х35→min

Для решения ТЗ используем метод потенциалов.

Подсчитаем стоимость полученного плана. Для этого умножим объем перевозок в заполненных клетках на цены перевозок в них:

f0СЗУ = 200 20 + 10 27 + 150 19 + 120 20 + 20 16 + 115 21 + 135 23 = 15360

Шаг 1. Проверка текущего плана на оптимальность

Признаком того, что текущий план перевозок является оптимальным, служит усло-

вие

(Y1) ui + vj – cij ≤ 0,

257

Которое должно выполняться для всех клеток таблицы. Неизвестные здесь величи-

ны ui и vj (называемые потенциалами) определяются из условий

Переходим к проверке условий оптимальности (Y2). Достаточно проверять их для незаполненных клеток, так как из (Y1) следует, что для клеток заполненных эти условия выполняются как равенства. Для проверки берется незаполненная клетка, складываются соответствующие ей потенциалы и из них вычитается цена перевозки в данной клетке. Если полученное число отрицательное (или ноль), то оптимальность в данной клетке не нарушается. Если же в таблице встретилась хотя бы одна клетка, для которой это число положительное, тогда решение не является оптимальным и может быть улучшено. Прове-

Условие оптимальности нарушено в клетках (1,2), (3,1), (3,2) и (3,3). Следовательно,

имеющийся план перевозок можно улучшить.

Улучшение плана происходит путем назначения перевозки θ > 0 в ту клетку (i,j)

таблицы 1, в которой нарушилось условие оптимальности. Но назначение ненулевой перевозки нарушает условия баланса вывоза продукции от поставщика к i (вывозит весь запас и еще плюс θ > 0) и условия баланса привоза продукции к потребителю j (получает все что можно и еще плюс θ > 0 ). Условия баланса восстанавливают путем уменьшения вывоза от i-поставщика к какому-то другому потребителю j (уменьшают на θ перевозку в какой-то заполненной клетке (i,j) строки i). При этом нарушается баланс привоза продукции к потребителю j (получает на θ меньше, чем ему требуется). Восстанавливают баланс в столбце j, тогда он нарушается в некоторой строке i и т.д. до тех пор, пока цикл перемещения перевозок не замкнется на клетке, в которой нарушилось условие оптимальности.

Внашем примере нарушена оптимальность в клетке (1,2). Назначим в нее перевозку

θ=150. Уменьшаем на θ перевозку в заполненной клетке (1,1). В заполненной клетке (2,1) увеличиваем перевозку на θ и уменьшаем на θ перевозку в клетке (2,2). Цикл пере-

возок построен. Новый (улучшенный) план перевозок представлен в таблице 2.

f1СЗУ = 50 20 + 150 10 + 160 27 + 120 20 + 20 16 + 115 21 + 135 23 = 15060