Линейное программирование. 7

ОГЛАВЛЕНИЕ

ВВЕДЕНИЕ……………………………………………………………………...…6

1Теоретическая часть…………………….…………………………………….….8

1.1 Графический метод решения задач линейного программирования……..….8

1.2 Симплексный метод решения задач линейного программирования………12

1.3 Симплекс-таблицы……………………………………………………………13

1.4 Двойственная задача………………………………………………………….17

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

2 Примеры решения задач линейного программирования…………………….25

ЗАКЛЮЧЕНИЕ…………………………………………………………….

БИБЛИОГРАФИЧЕСКИЙ СПИСОК……………………………………

ВВЕДЕНИЕ

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

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

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

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

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

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

• задача об оптимальном использовании ограниченных ресурсов (сырьевых, трудовых, временных);

• задача сетевого планирования и управления;

• задачи массового обслуживания;

• задачи составления расписания (календарного планирования);

• задачи выбора маршрута и другие.

Оптимизационная задача, в которой целевая функция и неравенства (уравнения), входящие в систему ограничений являются линейными функциями, называется задачей линейного программирования.

1 Теоретическая часть

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

Графический метод решения ЗЛП основан на следующих утверждениях.

Система ограничений ЗЛП геометрически представляет собой выпуклый многоугольник или выпуклую многоугольную область как пересечение полуплоскостей - геометрических образов неравенств системы.

Целевая функция Z = c1x1 + c2x2 геометрически изображает семейство параллельных прямых, перпендикулярных вектору нормали N(с1,с2). Эти прямые называются линиями уровня.

Линия уровня - это прямая, вдоль которой целевая функция принимает фиксированное значение.

Теорема. При перемещении линии уровня в направлении вектора нормали N значение целевой функции возрастает, в противоположном направлении - убывает.

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

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

Рис.1

Пусть геометрическим изображением системы ограничений является многоугольник ABCDE (рис 1.1). Необходимо среди точек этого многоугольника найти такую точку, в которой линейная функция F=c1x1+c2x2 принимает максимальное (или минимальное) значение.

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

c1x1+c2x2=а.  (1.1)

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

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

Уравнение линии уровня функции (1.1) есть уравнение прямой линии. При различных уровнях а линии уровня параллельный , т.к. их угловые коэффициенты определяются только соотношением между коэффициентами с1 и с2 и, следовательно, равны. Таким образом, линии уровня функции F –это своеобразные «параллели», расположенные обычно под углом к осям координат.

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

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

1. В системе координат построить прямые по уравнениям, соответствующим каждому неравенству системы ограничений;

2. найти полуплоскость решения каждого неравенства системы (обозначить стрелками). Для определения полуплоскости необходимо выбрать любую контрольную точку, не лежащую на данной прямой.   Подставить ее координаты в систему ограничений. Если неравенство выполняется, то нужно выбрать полуплоскость, содержащую контрольную точку. Если неравенство не выполняется нужно выбрать полуплоскость, не содержащую контрольную точку. В качестве контрольной точки рекомендуется выбирать точку с координатами (0;0);

3. найти многоугольник (многоугольную область) решений системы ограничений как пересечение полуплоскостей;

4. построить вектор нормали N. Начало вектора нормали в точке с координатами (0;0), конец вектора в точке с координатами (с1, с2);

5. через начало координат построить линию уровня, перпендикулярно к вектору нормали;

6. перемещать линию уровня параллельно самой себе по области решения в угловые точки, достигая max функции при движении вектора N (min функции при движении в противоположном направлении);

7. найти координаты точки max (min). Для этого необходимо решить систему уравнений прямых, которые пересекаются в этой точке или определить координаты по графику;

8. вычислить значение целевой функции в этой точке.

Рис.2

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

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

1.2 Симплексный метод решения задачи линейного программирования

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

Пусть имеется произвольная задача линейного программирования, с числом переменных n и числом уравнений m. Оптимальное решение, если оно существует, достигается в одной из опорных точек, в которой, по крайней мере, k из n переменных обращаются в нуль:

k=n-m                                                                                             (2.1)

