Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

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




ТРАНСПОРТНАЯ ЗАДАЧА

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

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

Задача линейного программирования с ограничениями—равенствами носит название основной задачи линейного программирования (ОЗЛП).

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

Имеется ряд переменных

x1, x2,......, x n.

Требуется найти такие неотрицательные значения этих переменных, которые удовлетворяли бы системе линейных уравнений:

a11 x 1 + a12 x 2 +.... + a1n x n = b 1;

a21 x 1 + a22 x 2 +.... + a2n x n = b 2;

(2.1)

.......................... ….

 

am1 x 1 + am2 x 2 +.... + amn x n = b m,

и, кроме того, ОБРАЩАЛИ БЫ В МИНИМУМ линейную функцию

L = c1 x1 + c2 x2 + …….+ cn xn. (2.2)

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

L׳ = -- L = -- c1 x1 -- c2 x2 -- …….-- cn xn. (2.3)

Условимся называть д о п у с т и м ы м решение ОЗЛП любую совокупность переменных

x1 ≥ 0, x2 ≥ 0, ……, x n ≥ 0,

удовлетворяющую уравнениям (2,1).

О п т и м а л ь н ы м решением будем называть то из допустимых решений, при которым линейная функция (2.2)

обращается в минимум.

ОЗЛП необязательно должна иметь решение. Может оказаться, что уравнения (2.1) противоречат друг другу; может оказаться, что они имеют решение, но не в области отрицательных значений x1, x2,....., x n.

Тогда ОЗЛП не имеет допустимых решений.. Наконец, может оказаться, что допустимые значения ОЗЛП существуют, НО СРЕДИ НИХ НЕТ ОПТИМАЛЬНОГО: ФУНКЦИЯ L в области допустимых решений неограниченна снизу.

Вопрос о существовании неотрицательных значений x1, x2,....., x n, удовлетворяющих системе уравнений (2.1) рассматривается в специальном разделе математики – линейной алгебре.

 

2.3 Геометрическая интерпретация основной задачи линейного программирования

Рассмотрим пример 1. Найти max (2 x1 + 5 x2) = z при условиях x1 ≤ 400, x 2 ≤ 300,

x1 + x 2 ≤ 500, x1 ≥ 0, x 2 ≥ 0.

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

 

\

Рассмотрим целевую функцию f (x1, x2) = 2 x1 + 5 x2.

Пусть f (x1, x2) = 1000 = z1. График уравнения 2 x1 + 5 x2 = 1000 представляет собой прямую с отрезками на осях x1 = 500 единиц, а x2 = 200 единиц.

2 x1 / 1000 + 5 x2 / 1000 = x1 / 500 + x2 / 200 = 1.

При f (x1, x2) = 1500, получим прямую z2, имеющую уравнение

2 x1 / 1500 + 5 x2 / 1500 = x1 / 750 + x2 / 300 = 1.

Прямая z2 параллельна прямой z1, но расположена выше ее. Двигая прямую вверх параллельно самой себе, приходим к положению zmax, когда прямая и множество К будут иметь только одну общую точку А. Очевидно, что точка А (x1 = 200; x2 = 300) оптимальное решение, так как она лежит на прямой с максимально возможным значением zmax. Заметим, что эта точка оказалась крайней точкой множества К.

Пример 2. Задача линейного программирования с семью переменными

x1, x2, x3, x4, x5, x6, x7

имеет m = 5 уравнений – ограничений:

 

 

x1 -- x2 + x3 = 4;

2 x1 -- x2 -- x3 -- x4 = --5; (2.4)

x1 + x2 -- x5 = -- 4;

x2 + x6 = 5;

2 x1 -- 2 x2 -- x6 + 2 x7 = 7.

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

Решение. Выберем в качестве свободных переменных, например, x1 и x2 и выразим через них остальные (базисные) переменные: x3, x4, x5, x6, x7. Из первого уравнения имеем:

x3 = -- x1 + x2 + 4 (2.5)

Из третьего

х5 = x1 + x2 + 4.

 

Из четвертого:

х6 = -- x2 + 5. (2.6)

 

Подставляя (2.5) во второе уравнение(2.3) и (2.6) -- в последнее и разрешая относительно x4 , x7, имеем:

х4 = 3х1 -- 2х2 + 1;

 

х7 = --х1 + ½ х2 + 6.

 

