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

Учреждение образования РБ

«Брестский государственный университет им. А.С.Пушкина»

Реферат на тему:

Графический способ решения задач

линейного программирования

Брест 2010

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

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

Найти минимальное значение функции

(1.1) Z = С₁х₁+С₂х₂

При

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

(1.2) a₂₁x₁ + a₂₂x₂ b₂

. . . . . . . .

a_M1x₁ + a_M2x₂ b_M

(1.3) х₁ 0, х₂ 0

Допустим, что система (1.2) при условии (1.3) совместна и ее многоугольник решений ограничен. Каждое из неравенств (1.2) и (1.3), как отмечалось выше, определяет полуплоскость с граничными прямыми: a_i1x₁ + a_i2x₂ + a_i3x₃ = b_i,(i = 1, 2, ..., n), х₁=0, х₂=0. Линейная функция (1.1) при фиксированных значениях Z является уравнением прямой линии: С₁х₁ + С₂х₂ = const. Если построить многоугольник решений системы ограничений (1.2) и график линейной функции (1.1) при Z = 0, то тогда поставленной задаче линейного программирования можно дать следующую интерпретацию. Найти точку многоугольника решений, в которой прямая С₁х₁ + С₂х₂ = const опорная и функция Z при этом достигает минимума.

Пример решения задачи графическим способом

ЗАДАНИЕ. Колхоз имеет возможность приобрести не более 19 трехтонных автомашин и не более 17 пятитонных. Отпускная цена трехтонного грузовика - 4000 руб., пятитонного - 5000 руб. Колхоз может выделить для приобретения автомашин 141 тысяч рублей. Сколько нужно приобрести автомашин, чтобы их суммарная грузоподъемность была максимальной?

РЕШЕНИЕ. Составим математическую модель задачи. Пусть x1 - количество трехтонных

автомашин, x2 - количество пятитонных автомашин. По условию 0 ? x1? 19, 0 ? x2 ? 17. На приобретение грузовиков необходима сумма 4000x1+ 5000 x2, при этом по условию она не должна превосходить 141 000, т.е. 4000x1+ 5000 x2 ? 141000. Теперь введем целевую функцию - грузоподъемность автомашин, которая составляет 3x1+ 5 x2.

Таким образом, задача заключается в следующем: максимизировать целевую функцию

f = 3x1+ 5 x2 > max (1)

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

4000x1+ 5000 x2 ? 141000, (*)

0 ? x1 ? 19, 0 ? x2 ? 17. (**)

Построим область допустимых решений задачи, ограниченную прямыми:

4000x1+ 5000 x2 = 141000, (I) x1 = 19, (II) x2 = 17. (III)

Множество точек, определяемых неравенствами (*), (**) - многоугольник АВСДО, в одной из вершин которого достигается максимум функции. Построим линию уровня 3 x1 + 5 x2 =0 и вектор градиента (3, 5). Будем передвигать линию уровня, пока не выйдем из многоугольника, что произойдет в точке В с координатами (14, 17). В этой точке функция принимает максимальное значение 127. Чтобы достичь этого значения грузоподъемности, нужно приобрести 14 трехтонных грузовиков и 17 пятитонных.

Симплекс-метод

Симплекс-метод -- алгоритм решения оптимизационной задачи линейного программирования путём перебора вершин выпуклого многогранника в многомерном пространстве. Метод был разработан американским математиком Джорджем Данцигом (George Dantzig) в 1947 году.

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

Заметим, что каждое из линейных неравенств на переменные ограничивает полупространство в соответствующем линейном пространстве. В результате все неравенства ограничивают некоторый многогранник (возможно, бесконечный), называемый также полиэдральным конусом. Уравнение W(x) = c, где W(x) -- максимизируемый (или минимизируемый) линейный функционал, порождает гиперплоскость L(c). Зависимость от c порождает семейство параллельных гиперплоскостей. Тогда экстремальная задача приобретает следующую формулировку -- требуется найти такое наибольшее c, что гиперплоскость L(c) пересекает многогранник хотя бы в одной точке. Заметим, что пересечение оптимальной гиперплоскости и многогранника будет содержать хотя бы одну вершину, причем, их будет более одной, если пересечение содержит ребро или k-мерную грань. Поэтому максимум функционала можно искать в вершинах многогранника. Принцип симплекс-метода состоит в том, что выбирается одна из вершин многогранника, после чего начинается движение по его ребрам от вершины к вершине в сторону увеличения значения функционала. Когда переход по ребру из текущей вершины в другую вершину с более высоким значением функционала невозможен, считается, что оптимальное значение c найдено.

Переход от одной вершины к другой

Рассмотрим следующую задачу линейного программирования:

