Dычисление симплекс метода в случае отрицательных свободных членов

  • 07 апр. 2012 г.
  • 4035 Слова
ВВЕДЕНИЕ
Целью курсовой работы является вычисление симплекс метода в случае отрицательных свободных членов.
Симплекс-метод впервые разработал Г.Данциг в 1947 г. Этот метод позволяет переходить от одного допустимого базисного решения к другому, причем так, что значения целевой функции непрерывно возрастают. В результате оптимальное решение находят за конечное число шагов.
Симплекс-методпрост как для математического интуитивного понимания, так и для реализации, и преподается ныне в базовых курсах оптимальных задач.
Симплекс-метод был прост, но оказался экспоненциальным - для разных эвристик выбора следующей вершины обхода исследователи сумели построить набор задач, для решения которых симплекс-методу было необходимо экспоненциально большое число итераций. И все же долгое времясимплекс-метод был даже теоретически лучшим известным алгоритмом для решения задач линейного программирования (ЛП). Однако в конце 1970-х годов Л. Г. Хачиян построил алгоритм, который решает задачу линейного программирования за полиномиальное число шагов - так называемый метод эллипсоидов Хачияна.
Полиномиальный алгоритм мог бы стать новым стандартом программирования. Но алгоритм Хачияна плох на практике.Существуют задачи размером в 50 переменных, для которых требуются более 24 тысяч итераций метода Хачияна, причем итерации эти отнюдь не тривиальны (хоть и полиномиальны). Количество итераций симплекс-метода в таких случаях исчисляется сотнями, и пересчет каждой из них гораздо проще. Метод эллипсоидов несравним с симплекс-методом: последний на практике справляется с задачами ЛП многократно лучше.Все промышленные реализации решения ЛП основаны на симплекс-методе и его вариантах.
В ходе выполнения данной курсовой работы будет рассмотрен симплекс метод в случае произвольных свободных членов, а также создана программа, решающая задачи по этой теме.
1. РЕАЛИЗАЦИЯ СИМПЛЕКС МЕТОДА В СЛУЧАЕ ПРОИЗВОЛЬНЫХ СВОБОДНЫХ ЧЛЕНОВ
1.1. Общая характеристика симплекс метода
Симплекс метод -универсальный метод для решения линейной системы уравнений или неравенств и линейного функционала.
Общая идея симплексного метода (метода последовательного улучшения плана) для решения ЗЛП (задачи линейного программирования) состоит в:
* умение находить начальный опорный план;
* наличие признака оптимальности опорного плана;
* умение переходить к нехудшему опорному плану.Пусть ЗЛП представлена системой ограничений в каноническом виде:
∑j-1naijxj=bi bi≥0 (i=1,…,m)
Ограничение ЗЛП имеет предпочтительный вид, если при неотрицательной правой части bi≥0 левая часть ограничений содержит переменную, входящую с коэффициентом, равным единице, а в остальные ограничения равенства - с коэффициентом, равным нулю.Пусть система ограничений имеет вид:
∑j-1naijxj≤bi bi≥0 (i=1,…,m)
Нужно свести задачу к каноническому виду. Для этого прибавим к левым частям неравенств дополнительные переменные xn+1≥0 (i=1,…,m). Получается система, эквивалентная исходной:
∑j-1naijxj=bi bi≥0 i=1,…,m,
которая имеетпредпочтительный вид
x0=(0;0;…;0;b1;b2;…;bm)
n m
В целевую функцию дополнительные переменные вводятся с коэффициентами, равными нулю cn+1=0 i=1,…,m.
Пусть далее система ограничений имеет вид
∑j-1naijxj≥bi bi≥0 (i=1,…,m)
Нужно свести её к эквивалентной вычитаниемдополнительных переменных xn+1≥0 (i=1,…,m) из левых частей неравенств системы. Получим систему
∑j-1naijxj-xn+1=bi bi≥0 (i=1,…,m)
Однако теперь система ограничений не имеет предпочтительного вида, так как дополнительные переменные xn+1 входят в левую часть (при bi≥0) с коэффициентами, равными –1. Поэтому, вообще говоря, базисный план...
tracking img