Геометрическая интерпретация задачи представлена на рис. 2 (прямые x1 = 0, x2 = 0 – оси координат; остальные ограничивающие прямые x3 = 0, x4 = 0, x5 = 0, x6 = 0,и x7 = 0;

короткой штриховкой помечены допустимые полуплоскости -- условия неотрицательности переменных).

 

 

Как видно из расположения прямых и отмеченных полуплоскостей, допустимые решения для рассмотренной задачи существуют; они заполняют ОДР, которая на рис.2 показана закрашенной.

Далее найдем оптимальное решение ОЗЛП, обращающее в минимум линейную функцию семи неизвестных:

 

L = x1 -- x2 + 2x3 -- x4 -- 3x5 + x6 -- 2x7 (2.7)

Выше были указаны условия-ограничения (2.4)., которые были разрешены относительно базисных переменных x3, x4, x5, x6, x7, которые были выражены через свободные х1 и х2:

 

x3 = -- x1 + x2 + 4

х4 = 3х1 -- 2х2 + 1;

х5 = x1 + x2 + 4. (2.8)

 

х6 = -- x2 + 5.

х7 = --х1 + ½ х2 + 6.

 

Подставляя эти выражения в (2.7) и приводя подобные члены, имеем:

 

L = -- 5x1 -- 2x2 -- 12. (2.9)

Воспроизведем область допустимых решений, ранее построенную на рис. 2 (рис.3).

 

Отбрасывая свободный в (2.9), имеем:

L* = -- 5x1 -- 2x2.

 

Строим основную прямую L* = 0. Для этого откладываем отрезки γ2 = -- 2 по оси абсцисс и -- γ1 = 5 по оси ординат, проводим через точку В с координатами (--2, 5) прямую L* = 0 и отмечаем стрелками направление убывания L*. перемещая основную прямую параллельно самой себе в сторону убывания L*, наименьшее значение L* мы получим в точке А (наиболее удаленной от начала координат в направлении стрелок). Координаты этой точки х1*, х2* и дают оптимальное решение ОЗЛП. В точке А пересекаются две ограничивающие прямые: х6 = 0 и х7 = 0. Приравнивая нулю выражения для х6 и х7, получим два уравнения:

-- х2 + 5 = 0

--х1 + ½ х2 + 6 = 0

Решая их совместно, найдем х1* = 8,5; х2* = 5.

Подставляя эти значения в (2.9), найдем оптимальные значения базисных переменных: х3* = 0,5; х4* = 16,5; х5* = 17,5.

Что касается х6 и х7, то их оптимальные значения равны нулю: х6* = 0;

Х7* = 0.

Подставляя найденные оптимальные значения х1* и х2* в линейную функцию (2.9), найдем минимальное значение (оптимум) линейной функции L:

L = -- 5•8,5 -- 2• 5 -- 12 = --64,5.

Таким образом решаются задачи ОЗЛП в частном случае, когда m = n -- 2, при помощи геометрического построения.

 

2.4. Симплекс метод решения задачи

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

Геометрическая интерпретация при решении задач линейного программирования перестает быть пригодной для этой цели при числе свободных переменных n –m > 3, а затруднительной уже при n –m = 3.

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

Пусть в задаче имеется n переменных и m независимых линейных ограничений, заданных в форме уравнений. Известно, что оптимальное решение (если оно существует) достигается в одной из опорных точек (вершин ОДР), где по крайней мере k = n -- m из переменных равны нулю. Выберем какие-то k переменных в качестве свободных и выразим через них остальные m базисных переменных. Пусть, например, в качестве свободных выбраны первые k = n -- m переменных х12,..... х k, а остальные через них:

 

xk+1 = α k+1,1 x 1 + α k+1,2 x 2 +.....+ α k+1,k x k + β k+1,

xk+2 = α k+2,1 x 1 + α k+2,2 x 2 +.....+ α k+2,k x k + β k+2, (2.10)

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

x n = α n,1 x 1 + α n,2 x 2 +.....+ α n,k x k + β n.

 

Попробуем, что будет, если положить все свободные переменные х12,..... х k равными нулю:

х1 = 0, х2 = 0,....., х k = 0.

При этом получим:

x k=1 = β k+1, x k=2 = β k+2,...., x n = β n .