Теперь поставим эту задачу в эквивалентной усиленной форме. Необходимо максимизировать Z, где:

Здесь x -- переменные из исходного линейного функционала, xs -- новые переменные, дополняющие старые таким образом, что неравенство переходит в равенство, c -- коэффициенты исходного линейного функционала, Z -- переменная, которую необходимо максимизировать. Полупространства х 0 и х_s 0 в пересечении образуют многогранник, представляющий множество допустимых решений. Разница между числом переменных и уравнений дает нам число степеней свободы. Проще говоря, если мы рассматриваем вершину многогранника, то это число ребер, по которым мы можем продолжать движение. Тогда мы можем присвоить этому числу переменных значение 0 и назвать их «непростыми». Остальные переменные при этом будут вычисляться однозначно и называться «простыми». Полученная точка будет вершиной в пересечении соответствующих непростым переменным гиперплоскостей. Для того, чтобы найти т. н. начальное допустимое решение (вершину, из которой мы начнем движение), присвоим всем изначальным переменным x значение 0 и будем их считать непростыми, а все новые будем считать простыми. При этом начальное допустимое решение вычисляется однозначно: X_si=b_i.

Алгоритм

Теперь приведем шаги алгоритма. На каждом шаге мы будем менять множества простых и непростых векторов (двигаться по ребрам), и матрица будет иметь следующий вид:

где cB -- коэффициенты вектора c соответствующие простым переменным (переменным xs соответствуют 0), B -- столбцы [AE] , соответствующие простым переменным. Матрицу, образованную оставшимися столбцами обозначим D. Почему матрица будет иметь такой вид поясним в описании шагов алгоритма.

Первый шаг.

Выбираем начальное допустимое значение, как указано выше. На первом шаге B -- единичная матрица, так как простыми переменными являются xs. cB -- нулевой вектор по тем же причинам.

Покажем, что в выражении только непростые переменные имеют ненулевой коэффициент. Заметим, что из выражения Ax+xs=b простые переменные однозначно выражаются через непростые, так как число простых переменных равно числу уравнений. Пусть x ' -- простые, а x ' ' -- непростые переменные на данной итерации. Уравнение Ax+xs=b можно переписать, как Bx '+Dx ' '=b. Умножим его на B ? 1 слева: x' + B ? 1Dx'' = B ? 1b. Таким образом мы выразили простые переменные через непростые, и в выражении B ? 1Ax + B ? 1xs, эквивалентному левой части равенства, все простые переменные имеют единичные коэффициенты. Поэтому, если прибавить к равенству Z ? cTx = 0 равенство , то в полученном равенстве все простые переменные будут иметь нулевой коэффициент -- все простые переменные вида x сократятся, а простые переменные вида xs не войдут в выражение .

Выберем ребро, по которому мы будем перемещаться. Поскольку мы хотим максимизировать Z, то необходимо выбрать переменную, которая будет более всех уменьшать выражение .

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

Второй шаг

Теперь необходимо понять, какая простая переменная первой обратится в ноль по мере увеличения входящей переменной. Для этого достаточно рассмотреть систему:

При фиксированных значениях непростых переменных система однозначно разрешима относительно простых, поэтому мы можем определить, какая из простых переменных первой достигнет нуля при увеличении входящей. Эту переменную назовем выходящей. Это будет означать, что мы натолкнулись на новую вершину. Теперь входящую и выходящую переменную поменяем местами -- входящая «войдет» в простую, а выходящая из них «выйдет» в непростые. Теперь перепишем матрицу B и вектор cB в соответствии с новыми наборами простых и непростых переменных, после чего вернемся ко второму шагу. x''

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

Пример решения задачи симплекс-методом

Начальные условия:

Y = 12X1 +X2 -2X3 > max

-2X1-X2 ? -10

2X1-X2-2X3 ? 8

-X1+X3 ? -2

Решение задачи:

Y = 0 - ( -12X1-X2+2X3 )

X4 = 10 - ( 2X1+X2 )

X5 = 8 - ( 2X1-X2-2X3 )

X6 = -2 - ( -X1+X3 )

Двойственный СМ - выводим X6 вводим X1

Выводим X5 вводим X6

Выводим X4 вводим X3

Итоговое значение Y = 58

Ответ: X = ( 5; 0; 1 ).

Итоговое количество проделанных итераций: 3

Транспортная задача

Алгоритм выполнения метода.

1. В каждой строке и каждом столбце распределительной таблицы вычислить разности между всеми парами элементов (C_ij) и выбрать минимальную.

2. Среди всех выбранных минимальных разностей C_ij выбрать максимальное значение и выделить соответствующий столбец (строку).

