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

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

t = min (14 100/500; 17/1) = 17

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

Рассчитаем элементы новой симплексной таблицы (таблица 2.2).

                                                                                                             Таблица 2.2

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

                                                                                Таблица 2.3

В последней таблице содержится опорный план, оказавшийся оптимальным :

х1 = 14, х2 = 17, х3 = 0, х4 =5,  х5 = 0,          

Z = 3*14+5*17=127 .

Это решение означает следующее: транспортное предприятие может приобрести 14 трехтонных автомашин и 17 пятитонных, при этом их суммарная грузоподъемность будет максимальной – 127 тонн.                  

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

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

400 х1+500 х2 = 14 100,              (1)

х1 = 19,                                        (2)

х2 = 17,                                        (3)

х1 = 0,                                          (4)       

х2 = 0.                                          (5)

Каждое из записанных  уравнений представляет собой прямую на плоскости, причем 4-я и 5-я прямые являются координатными осями. Точки, удовлетворяющие ограничениям х1 0,   х2 0, находятся в первом квадранте.

Рисунок 2.1

Чтобы построить первую прямую, найдем точки ее пересечения с осями координат: при х1 = 0, х2 = 28,2, а при  х2 = 0, х1 = 35,25. Дале определяем, по какую сторону от прямой будет находиться полуплоскость, соответствующая первому неравенству. Чтобы определить искомую полуплоскость, возьмем точку О(0,0) и подставим ее координаты в неравенство – оно удовлетворяется. Так как точка О(0,0)  лежит левее первой прямой, то и полуплоскость будет находится левее прямой  400 х1+500 х2 = 14 100. На рисунке 2.1 расположение полуплоскости относительно первой прямой отмечено стрелками.

Прямые 2-я и 3-я параллельны координатным осям. Точка О (0,0)  лежит левее прямой   х1 = 19 и ниже прямой х2 = 17. Расположение полуплоскостей также отмечено стрелками на рисунке 2.1.

Множество точек, удовлетворяющих всем ограничениям одновременно, является областью допустимых решений (ОДР) системы ограничений. На графике (рис.2.1) это многоугольник ОАВС.

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

Приравняем функцию к нулю и построим соответствующую прямую. Вектор-градиент прямой 3х1+5х2 = 0 имеет координаты = ( 3;5). Изобразим вектор на графике и построим прямую перпендикулярно этому вектору. Перемещая прямую функции параллельно самой себе в направлении вектора, увидим, что последней точкой многоугольника решений, которую пересечет прямая функции, является угловая точка В с координатами (14;17). Следовательно, в точке В функция достигает максимального значения. Чтобы достичь этого значения грузоподъемности, предприятию необходимо приобрести 14 трехтонных грузовиков и 17 пятитонных.

ЗАКЛЮЧЕНИЕ

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

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

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

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

Целью курсовой работы было практическое решение задачи линейной оптимизации обоими методами. Результаты решений задачи линейного программирования совпадают. Максимум функции равен 127.

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

ЛИТЕРАТУРА

1. Акулич И.Л. Математическое программирование в примерах и задачах/ И.Л.Акулич. М.1986. – 319 с.

2. Вентцель Е.С. Исследование операций/У.С.Вентцель. – М., 1972.–552 с.

3. Вентцель Е.С. Исследование операций. Задачи, принципы, методология / Е.С.Вентцель. – М., 1988.– 206 с.

4. Высшая математика для экономистов / И.В.Гайшун и др. – Минск: БГЭУ, 2005. – 623 с.

5. Дегтярев Ю.И. Исследование операций. / Ю.И.Дегтярев. – М., 1986. – 269 с.

6. Конюховский П.В. Математические методы исследования операций в экономике / П.В.Конюховский. – СПб., М., Харьков, Минск: Питер, 2000. –   208 с.

7. Костевич Л.С. Математическое программирование / Л.С.Костевич. – Минск: Новое знание, 2003. – 424 с.

8. Кузнецов А.В. Высшая математика. Математическое программирование / А.В.Кузнецов, Н.Н.Холод, Л.С.Костевич; под ред. А.В.Кузнецова. – Минск: Вышэйшая школа, 2001. – 351 с.

9. Кузнецов А.В. Руководство к решению задач по математическому программированию / А.В.Кузнецов, Н.Н.Холод, Л.С.Костевич; под ред. А.В.Кузнецова – Минск: Вышэйшая школа, 2001. – 448 с.

10. Сборник задач и упражнений по высшей математике. Математическое прграммирование / А.В.Кузнецов и др. ; под ред. А.В.Кузнецова, Р.А.Рутковского. – Минск: Вышэйшая школа, 2002. – 447 с.

11. Кузнецов А.В. Экономико-математические методы исследования операций / А.В.Кузнецов. – Минск: БГЭУ, 2000. –103 с.

12. Саати Т.Л. Математические методы исследования операций / Т.Л.Саати. – М., 1963. – 133 с.

13. Таха Х.А. Введение в исследование операций / Х.А.Таха. – М., СПб., Киев: Вильямс, 2005. – 912 с.

14. Федосеев В.В. Экономико-математические методы и прикладные модели / В.В.Федосеев. – М.: ЮНИТИ, 2000. – 304 с.