Это решение может быть допустимым или недопустимым. Оно допустимо, если все свободные члены неотрицательны. Предположим, что это условие выполнено. Тогда мы получили о п о р н о е р е ш е н и е. Но является ли оно оптимальным? Чтобы это проверить, выразим минимизируемую линейную функцию L через свободные переменные х12,..... х k:

L = γ0 + γ1 х 1 + γ2 х 2 +.... + γk х k. (2.11)

Очевидно, что при х1 = х2 =.....= х k = 0 L = γ0. Посмотрим, не можем ли мы улучшить решение, т.е. уменьшить функцию L, у в е л и ч и в а я какие-нибудь из переменных х12,..... х k (уменьшать мы их не можем, т.к. все они равны нулю, а отрицательные значения переменных недопустимы). Если все коэффициенты γ1, γ2,..... γ k в выражении (2.11) п о л о ж и т е л ь н ы, то, увеличивая какие-то из переменных х12,..... х k сверх нуля, мы не можем уменьшить L; следовательно найденное нами опорное решение является о п т и -м а л ьн ы м. Если же среди коэффициентов γ1, γ2,..... γ k в выражении (2.11) есть отрицательные, то, увеличивая некоторые из переменных х12,..... х k, а именно –те, коэффициенты при которых отрицательны, мы можем улучшить решение, т.е. уменьшить L.

Пример 3. Имеется задачалинейного программирования с ограничениями-неравенствами:

--5х1 -- х2 + 2х3 ≤ 2,

--х1 + х3 + х4 ≤ 5, (2.12)

--3х1 + 5 х2 ≤ 7.

Требуется минимизировать линейную функцию

L = 5х1 -- 2х3 .

Решение. Приводя неравенства к стандартному виду (≥ 0) и вводя добавочные переменные y1, y2, y3, переходим к условиям-равенствам:

y1 = 5х1 + х2 -- 2х3 + 2,

у2 = х1 -- х3 -- х4 + 5, (2.13)

у3 = 3х1 -- 5 х2 + 7.

Число переменных n = 7 на 4 превышает число уравнений m = 3. Значит, четыре переменных могут быть выбраны в качестве свободных.

Попробуем выбрать в качестве свободных переменных х1, х 2, х 3, х4 и положить их равными нулю. При этом получим опорное решение

х1 = х 2 = х 3 = х4 = 0; у1 = 2; у2 = 5; у3 = 7.

При этих значениях переменных L = 0.

Посмотрим, является ли это решение оптимальным? Нет! Потому что в выражении линейной функции L коэффициент при х 3 отрицателен. Значит, увеличивая х 3 , можно уменьшить L.

Попробуем увеличивать х 3 . Проследим по по уравнениям (2.13), опасно ли это для других переменных? Да, опасно для y1 и у2 -- в оба эти уравнения переменная х 3 с отрицательным коэффициентом, значит, при увеличении х 3 соответствующие переменные y1 и у2 могут стать отрицательными.

Посмотрим, какая из этих переменных y1 или у2 раньше обратится в нуль при увеличении х 3 . Очевидно, y1 ; она станет равной нулю при х 3 = 1, а у2 -- только при х 3 = 5.

Поэтому выбираем переменную y1 и вводим ее в число свободных вместо х 3 . Чтобы «переразрешить» систему (2.13) относительно х 3 , у2 , у3 , поступим следующим образом. Разрешим первое уравнение (2.13) относительно новой базисной переменной х 3 :

х 3 = 5/2 х1 + ½ х2 -- ½ y1.

Это выражение вместо х 3 подставим во второе уравнение; получим

у2 = -- 3/2 х1 -- ½ х2 + ½ у1 --х4 + 4.

Что касается третьего уравнения, то оно, как не содержащее х 3 , не изменится. Итак, мы привели систему (2.13) к виду:

 

х 3 = 5/2 х1 + ½ х2 -- ½ y1,

у 2 = -- 3/2 х1 -- ½ х2 + ½ у1 -- х4 + 4, (2.14)

у3 = 3х1 -- 5 х2 + 7

со свободными переменными х1, х2, у1, х4 и базисными х 3, у 2, у3.

Выразим линейную функцию L через новые свободные переменные:

L = 5х1 -- 5х1 -- х2 + у1 -- 2,

или

L = -- х2 + у1 -- 2. (2.15)

