Предыдущая страница реферата | 1  2  3  4  5  6  7  8  9  10  11 | Следующая страница реферата

…

[pic].

Весь процесс решения задачи приведен в табл. 3.2.1, которая состоит из
2 частей, отвечающих 0-й (исходная таблица) и 1-й итерациям.

Заполняем таблицу 0-й итерации.

Среди оценок [pic] имеются отрицательные. Значит, исходный опорный план не является оптимальным. Перейдем к новому базису. В базис будет введен вектор А1 с наименьшей оценкой [pic]. Значения t вычисляются для всех позиций столбца t (т.к. все элементы разрешающего столбца положительны).
Наименьший элемент [pic] достигается на пятой позиции базиса. Значит, пятая строка является разрешающей строкой, и вектор А9 подлежит исключению из базиса.

Составим таблицу, отвечающую первой итерации.

В столбце Бх, в пятой позиции базиса место вектора А9 занимает вектор
А1. Соответствующий ему коэффициент линейной формы С41 = 0 помещаем в столбец Сх. Главная часть таблицы 1 заполняется по данным таблицы 0 в соответствии с рекуррентными формулами. Так как все [pic], то опорный план
[pic] является решением L-задачи. Наибольшее значение линейной формы равно
[pic].

Таблица 3.2.1

[pic]

3.3. Формирование начального опорного плана исходной задачи линейного программирования из оптимального плана L-задачи

Поскольку [pic], где [pic] [pic]- оптимальный опорный план L-задачи, то [pic] [pic]является начальным опорным планом исходной задачи (2.12) -
(2.13).

4. Решение исходной задачи I алгоритмом симплекс-метода

Описание I алгоритма

Симплекс-метод позволяет, отправляясь от некоторого исходного опорного плана и постепенно улучшая его, получить через конечное число итераций оптимальный план или убедиться в неразрешимости задачи. Каждой итерации соответствует переход от одной таблицы алгоритма к следующей. Таблица, отвечающая опорному плану в ?-й итерации имеет вид табл. 4.1.

Таблица 4.1

| | | |C |[pi|… |[pi|… |[pi|… |[pi| |
| | | | |c] | |c] | |c] | |c] | |
|N |[pi|[pi|B |[pi|… |[pi|… |[pi|… |[pi|t |
| |c] |c] | |c] | |c] | |c] | |c] | |
|1 |[pi|[pi|[pi|[pi|… |[pi|… |[pi|… |[pi| |
| |c] |c] |c] |c] | |c] | |c] | |c] | |
|[pic|[pi|[pi|[pi|[pi|[pi|[pi|[pi|[pi|[pi|[pi| |
|] |c] |c] |c] |c] |c] |c] |c] |c] |c] |c] | |
|l |[pi|[pi|[pi|[pi|… |[pi|… |[pi|… |[pi|[pi|
| |c] |c] |c] |c] | |c] | |c] | |c] |c] |
|[pic|[pi|[pi|[pi|[pi|[pi|[pi|[pi|[pi|[pi|[pi| |
|] |c] |c] |c] |c] |c] |c] |c] |c] |c] |c] | |
|m |[pi|[pi|[pi|[pi|… |[pi|… |[pi|… |[pi| |
| |c] |c] |c] |c] | |c] | |c] | |c] | |
|m+1 |– |– |[pi|[pi|… |[pi|… |[pi|… |[pi|– |
| | | |c] |c] | |c] | |c] | |c] | |

Заполнение таблицы, соответствующей исходному опорному плану (0-й итерации). Пусть [pic] некоторый опорный план задачи (2.1) - (2.3) с базисом [pic]. Тогда [pic] – базисные компоненты, а [pic] – небазисные компоненты.

Вычисляем коэффициенты разложения векторов Аj по базису Б0

[pic] (в случае, если Б0 является единичной матрицей, [pic]) и находим оценки [pic]. Далее определяем значение линейной формы

[pic]

Полученные результаты записываем в таблицу 4.1.

В первом столбце N таблицы указываются номера строк. Номера первых m строк совпадают с номерами позиций базиса. Во втором столбце Сх записываются коэффициенты [pic]линейной формы при базисных переменных.
Столбец Бх содержит векторы базиса [pic]. В столбце В записываются базисные переменные [pic] опорного плана. Столбцы [pic]содержат коэффициенты
[pic]разложения соответствующих векторов условий [pic] по векторам базиса.
Все вышесказанное относится только к первым m строкам таблицы. Последняя
(m+1)-я строка таблицы заполняется последовательно значением линейной формы
F и оценками [pic]. Позиции таблицы, которые не должны заполняться, прочеркиваются.

В результате заполнена таблица 0-й итерации кроме столбца t.

Столбцы В, А1,…, An (все m+1 позиций) будем называть главной частью таблицы.

Порядок вычислений в отдельной итерации. Пусть ?-я итерация закончена.
В результате заполнена таблица ? за исключением последнего столбца t.

Рекомендуем скачать другие рефераты по теме: доклад, курсовая работа на тему предприятие.





Предыдущая страница реферата | 1  2  3  4  5  6  7  8  9  10  11 | Следующая страница реферата