Дипломная работа: Некоторые задачи оптимизации в экономике

Одним их таких методов является симплексный метод .

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

Пусть ОДР изображается многоугольником ABCDEGH. Предположим,

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

Идея последовательного улучшения решения легла в основу универсального метода решения ЗЛП – симплексного метода. Для использования симплексного метода ЗЛП должна быть приведена к каноническому виду. Для реализации симплексного метода необходимо освоить 3 основных элемента:

· способ определения какого – либо первоначального допустимого решения

· правило перехода к лучшему решению

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

Алгоритм конкретной реализации этих элементов рассмотрим на примере.

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

Алгоритм составления симплексных таблиц :

1. Система ограничений приводится к каноническому виду.

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

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

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

4. Если критерий оптимальности не выполнен, то наибольший по модулю отрицательный коэффициент в последней строке определяет разрешающий столбец S . Составляют оценочные ограничения по следующим правилам:

· ∞, если b_i и а_is имеют разные знаки;

· ∞, если b_i =0и а_is <0;

· ∞, если а_is =0;

· 0, если b_i =0 и а_is >0;

· , если b_i и а_is имеют одинаковые знаки.

Определяют min. Если конечного минимума нет, то задача не имеет конечного оптимума. Далее выбирают строку с номером q , на которой он достигается (любую, если их несколько), и называют её разрешающей строкой . На пересечении разрешающей строки и разрешающего столбца находится разрешающий элемент а_qs .

5. Переходим к следующей таблице по правилам:

а) в левом столбце записывают новый базис: вместо основной переменной х_q - переменную х_s , а геометрически произо