Положим теперь свободные переменные равными нулю. Линейная функция L станет равной –2. Это уже лучше, чем прежнее значение L = 0. Но является ли это решение оптимальным? Все еще нет, т.к. коэффициент при х2 в выражении (2.15) отрицателен. Итак, будем увеличивать х2. Посмотрим, для какой из переменных, стоящих в левых частях системы (2.14), это может быть «опасно». Только для у 2 (в первое уравнение х2 входит с положительным коэффициентом, а в третье совсем не входит).

Итак, обменяем местами переменные х2 и у 2 -- первую выведем из числа свободных, а вторую - введем. Для этого разрешим второе уравнение (2.14) относительно х2 и подставим это х2 в первое уравнение. Получим еще один вид системы (2.13):

х3 = х1 -- у 2 -- х4 + 5;

х2 = -- 3х1 -- 2у2 + у1 --2х4 + 8; (2.16)

у3 = 3х1 -- 5 х4 + 7.

Выразим L через новые свободные переменные:

L = 3х1 + 2у2 -- у1 + 2 х4 -- 8 + у1 -- 2,

или

L = 3х1 + 2у2 + 2х4 -- 10. (2.!?)

Полагая х1 = у1 = х4 = 0, получим

L = -- 10.

Является ли это решение оптимальным? На этот раз - да, так как коэффициенты всех свободных переменных в выражении (2.17) неотрицательны.

Итак, оптимальное решение ОЗЛП найдено:

х1* = 0, х2* = 8, х3* = 5, х4* = 0, у1* = 0, у2 = 0; у3 = 7.

При таких значениях переменных линейная функция принимает минимальное значение:

Lmin = --10.

Заметим, что в рассмотренном примере нам не пришлось искать опорного решения: оно сразу же получилось, когда мы положили свободные переменные равными нулю. Это объясняется тем, что в уравнениях (2.13) все свободные члены были неотрицательны и, значит, первое же попавшееся оказалось опорным. Если это окажется не так, можно будет прийти к опорному решению с помощью такой же процедуры обмена местами некоторых базисных и опорных переменных, переразрешая уравнения до тех пор, пока свободные члены не станут отрицательными.

При решении практических задач обычно используется обычно используется табличный алгоритм замены базисных переменных. Процедура «переразрешения» системы уравнений-ограничений ОЗЛП при этом сводится к заполнению стандартных таблиц по определенной системе правил [ Л.6,7,8].

 

Симплекс-метод решения задачи линейного программирования является универсальным и применим для решения любых таких задач. Однако существуют некоторые частные типы задач линейного программирования, которые допускают решение более простыми методами. К ним, в частности, относится и транспортная задача.

Классическая транспортная задача ЛП формулируется следующим образом.

Имеется m пунктов отправления: А1, А2,...... : Аm., в которых сосредоточены запасы какого-то однородного товара в количестве соответственно а1, а2, аm, единиц. Имеется также n пунктов назначения:

В1, В2,........ Вm, подавших заявки соответственно на b1, b2,.....bn, единиц товара.

Предполагается, что сумма всех заявок равна сумме всех запасов.

(3.1)

Известна стоимость с ij перевозки единицы товара от каждого пункта отправления Ai до каждого пункта назначения Bj. Таблица (матрица) стоимостей перевозки с ij задана:

 


 

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

