Методы решения задач линейного программирования

 

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

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

Симплекс метод - универсальный метод для решения линейной системы уравнений или неравенств и линейного функционала.

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

 

x₁ + a_1,m+1x_m+1 + ... + a_1sx_s+...+ a_1nx_n = b₁;

x₂ + a_2,m+1x_m+1 + ... + a_2sx_s+...+ a_2nx_n = b₂;

...

x_m + a_m,m+1x_m+1 + ... + a_msx_s+...+ a_mnx_n = b_m

Общая  идея  перехода  от  ОЗЛП  к  КЗЛП  достаточно  проста:

• ограничения  в  виде  неравенств  преобразуются  в  уравнения  за  счет  добавления  фиктивных  неотрицательных  переменных  ,  которые одновременно  входят  в целевую функцию с коэффициентом 0,  т.  е.  не  оказывают  влияния  на  ее  значение;
• переменные,  на  которые  не  наложено  условие  не  отрицательности,  представляются  в  виде  разности  двух  новых  неотрицательных  переменных:

• переменные,  на  которые  наложено  условие  неположительности,  представляются  в виде  новой неотрицательной переменной  помноженной на   ( -1) :

Следует  отметить,  что  переход  от  ОЗЛП  к  КЗЛП  приводит  к  увеличению  её  размерности,  что  усложняет  процесс  решения.

 

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

1. Выбираем начальное допустимое базисное решение. Базисным решением называется решение, полученное при нулевых значениях небазисных переменных, т.е. x_i=0, i=m+1,...,n. Базисное решение называется допустимым базисным решением, если значения входящих в него базисных переменных неотрицательны, т.е. x_j = b_j ³ 0, j=1,2,...,m. В этом случае целевая функция примет следующий вид: W=c_bx_b=c₁b₁+c₂b₂+...+c_mb_m.

  Заполняем первоначальную таблицу  симплекс - метода:

2. Вычисляем вектор относительных оценок c при помощи правила скалярного произведения с_j = с_j - c_bS_j,

где

с_b - вектор оценок базисных переменных;

Sj - j-тый столбец из коэффициентов a_ij в канонической системе, соответствующей рассматриваемому базису.

Дополняем первоначальную таблицу c - строкой.

 

3. Если все оценки c_j £ 0 (c_j ³ 0), i=1,...,n, то текущее допускаемое решение - максимальное (минимальное). Решение найдено.

4. В противном случае в базис необходимо ввести небазисную переменную x_r с наибольшим значением c_j вместо одной из базисных переменных (см. таблицу).

5. При помощи правила минимального отношения min(b_i/a_ir) определяем переменную x_p, выводимую из базиса. Если коэффициент a_ir отрицателен, то b_i/a_ir=¥. В результате пересечение столбца, где находится вводимая небазисная переменная x_r, и строки, где находится выводимая базисная переменная x_p, определит положение ведущего элемента таблицы

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

7. Вычисляем новые относительные оценки с использованием правила скалярного преобразования и переходим к шагу 4. 

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

 

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

Лесничество имеет 24 га свободной земли под  паром и заинтересовано извлечь  из нее доход. Оно может выращивать саженцы быстрорастущего гибрида  новогодней ели, которые достигают  спелости за один год, или бычков, отведя часть земли под пастбище. Деревья выращиваются и продаются в партиях по 1000 штук. Требуется 1.5 га для выращивания одной партии деревьев и 4 га для вскармливания одного бычка. Лесничество может потратить только 200 ч. в год на свое побочное производство. Практика показывает, что требуется 20 ч. для культивации, подрезания, вырубки и пакетирования одной партии деревьев. Для ухода за одним бычком также требуется 20 ч. Лесничество имеет возможность израсходовать на эти цели 6 тыс. руб. Годовые издержки на одну партию деревьев выливаются в 150 руб. и 1,2 тыс. руб. на одного бычка. Уже заключен контракт на поставку 2 бычков. По сложившимся ценам, одна новогодняя ель принесет прибыль в 2,5 руб., один бычок - 5 тыс. руб.

Целевая функция:      5000 x1 + 2500 x2 à max,                             

 Ограничения:

• По использованию земли, га:  4 x₁ + 1,5 x₂ £ 24
• По бюджету, руб.:    1200 x₁ + 150 x₂ £ 6000
• По трудовым ресурсам, ч:   20 x₁ + 20 x₂ £ 200
• Обязательства по контракту, шт.:  x₁ ³ 2
• Областные ограничения:   x₁ ³ 0, x₂ ³ 0

Приведем  задачу к стандартной форме:

4 x₁ + 1,5 x₂ +x₃= 24

1200 x₁ + 150 x₂ +x₄= 6000

20 x₁ + 20 x₂ +x₅= 200

x₁ – x₆= 2

x₁ ... x₆ ³ 0

Первые три  уравнения имеют соответственно по базисной переменной x₃, x₄, x₅, однако в четвертом она отсутствует ввиду того, что при переменной x₆ стоит отрицательный единичный коэффициент. Для приведения системы к каноническому виду используем метод искусственных переменных.

x₁ – x₆+x₇= 2, ввели искусственную переменную x₇

 

 

2 этап симплекс-метода: W=5000 x₁ + 2500 x₂ à max

Изменяем  базисные переменные в предыдущей таблице  и коэффициенты с_i целевой функции.

Вариант с  заменой х₅ на х₂ (вводом х₂ в базисные переменные) приводит к более быстрому окончанию итераций).

Все значения С строки неположительные, сл. найдено оптимальное решение.

Таким образом, корнями задачи ЛП про размещение побочного производства лесничества  будут x₁=3.6 бычка и х₂=6.4 партий ели, а прибыль – 34000 рублей (без учета целочисленности задачи).

 

Заключение

 

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

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

 

 

,0Список используемой литературы

 

1. Ашманов С.А. Линейное программирование. М.: Наука, 2001.
2. Калихман И.Л. Линейная алгебра и программирование. - М.: Высшая школа, 1987
3. Лунгу К.К. Линейное программирование. Руководство к решению задач. – М.: ФИЗМАТЛИТ, 2005.
4. Лищенко «Линейное и нелинейное программирование», М. 2003
5. Орлов А.И. Теория принятия решений. Учебное пособие. - М.: Издательство "Март", 2004