Выберем в качестве свободных эти k переменных, остальные m будут базисными. Для определенности в качестве свободных выберем первые k переменных: х1 ,…, хk . Остальные хk+1 ,…,хn базисные переменные можно выразить через эти свободные.

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

L=y0 + y1x1+…+ykxk→ max.                                                       (2.2)

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

х1 = x2=…xk =0                                                                              (2.3)

Допустим, что все коэффициенты в целевой функции при переменных х1,  x2, …,хk   отрицательны, тогда

L=y0 ,                                                                                               (2.4)

и найденное опорное решение является оптимальным.

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

Если для какой-то переменной хr

xr = ar1 xr1 +…+ari xri +ark xrk +br                                                     (2.5)

коэффициент при свободной переменной хi меньше нуля, то увеличивать переменную хi можно только до тех пор, пока переменная хr не станет равной нулю

хi r  = -br / ari                                                                                      (2.6)

Пусть есть еще одна переменная хl

xl = al1 x1i +…+ari xi +alk xk +bl ,                                                     (2.7)

для которой коэффициент при хi тоже меньше нуля. Тогда предел увеличения переменной хi для этой переменной

хi l  = -bl / ali .                                                                                     (2.8)

Очевидно, что увеличивать переменную хi можно до того значения, которое является минимальным, то есть для той из переменных, которая быстрее обращается в нуль. Пусть в ноль быстрее обращается переменная  xr . Тогда эти две переменные мы должны поменять местами, то есть i–ую переменную из свободных перевести в базисные, а r-ую – из базисных в свободные. Необходимо переразрешить систему ограничений и саму целевую функцию относительно нового набора базисных и свободных переменных:

х1,х 2,…, хi-1,xi+1,…, xk, xr – свободные переменные,

хi,, х k-1,…, хr-1, xr+1,…, xn – базисные переменные.

Появилась другая опорная точка. Далее вся процедура повторяется.

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

1.3 Симплекс-таблицы

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

Обозначим через хi свободные переменные, через уj- базисные переменные. Пусть есть система ограничений: необходимо поменять местами переменную у3 и свободную переменную х2  из третьего уравнения (а32≠0) и подставить во все остальные.

y1 = a11x1 + a12x2 + a13x3 + a14x4 + b1 ,              (3.1)

y2 = a21x1 + a22x2 + a23x3 + a24x4 + b2 ,

y3 = a31x1 + a32x2 + a33x3 + a34x4 + b3 ,

y4 = a41x1 + a42x2 + a43x3 + a44x4 + b4 ,

y5 = a51x1 + a52x2 + a53x3 + a54x4 + b5 ,

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

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

y1= b1- (-a11x1 - a12x2- …- a14x4).              (3.2)

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

                                                                                                 Таблица 1

Алгоритм замены:

1)     разрешающий элемент заменяется на обратную ему величину;

2)     все элементы разрешающей строки делятся на разрешающий элемент;

3)     все элементы разрешающего столбца, кроме разрешающего элемента, меняют на противоположный и делятся на разрешающий элемент;

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

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

1)     выделяют в таблице разрешающий элемент a1k;

2)     найти обратную ему величину λ=1/аlk и записать ее в правом нижнем углу этой же ячейки;

3)     все элементы разрешающей строки, кроме разрешающего элемента, умножить на λ и результат записать в правой нижней части ячейки;

4)     все элементы разрешающего столбца, кроме разрешающего элемента, умножить на (-λ).

5)     выделить в разрешающей строке все верхние числа, а в разрешающем столбце – все нижние числа;

6)     для каждого из элементов, которые не принадлежать ни разрешающему столбцу, ни разрешающей строке, записать в нижнюю часть ячейки произведение выделенных чисел, стоящих в той же строке и том же столбце, что и данный элемент;

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

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

1) нахождение опорного решения;

2) нахождение оптимального решения.

В процессе первого этапа выясняется имеет ли данная задача допустимое решение. Если да, то находится опорное решение.

В процессе второго этапа выясняется ограничена ли сверху целевая функция . Если нет, то оптимального решения нет.

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

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

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

F=c1x1 +…+ cnxn→ max                                                                          (4.1)

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

a11x1 + a12x1 + …+ а1nxn ≤b1 ,               (4.2)

