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

Результаты вычислений сводятся в основные таблицы (вида табл. 6.1) и вспомогательную таблицу (вида табл. 6.2); столбцы В, е1, …, еm основных таблиц (все m+1 позиций) называют главной частью этих таблиц. Столбец Аk – разрешающий столбец, строка l – разрешающая строка.

Таблица 6.1 Таблица

6.2

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

Краткое описание алгоритма.

1. Нулевая итерация: а) составляется вспомогательная табл. 6.2, в которую вносятся параметры задачи; дополнительная строка таблицы с номером ? заполняется по мере выполнения ?-й итерации; б) составляется основная табл. 6.1 с номером 0, в которой заполняются первые m строк, за исключением последних двух столбцов Аk и t. Элементы
[pic] и [pic] определяются скалярными произведениями (Cx, ej) и (Cx, B) соответственно. Нулевая итерация заканчивается заполнением нулевой дополнительной строки вспомогательной таблицы с оценками [pic].

2. (?+1)-я итерация.

Пусть ?-я итерация закончена. В результате заполнена ?-я основная таблица, за исключением двух последних столбцов, и ?-я дополнительная строка вспомогательной таблицы. Просматривается эта строка. Если все [pic], то опорный план [pic]- решение задачи. Если хотя бы одна [pic], то в базис вводится вектор Аk с [pic] (обычно [pic]). После этого заполняется столбец
[pic] основной таблицы. В позицию (m+1) этого столбца заносится оценка
[pic] вектора Аk. Остальные элементы этого столбца равны

[pic].

Возможны два случая:

1) все [pic] - задача неразрешима;

2) [pic] хотя бы для одного i. В этом случае, также как и в первом алгоритме, заполняется столбец (t) основной таблицы ?, определяется разрешающий элемент [pic]. Главная часть заполняется по рекуррентной формуле (6.3). Заполняется (?+1)-я дополнительная строка вспомогательной таблицы. На этом заканчивается (?+1)-я итерация.

Решение М-задачи

Таблица 6.3

[pic]

Таблица 6.4

[pic]

Задача (5.4), (5.5) имеет опорный план
Х0 = (0, 0, 0, [pic], [pic], [pic], [pic], 0 , [pic]) с базисом [pic].
Следовательно, [pic]. Процесс решения М-задачи вторым алгоритмом приведен в основной табл. 6.3 и вспомогательной табл. 6.4.

Решение М-задачи получено за 5 шагов. Оптимальный план ее равен [pic] и
[pic]. В оптимальном плане М-задачи искусственная переменная х9 = 0, поэтому [pic] - решение задачи (2.12), (2.13) и [pic].

Окончательное решение задачи определения плана смешения компонентов полностью повторяет решение, рассмотренное в завершающей части п.4 (см. стр.11-12).

7. Формирование двойственной задачи

Произвольной задаче линейного программирования определенным образом соответствует некоторая другая задача линейного программирования. Будем называть ее двойственной, а первоначальную задачу – исходной.

Обозначим

[pic]; [pic]; [pic]; [pic]; [pic] (7.1)

Теперь исходная задача (2.1) - (2.3) в канонической форме может быть записана в матричном виде следующим образом.

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





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