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

ОГЛАВЛЕНИЕ

ВВЕДЕНИЕ……………………………………………………………………...…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 – базисные переменные.

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

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