………..,

ak1x1 + ak2x2 + …+ аknxn ≤bk  ,

ak+1x1 + ak+2x2 + …+ аk+1xn =bk+1  ,

…………….,

am1x1 + am2x2 + …+ аmnxn =bm ,

xj ≥ 0 (j=l,…,l; l≤n).

Это прямая задача. Двойственной к этой задаче является задача, состоящая в нахождении минимума функции

F*=b1y1 + …+ bmym

              (4.3)

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

a11у1 + a21у1 + …+ аm1ym ≥c1 ,               (4.4)

………..,

a11y1 + a21y2 + …+ аm1ym ≥c1 ,

a11+1y1 + a21+1y2 + …+ аm 1+1ym =cl+1  ,

…………….,

a1ny1 + a2ny2 + …+ аmnym =cn,

yi≥ 0 (i=l,…,k; k≤m).

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

1)                       если прямая задача является задачей максимизации, то двойственная будет будет задачей минимизации, и наоборот;

2)                       коэффициенты целевой функции прямой задачи с1 , с2 , …,сn становятся свободными членами ограничений двойственной задачи;

3)                       свободные члены ограничений прямой задачи b1 , b2 , …,bm становятся коэффициентами целевой функции двойственной задачи;

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

5)                       число ограничений прямой задачи равно числу переменных двойственной задачи, а число ограничений двойственной задачи равно числу переменных прямой задачи;

6)                       если переменная xj  прямой задачи может принимать только неотрицательные значения, то j-ое ограничение в двойственной задаче является неравенством вида больше или равно; если же переменная xj  может принимать как положительные, так и отрицательные значения, то j-ое ограничение в двойственной задаче – уравнение.

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

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

Правила перехода от прямой к двойственной задаче для симметричных и несимметричных задач (табл.2).

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

Теорема 1. если х0 и u0  - допустимые решения прямой и двойственной задач соответственно, то значение целевой функции прямой задачи никогда не превышают значения целевой функции двойственной задачи.

Теорема 2. Если х0 и u0   - допустимые решения прямой и двойственной задач соответственно, и если выполняется равенство

CT х0 =u0T*B,              (4.5)

то   х0 и u0   - оптимальные решения пары двойственных задач.

Таблица2
 

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

Транспортная задача- это более простой метод решения задач линейного программирования.

Пусть имеются m пунктов отправления (ПО) А1, А2,…,Аm, в которых сосредоточены запасы каких-то однородных грузов в количестве соответственно а1, а2,…, аm, единиц. Имеются n пунктов назначения (ПН) В1, В2,…,Вm, подавших заявки соответственно на b1, b2,…, bm, единиц груза. Сумма всех заявок в сумме равна сумме всех запасов:

=

Условие называется балансовым условием, а транспортная задача- задача с правильным балансом.

Известны стоимости Су перевозки единицы груза от каждого пункта отправления А до каждого пункта назначения В. Задана матрица стоимостей С. Считается, что стоимость перевозки нескольких единиц груза пропорциональна их числу.

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

Нужно обозначить через хij количество единиц груза, отправляемого из i-ого ПО А1  в j-ый ПН В1 .

Совокупность чисел (хij) будет называться «планом перевозок», а сами величины хij  - «перевозками». Эти положительные переменные должны удовлетворять следующим условиям:

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

х11 +х 12  +…+ х1n= а1,              (5.2)

.

.

xm1 +х m2  +…+ хmn= аm,

или в общем виде

=ai, (i=1,m).

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

Это даст n условий-равенств:

х11 +х 12  +…+ хm1= b1,              (5.3)

.

.

x1n +х 2n  +…+ хmn= bn,

=bj, (i=1,n).

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

L=→min,

где знак двойной суммы означает, что суммирование производится по всем комбинациям индексов i и j, то есть по всем парам ПО-ПН.

Особенности транспортной задачи, которые позволяют решит её более простыми способами:

1.                              Все коэффициенты при переменных в ограничениях равны единицы.

2.                              Значение имеет структура связей между переменными. Число линейно-независимых уравнений равно не m+n, а (n+m-1). Общее число в данной задаче равно mn.