Реферат: Решение задач линейной оптимизации симплекс – методом
…
.
Весь процесс решения задачи приведен в табл. 3.2.1, которая состоит из 2 частей, отвечающих 0-й (исходная таблица) и 1-й итерациям.
Заполняем таблицу 0-й итерации.
Среди оценок 
имеются
отрицательные. Значит, исходный опорный план не является оптимальным. Перейдем
к новому базису. В базис будет введен вектор А1 с наименьшей
оценкой 
. Значения t
вычисляются для всех позиций столбца t
(т.к. все элементы разрешающего столбца положительны). Наименьший элемент 
достигается на
пятой позиции базиса. Значит, пятая строка является разрешающей строкой, и
вектор А9 подлежит исключению из базиса.
Составим таблицу, отвечающую первой итерации.
В столбце Бх, в пятой позиции базиса
место вектора А9 занимает вектор А1.
Соответствующий ему коэффициент линейной формы С41 = 0
помещаем в столбец Сх. Главная часть таблицы 1 заполняется по
данным таблицы 0 в соответствии с рекуррентными формулами. Так как все 
,
то опорный план 
является решением L-задачи.
Наибольшее значение линейной формы равно 
.
Таблица 3.2.1
3.3. Формирование начального опорного плана исходной задачи линейного программирования из оптимального плана L-задачи
Поскольку 
,
где 
- оптимальный опорный план L-задачи,
то 
является начальным опорным
планом исходной задачи (2.12) - (2.13).
4. Решение исходной задачи I алгоритмом симплекс-метода
Описание I алгоритма
Симплекс-метод позволяет, отправляясь от некоторого исходного опорного плана и постепенно улучшая его, получить через конечное число итераций оптимальный план или убедиться в неразрешимости задачи. Каждой итерации соответствует переход от одной таблицы алгоритма к следующей. Таблица, отвечающая опорному плану в ν-й итерации имеет вид табл. 4.1.
Таблица 4.1
C |
|
… |
|
… |
|
… |
|
||||
N |
|
|
B |
|
… |
|
… |
|
… |
|
t |
| 1 |
|
|
|
|
… |
|
… |
|
… |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
l |
|
|
|
|
… |
|
… |
|
… |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
m |
|
|
|
|
… |
|
… |
|
… |
|
|
|
m+1 |
– | – |
|
|
… |
|
… |
|
… |
|
– |
Заполнение таблицы, соответствующей исходному опорному
плану (0-й итерации). Пусть 
некоторый
опорный план задачи (2.1) - (2.3) с базисом 
. Тогда 
–
базисные компоненты, а 
– небазисные компоненты.
Вычисляем коэффициенты разложения векторов Аj по базису Б0
(в
случае, если Б0 является единичной матрицей, 
)
и
находим оценки 
. Далее определяем значение линейной формы
Полученные результаты записываем в таблицу 4.1.
В первом столбце N таблицы указываются номера
строк. Номера первых m строк совпадают с номерами позиций базиса. Во втором
столбце Сх записываются коэффициенты 
линейной
формы при базисных переменных. Столбец Бх содержит векторы
базиса 
. В столбце В записываются базисные переменные 
опорного
плана. Столбцы 
содержат коэффициенты 
разложения
соответствующих векторов условий 
по векторам базиса. Все вышесказанное относится
только к первым m строкам
таблицы. Последняя (m+1)-я строка таблицы заполняется последовательно значением
линейной формы F и
оценками 
. Позиции таблицы, которые не должны заполняться,
прочеркиваются.
В результате заполнена таблица 0-й итерации кроме столбца t.
Столбцы В, А1,…, An (все m+1 позиций) будем называть главной частью таблицы.
Порядок вычислений в отдельной итерации. Пусть ν-я итерация закончена. В результате заполнена таблица ν за исключением последнего столбца t.
Каждая итерация состоит из двух этапов.
I этап: проверка исследуемого опорного плана на оптимальность.
Просматривается (m+1)-я
строка таблицы ν. Если все 
, то опорный план, полученный после ν-й
итерации, является оптимальным
(случай 1), завершаем
решение задачи. Пусть теперь имеются отрицательные оценки. Проверяем знаки
элементов 
столбцов 
с 
. Наличие по крайней мере одного столбца 
,
для которого 
и все 
, свидетельствует о неразрешимости задачи (случай 2).
Установив это, прекращаем вычисления.
Если в каждом столбце 
,
для которого 
, содержится хотя бы один положительный коэффициент 
,
то опорный план является неоптимальным (случай 3). Переходим ко II
этапу.
II этап: построение нового опорного плана с большим значением линейной формы.
Определяется вектор Ak, который должен быть введен в базис, из следующего условия
.
После этого заполняется последний столбец таблицы ν
– столбец t. В него записываются отношения базисных переменных 
(элементы
столбца В) к соответствующим составляющим 
(элементы столбца Ak). Т.о.
заполняются только те позиции, для которых 
. Если 
, то в позиции i столбца t записывается 
.
Вектор базиса 
, на котором достигается t0,
,
подлежит исключению из базиса (если t0 достигается на нескольких векторах, то из базиса исключается любой из них).
Столбец Ak , отвечающий
вектору, вводимому в базис, и l-я строка, соответствующая вектору 
, исключаемому из базиса, называется соответственно разрешающим
столбцом и разрешающей строкой. Элемент 
,
расположенный на пересечении разрешающего столбца и разрешающей строки,
называется разрешающим элементом.
После выделения разрешающего элемента заполняется (ν+1)-я
таблица. В l-е
позиции столбцов Бх, Сх вносятся
соответственно Ак, Ск, которые в (ν+1)-й
таблице обозначаются как 
, 
. В остальные позиции столбцов Бх, Сх
вносятся те же параметры, что и в таблице ν.
Далее заполняется главная часть (ν+1)-й таблицы. Прежде всего происходит заполнение ее l-й строки в соответствии с рекуррентной формулой
.
Рекуррентная формула для заполнения i-й строки (ν+1)-й таблицы имеет вид
.
Здесь
.
Заполнение главной части (ν+1)-й таблицы завершает (ν+1)-ю итерацию. Последующие итерации проводятся аналогично. Вычисления продолжаются до тех пор, пока не будет получен оптимальный план либо будет установлено, что исследуемая задача неразрешима.