3. В выбранном столбце (строке) найти минимальное значение C_ij и назначить необходимую перевозку, ориентируясь на наличие запасов (a_i) данного поставщика (A_ij) и потребностей (b_j) данного потребителя (B_ij).

4. Вычеркнув соответствующую строку (столбец), т.е. удалив из дальнейших расчетов поставщика (потребителя), запасы которого (потребности) исчерпаны, повторить заново алгоритм (1-4) до полного составления плана перевозок.

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

Найденное исходное опорное решение проверяется на оптимальность методом потенциалов по следующему критерию: если опорное решение транспортной задачи является оптимальным, то ему соответствует система m+n действительных чисел u_i и v_j, удовлетворяющих условиям u_i+v_j=c_ij для занятых клеток и u_i + v_j -c_ij ? 0 для свободных клеток.

Числа u_i и v_j называют потенциалами. В распределительную таблицу добавляют строку v_j и столбец u_i.

Потенциалы u_i и v_j находят из равенства u_i + v_j = c_ij, справедливого для занятых клеток. Одному из потенциалов дается произвольное значение, например u₁ = 0, тогда остальные потенциалы определяются однозначно. Так, если известен потенциал u_i, то v_j=c_ij-u_i; если известен потенциал v_j, то u_i=cij-vj.

Обозначим ?_ij=u_i+v_j-c_ij. Эту оценку называют оценкой свободных клеток. Если ?_ij?0, то опорное решение является оптимальным. Если хотя бы одна из оценок ?_ij>0, то опорное решение не является оптимальным и его можно улучшить, перейдя от одного опорного решения к другому.

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

где X_ij - объем поставок груза,

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

Xij?0,

Пользуясь методом потенциалов, (Фогеля) решаем задачу при k=д до получения оптимального решения. Признаком оптимальности является условие:

для незанятых клеток

и для занятых клеток,

где - потенциалы строк, столбцов распределительной таблицы.

Условие совместимости транспортной задачи запишется в виде

Значения aij и Bij определяются из условия

где определяются из систем уравнений

Значения k находятся в пределах k₁?k?k₂:

если существует хотя бы одно B_ij>0;

если все B_ij?0

если существует хотя бы одно B_ij>0;

если все B_ij?0.

Алгоритм решения.

1) Задачу решаем при конкретном значении параметра k=д до получения оптимального решения.

2) Определяем a_ij и B_ij.

3) Вычисляем значение параметра k.

Если k>д, производим перераспределение поставок и получаем новое оптимальное решение. Если k = д, то процесс решения окончен.

Пример решения транспортной задачи

ЗАДАНИЕ. Из трех холодильников Ai , i = 1,3, вмещающих мороженную рыбу в количествах i a т, необходимо последнюю доставить в пять магазинов j B , j = 1,5 в количествах j b т. Стоимости перевозки 1т рыбы из холодильника i A в магазин j B заданы в виде матрицы С=((с_ij)), 3x5.

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

А₁ =320, B₁=140,

A₂ =280, B₂=110,

A₃ =250, B₃=230,

B₁ =150, B₅=220

20 23 20 15 24

С = 29 15 16 19 29

6 11 10 9 8

РЕШЕНИЕ. Составим математическую модель задачи. Пусть x_ij - количество т рыбы, перевозимой из холодильника (поставщика) A_i в магазин (потребитель) B_j . Тогда задача заключается в минимизации общих транспортных расходов.

Задача имеет закрытый тип, т.к. запасы груза 320+280+250 = 850 т равны суммарным потребностям магазинов 150+140+110+230+220 = 850 т.

Составим опорный план по правилу минимального элемента.

Введем некоторые обозначения: A_i* - излишек нераспределенного груза от поставщика A_i, B_j* - недостача в поставке груза потребителю B_j.

Находим незанятую клетку с минимальным тарифом: (3,1). Помещаем туда меньшее из чисел A3*=250 и B1*=150.

Находим незанятую клетку с минимальным тарифом: (3,5). Помещаем туда меньшее из чисел A3*=100 и B5*=220.

Находим незанятую клетку с минимальным тарифом: (1,4). Помещаем туда меньшее из чисел A1*=320 и B4*=230.

Находим незанятую клетку с минимальным тарифом: (2,2). Помещаем туда меньшее из чисел A2*=280 и B2*=140.

Находим незанятую клетку с минимальным тарифом: (2,3). Помещаем туда меньшее из чисел A2*=140 и B3*=110. Находим незанятую клетку с минимальным тарифом: (1,5). Помещаем туда меньшее из чисел A1*=90 и B5*=120.

Находим незанятую клетку с минимальным тарифом: (2,5). Помещаем туда меньшее из чисел A2*=30 и B5*=30.

Пришли к таблице:

Транспортные расходы составят z = 12040.