Дадим этой задаче математическую формулировку. Обозначим x i j - количество товара, направляемого из i-го пункта отправления Ai в j – й пункт назначения Bj (i = 1,..., m; j = 1,... n). Неотрицательные переменные х11, х12,...., хmn (число которых, очевидно, равно (m × n) должны удовлетворять следующим условиям:

1. Суммарное количество товара, направляемое из каждого пункта отправления во все пункты назначения, должно быть равно запасу товара в данном пункте. Это дает нам m условий-равенств;

 

х11 + х12 +.... + х1 n = а1,

х21 + х22 +.... + х2 n = а2, (3,2)

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

х m1 + хm2 +.... + хm n = а m.

 

2. Суммарное количество товара, доставляемое в каждый пункт назначения изо во всех пунктов отправления, должно быть равно заявке, поданной каждым пунктом. Это даст n условий-равенств:

 

х11 + х21 +.... + х m1 = b1,

х12 + х22 +.... + хm2 = b2, (3.3)

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

х 1n + х2n +.... + хm n = bn.

 

3. Суммарная стоимость всех перевозок, т.е. сумма величин х i j , умноженных на соответствующие стоимости с i j должна быть минимальной:

 

L = c11 x11 + c12 x12 +.... + c1n x1n + c21 x21 + c22 x22 +....

 

c2n x2n +.... + cm1 x m1 + cm2 x m12 +.... + cm n x m n = min. (3.4)


Функция (3.4) линейна, ограниченная – равенства (3.2),(3.3) также линейны. Перед нами типичная задача с ограничениями – равенствами (ОЗЛП).

Как и всякую другую задачу линейного программирования, ее было бы решить симплекс-методом, но данная задача имеет некоторые особенности, позволяющие решить ее более просто. Причиной является то, что все коэффициенты при переменных в уравнениях (3.2),(3.3) равны единице. Кроме того имеет значение структура связи между условиями. Нетрудно убедиться, что не все m + n уравнений нашей задачи являются независимыми. Действительно, складывая между собой все уравнения (3.2) и все уравнения (3.3) мы должны получить одно и то же, в силу условия (3.1). Таким образом, условия (3.2), (3.3) связаны одной линейной зависимостью, и фактически из этих уравнений только m + n -- 1, а не m + n являются линейно независимыми. Значит, ранг системы уравнений (3.2),(3.3) равен

r = m + n --1

 

а, следовательно, можно разрешить эти уравнения

относительно m + n --1 базисных переменных, выразив их через остальные, свободные.

 

Подсчитаем количество свободных переменных. Оно равно:

 

k = mn -- (m + n –1) = mn -- m – (n –1) =

 

= m(n -- 1) – (n –1) = (m—1) (n –1).

 

Мы знаем, что в задаче линейного программирования оптимальное решение достигается в одной из вершин ОДР, где по крайней мере k переменных обращается в нуль. Значит в нашем случае для оптимального плана перевозок по крайней мере (m—1) (n –1) значений x i j должны быть равны нулю.

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

значения x i j количества единиц транспортируемого продукта, направляемых из пункта Аi

в пункт Вj мы будем называть п е р е в о з к а м и.

Любую совокупность значений (x i j ) (i = 1,...., m; j = 1,... n), будем называть планом перевозок, или просто планом.

План (x i j ) будет называться д о п у с т и м ы м, если он удовлетворяет условиям (3.2).(3.3)

(балансовым условиям)6 все заявки удовлетворены, все запасы исчерпаны.

Допустимый план будет о п о р н ы м, если в нем отличны от нуля не более r = m + n --1

базисных перевозок x i j, а остальные равны нулю.

План (x i j ) будем называть оптимальным, если он среди всех допустимых планов приводит к наименьшей стоимости всех перевозок.

Методы решения транспортной задачи сводятся к простым операциям непосредственно с таблицей, где в определенном порядке записаны все условия транспортной задачи. Такую таблицу называют т р а н с п о р т н о й т а б л и ц е й.

В транспортной таблице записываются

1) пункты отправления и назначения,

2) запасы, имеющиеся в пунктах отправления,

3) заявки, поданные пунктами назначения,

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

Стоимости перевозок помещают в правом верхнем углу каждой ячейки, с тем чтобы в самой ячейке при составлении плана помещать перевозки x i j .

 

Образец заполнения транспортной таблицы

Таблица 3.1

 

пн по\ B1 B2   Bn Запасы ai
А1 С11 С12   С1n a1
А2 с21 с22   с2n a2
……………… ……………… …………………………. ………………………… …………………….  
Аm сm1 сm2   сmn a m
Заявки b1 b2   bn ∑ai = ∑bJ

 

 

Поскольку ранг системы уравнений-ограничений ТЗ равен r = n + m – 1, где

m – число строк, а n – число столбцов, следует утверждать, что в каждом опорном плане, включая и оптимальный, будут отличны от пуля не более чем r = n + m – 1 перевозок.

Ячейки (клетки) таблицы, в которых записываются отличные от нуля перевозки,

 

Называют базисными, а остальные (пустые) свободными.

 




Поделиться с друзьями:


Дата добавления: 2014-01-07; Просмотров: 420; Нарушение авторских прав?; Мы поможем в написании вашей работы!


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



studopedia.su - Студопедия (2013 - 2024) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление




Генерация страницы за: 0.121 сек.