Реферат: Решение задач линейной оптимизации симплекс – методом
Курсовая работа по дисциплине «Численные методыоптимизации»
Выполнил: ст.гр.4408 Калинкин А.А.
Казанский Государственный Университет им. А.Н.Туполева.
г. Казань 2001г.
1. Постановка задачи
1.1. Физическая (техническая) постановка задачи
Нефтеперерабатывающий завод получает четыреполуфабриката:
400 тыс. л. алкилата;
250 тыс. л. крекинг-бензина;
350 тыс. л. бензина прямой перегонки;
250 тыс. л. изопентона;
В результате смешивания этих четырёх компонентов вразных пропорциях образуются три сорта авиационного бензина:
Бензин А – 2: 3: 5: 2 ;
Бензин В – 3: 1: 2: 1 ;
Бензин С – 2: 2: 1: 3 ;
Стоимость 1 тыс.л. указанных сортов бензина:
Бензин А – 120 руб.
Бензин Б – 100 руб.
Бензин С – 150 руб.
Необходимо определить план смешения компонентов, прикотором будет достигнута максимальная стоимость все продукции. При следующихусловиях:
Бензина каждого сорта должно быть произведено не менее300 тыс… л.
Неиспользованного крекинг бензина должно остаться неболее 50 тыс.л.
Сводная таблица условий задачи:
Компоненты, используемые для производства трёх видов бензина. Сорта производимого бензинаОбъем ресурсов
(тыс. л)
А В С Алкилат/>
/>
/>
400 Крекинг-бензин/>
/>
/>
250 Бензин прямой перегонки/>
/>
/>
300 Изопентат/>
/>
/>
250 Цена бензина (рублей за 1 тыс.л.) 120 100 1501.2. Математическая постановка задачи
Исходя из условий задачи, необходимо максимизироватьследующую целевую функцию:
/> (1.2.1)
при ограничениях
/> (1.2.2)
/>,где />
В этих выражениях:
/> -объемы бензина А-го, В-го и С-го сорта соответственно.
Тогда
/>объёмная доля первой компоненты (алкилата)в бензине А.
/>объёмная доля первой компоненты (алкилата)в бензине В.
/>объёмная доля первой компоненты (алкилата)в бензине С.
и т.д.
Целевая функция /> выражаетстоимость всей продукции в зависимости от объема производимого бензина каждогосорта. Таким образом, для получения максимальной стоимости продукции необходимомаксимизировать целевую функцию /> (1.2.1) ссоблюдением всех условий задачи, которые накладывают ограничения (1.2.2) на />.
2. Приведение задачи к канонической форме
Задача линейного программирования записана вканонической форме, если она формулируется следующим образом.
Требуется найти вектор />,доставляющий максимум линейной форме
/> (2.1)
при условиях
/> (2.2)
/> (2.3)
где />
Перепишем исходную задачу (1.2.1) — (1.2.2):
/> (2.4)
при ограничениях
/> (2.5)
/>,где /> (2.6)
В канонической форме задачи линейного программированиянеобходимо, чтобы все компоненты искомого вектора Х были неотрицательными, авсе остальные ограничения записывались в виде уравнений. Т.е. в задачеобязательно будут присутствовать условия вида (2.3) и 8 уравнений вида (2.2),обусловленных неравенствами (2.5), (2.6).
Число ограничений задачи, приводящих к уравнениям(2.2) можно уменьшить, если перед приведением исходной задачи (2.4) — (2.6) к каноническойформе мы преобразуем неравенства (2.6) к виду (2.3). Для этого перенесемсвободные члены правых частей неравенств (2.6) в левые части. Таким образом, отстарых переменных /> перейдем к новымпеременным/>, где />:
/>,/>.
Выразим теперь старые переменные через новые
/>,/> (2.7)
и подставим их в линейную форму (2.4) и в неравенства(2.5), (2.6). Получим
/>
/>
/>, где />.
Раскрывая скобки и учитывая, что
/> (2.8),
можем окончательно записать:
/> (2.9)
/> (2.10)
/>,где /> (2.11)
Путем несложных преобразований задачу (1.2.1), (1.2.2)свели к задаче (2.9) — (2.11) с меньшим числом ограничений.
Для записи неравенств (2.10) в виде уравнений введемнеотрицательные дополнительные переменные />,и задача (2.9) — (2.11) запишется в следующей эквивалентной форме:
/> (2.12)
/> (2.13)
/>,где />
Задача (2.12), (2.13) имеет каноническую форму.
3. Нахождение начального опорного плана с помощью L-задачи
Начальный опорный план задачи (2.1) — (2.3),записанной в канонической форме, достаточно легко может быть найден с помощьювспомогательной задачи (L-задачи):
/> (3.1)
/> (3.2)
/> (3.3)
Начальный опорный план задачи (3.1) — (3.3) известен.Он состоит из компонент
/>
и имеет единичный базис Б = />= E.
Решая вспомогательную задачу первым алгоритмомсимплекс-метода (описание алгоритма приводится в п.4), в силу ограниченностилинейной формы />сверху на множествесвоих планов (/>) получим, чтопроцесс решения через конечное число шагов приведет к оптимальному опорномуплану вспомогательной задачи.
Пусть />-оптимальный опорный план вспомогательной задачи. Тогда /> является опорным планомисходной задачи. Действительно, все дополнительные переменные />. Значит, />удовлетворяет условиямисходной задачи, т.е. является некоторым планом задачи (2.12) — (2.13). Попостроению план />является такжеопорным.
3.1. Постановка L-задачи
Вспомогательная задача для нахождения начальногоопорного плана задачи (2.12) — (2.13) в канонической форме состоит в следующем.
Требуется обратить в максимум
/>
при условиях
/>
/>,где />.
/> <td/> />рассматривая в качестве исходного опорного планаплан
Здесь добавление только одной дополнительнойпеременной /> (вместо пяти) обусловленотем, что исходная задача уже содержит четыре единичных вектора условий А4,А5, А6, А7.
3.2. Решение L-задачи
Решение L-задачи будем проводить в соответствии с первымалгоритмом симплекс-метода (описание алгоритма приводится в п.4). Составимтаблицу, соответствующую исходному опорному плану (0-й итерации).
Т.к. Б0= />-базис, соответствующий известному опорному плану/>,является единичной матрицей, то коэффициенты разложения векторов Аjпо базису Б0
/>.
Значение линейной формы /> иоценки /> для заполнения (m+1)-йстроки таблицы определяются следующими соотношениями:
/>,
/>.
Отсюда получим:
/>;
/>;
/>;
…
/>.
Весь процесс решения задачи приведен в табл. 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<sub/>, отвечающий вектору,вводимому в базис, и l-я строка, соответствующая вектору />, исключаемому из базиса,называется соответственно разрешающим столбцом и разрешающей строкой. Элемент />, расположенный напересечении разрешающего столбца и разрешающей строки, называется разрешающимэлементом.
После выделения разрешающего элемента заполняется(ν+1)-я таблица. В l-е позиции столбцов Бх, Схвносятся соответственно Ак, Ск, которые в (ν+1)-йтаблице обозначаются как />, />. В остальные позициистолбцов Бх, Сх вносятся те же параметры, что и в таблицеν.
Далее заполняется главная часть (ν+1)-й таблицы.Прежде всего происходит заполнение ее l-й строки в соответствии срекуррентной формулой
/>.
Рекуррентная формула для заполнения i-й строки(ν+1)-й таблицы имеет вид
/>.
Здесь
/>.
Заполнение главной части (ν+1)-й таблицызавершает (ν+1)-ю итерацию. Последующие итерации проводятся аналогично.Вычисления продолжаются до тех пор, пока не будет получен оптимальный план либобудет установлено, что исследуемая задача неразрешима.
Решение исходной задачи
Весь процесс решения исходной задачи (2.12) — (2.13)приведен в табл. 4.2.
Заполнение таблицы, отвечающей 0-й итерации,происходит на основе табл. 3.2.1 (см. итерацию 1) следующим образом. Главнаячасть таблицы 0-й итерации исходной задачи (за исключением (m+1)-йстроки) полностью повторяет главную часть таблицы заключительной итерации L-задачибез столбца А9. Также без изменений остается столбец базисныхвекторов Бх. Строка С коэффициентов линейной формы исходной задачи истолбец Сх коэффициентов при базисных переменных заполняются исходяиз (2.12). С учетом новых коэффициентов С пересчитываются значение линейнойформы F и оценки />.
Заполнение таблиц, отвечающих последующим итерациям,происходит в соответствии с описанным выше первым алгоритмом.
Таблица 4.2
/>
Решение исходной задачи (2.12) — (2.13) получено за 3итерации. Оптимальный план ее равен /> и />.
Найденное решение /> задачив канонической форме (2.12) — (2.13) соответствует решению /> (4.1) общей задачи линейногопрограммирования (2.9) — (2.11), записанной для новых переменных />. Для общей задачи из (2.9)следует, что /> (4.2).
Вернемся к задаче (1.2.1), (1.2.2) со старымипеременными />. Учитывая (4.1) и (4.2) из(2.7) и (2.8) получим
/> (4.3)
и
/>. (4.4)
Таким образом, для получения максимальной цены(142750 руб.) всей продукции необходимо произвести:
450 тыс.л. бензина А из полуфабрикатов в следующихколичествах:
Алкитата />тыс.л.
Крекинг-бензина />тыс.л.
Бензина прямой перегонки />тыс.л.
Изопентона />тыс.л.
/> тыс.л.бензина В из полуфабрикатов в следующих количествах:
Алкитата />тыс.л.
Крекинг-бензина />тыс.л.
Бензина прямой перегонки />тыс.л.
Изопентона />тыс.л.
300 тыс.л. бензина В из полуфабрикатов в следующихколичествах:
Алкитата />тыс.л.
Крекинг-бензина />тыс.л.
Бензина прямой перегонки />тыс.л.
Изопентона />тыс.л.
5. Формирование М-задачи
Далеко не всегда имеет смысл разделять решение задачилинейного программирования на два этапа – вычисление начального опорного планаи определение оптимального плана. Вместо этого решается расширенная задача(М-задача). Она имеет другие опорные планы (один из них всегда легко указать),но те же решения (оптимальные планы), что и исходная задача.
Рассмотрим наряду с исходной задачей (2.1) — (2.3) вканонической форме следующую расширенную задачу (М-задачу):
/> (5.1)
/> (5.2)
/>. (5.3)
Здесь М>0 – достаточно большое число.
Начальный опорный план задачи (5.1) — (5.3) имеет вид
/>
Переменные /> называютсяискусственными переменными.
Таким образом, исходная задача линейногопрограммирования с неизвестным заранее начальным опорным планом сводится кМ-задаче, начальный опорный план которой известен. В процессе решения этойрасширенной задачи можно либо вычислить оптимальный план задачи (2.1) — (2.3),либо убедиться в ее неразрешимости, если оказывается неразрешимой М-задача.
В соответствии с вышеизложенным имеем: требуетсярешить задачу (2.12), (2.13), записанную в канонической форме. Введемискусственную неотрицательную переменную х9 и рассмотрим расширеннуюМ-задачу
/> (5.4)
при условиях
/> (5.5)
/>,где />.
где М – сколь угодно большая положительная величина.
Как и в L-задаче, добавление только одной искусственнойпеременной /> (вместо пяти) обусловлено тем,что исходная задача уже содержит четыре единичных вектора условий А4, А5,А6, А7.
6. Решение М-задачи IIалгоритмом симплекс-метода
Описание II алгоритма
Второй алгоритм (или метод обратной матрицы) симплексметода основан на ином способе вычисления оценок /> векторовусловий Аj, чем в первом алгоритме.
Рассматривается задача линейного программирования вканонической форме (2.1) — (2.3). Пусть Х – опорный план с базисом />.Все параметры, необходимые для оценки плана на оптимальность и перехода клучшему плану, можно получить, преобразовывая от шага к шагу элементы матрицы />.
Действительно, зная обратную матрицу />, можно получить базисныесоставляющие опорного плана:
/>
и вычислить оценки векторов условий относительнотекущего базиса
/>, (6.1)
предварительно определив вектор-строку /> по формуле
/>
или
/>. (6.2)
Здесь />-вектор-строка из коэффициентов линейной формы, отвечающих базисным переменным.
Оценки /> позволяютустановить оптимальность рассматриваемого опорного плана и определить вектор Ак,вводимый в базис. Коэффициенты /> разложениявектора Ак по текущему базису вычисляются по формуле
/>.
Как и в I алгоритме, вектор, подлежащий исключению избазиса, определяется величиной
/>.
Таким образом при втором алгоритме на каждом шагезапоминаются базисные компоненты />, обратнаяматрица />, значение линейной формы F(X) ивектор Y, соответствующие текущему опорному плану Х. Элементыстолбцов матрицы /> удобнорассматривать как коэффициенты /> разложенияединичных векторов /> по векторамбазиса. Рекуррентные формулы, связывающие параметры двух последовательныхитераций
/>; (6.3)
/>. (6.3)
Здесь
/>.
Результаты вычислений сводятся в основные таблицы(вида табл. 6.1) и вспомогательную таблицу (вида табл. 6.2); столбцы В, е1,…, еm основных таблиц (все m+1 позиций) называют главной частью этихтаблиц. Столбец Аk – разрешающий столбец, строка l – разрешающаястрока.
Таблица 6.1 Таблица 6.2
N/>
/>
B/>
…/>
/>
t N B/>
/>
…/>
1/>
/>
/>
/>
…/>
/>
1/>
/>
/>
…/>
/>
/>
/>
/>
/>
/>
/>
/>
/>
/>
/>
/>
/>
/>
/>
l/>
/>
/>
/>
…/>
/>
/>
m/>
/>
/>
…/>
/>
/>
/>
/>
/>
/>
/>
/>
/>
m+1 C/>
/>
…/>
M/>
/>
/>
/>
…/>
/>
/>
/>
/>
…/>
m+1 – –/>
/>
…/>
/>
– 1/>
/>
/>
…/>
2/>
/>
/>
…/>
… … … … … …Краткое описание алгоритма.
1. Нулевая итерация:
а) составляется вспомогательная табл. 6.2, в которуювносятся параметры задачи; дополнительная строка таблицы с номером νзаполняется по мере выполнения ν-й итерации;
б) составляется основная табл. 6.1 с номером 0, вкоторой заполняются первые m строк, за исключением последних двух столбцов Аk иt. Элементы /> и /> определяются скалярнымипроизведениями (Cx, ej) и (Cx, B)соответственно. Нулевая итерация заканчивается заполнением нулевойдополнительной строки вспомогательной таблицы с оценками />.
2. (ν+1)-я итерация.
Пусть ν-я итерация закончена. В результате заполненаν-я основная таблица, за исключением двух последних столбцов, и ν-ядополнительная строка вспомогательной таблицы. Просматривается эта строка. Есливсе />, то опорный план /> — решение задачи. Если хотябы одна />, то в базис вводится векторАk с /> (обычно />). После этого заполняетсястолбец /> основной таблицы. В позицию(m+1) этого столбца заносится оценка /> вектора Аk.Остальные элементы этого столбца равны
/>.
Возможны два случая:
все /> - задачанеразрешима;
/> хотябы для одного i. В этом случае, также как и в первом алгоритме,заполняется столбец (t) основной таблицы ν, определяется разрешающийэлемент />. Главная часть заполняетсяпо рекуррентной формуле (6.3). Заполняется (ν+1)-я дополнительная строкавспомогательной таблицы. На этом заканчивается (ν+1)-я итерация.
Решение М-задачи
Таблица 6.3
/>
Таблица 6.4
/>
Задача (5.4), (5.5) имеет опорный план Х0=(0, 0, 0, />, />, />, />,0, />) с базисом />. Следовательно, />. Процесс решения М-задачивторым алгоритмом приведен в основной табл. 6.3 и вспомогательной табл. 6.4.
Решение М-задачи получено за 5 шагов. Оптимальный планее равен /> и />.В оптимальном плане М-задачи искусственная переменная х9 = 0,поэтому /> - решение задачи (2.12), (2.13)и />.
Окончательное решение задачи определения планасмешения компонентов полностью повторяет решение, рассмотренное в завершающейчасти п.4 (см. стр.11-12).
7. Формирование двойственной задачи
Произвольной задаче линейного программированияопределенным образом соответствует некоторая другая задача линейногопрограммирования. Будем называть ее двойственной, а первоначальную задачу –исходной.
Обозначим
/>;/>; />;/>; /> (7.1)
Теперь исходная задача (2.1) — (2.3) в каноническойформе может быть записана в матричном виде следующим образом.
Требуется определить вектор />, обращающий в максимум
/>. (7.2)
при условиях
AX=B; (7.3)
/>. (7.4)
Тогда двойственная задача – определить вектор />, обращающий в минимум
f(Y)=YB (7.5)
при условиях
/>. (7.6)
Транспонируя обе части неравенства (7.6), записанногов виде строки, и учитывая />, получим
/>. (7.7)
Отметим, что в двойственной задаче переменные yi<sub/>могутбыть и отрицательными.
Рассмотрим в качестве исходной задачу (2.12), (2.13).С учетом (7.1) и (7.7) запишем
С = (120, 100, 150, 0, 0, 0, 0, 0), B = (/>, />,/>, />,/>),
/>
/>.
Двойственная задача имеет вид
/>; (7.8)
/> (7.9)
8. Формирование оптимального решения двойственнойзадачи на основе теоремы о двойственности
Оказывается, что для задач (7.2) — (7.4) и (7.5), (7.6),называемых двойственной парой, справедлива следующая теорема.
Теорема (первая теорема о двойственности). Если однаиз задач двойственной пары (7.2) — (7.4) и (7.5), (7.6) имеет решение, тодругая задача также разрешима. При этом для любых оптимальных планов /> и />(здесь Мх, Му– множества планов соответственно прямой и двойственной задач) задач (7.2) — (7.4)и (7.5), (7.6) имеет место равенство
/>.
Если линейная форма одной из задач не ограничена (для F(X)– сверху, для f(Y) — снизу), то другая задача не имеет ни одного плана.
Оптимальное решение двойственной задачи может бытьнайдено на основе следующего следствия из этой теоремы.
Следствие. Если вектор /> являетсяоптимальным опорным планом задачи (7.2) — (7.4), то вектор /> (8.1), является оптимальнымопорным планом задачи (7.5), (7.6).
Стоит отметить, что в ходе решения исходной задачивторым алгоритмом, при каждом шаге вычисляется вектор />. И если Х – оптимальныйопорный план задачи (7.2) — (7.4), то в (m+1)-й строке,соответствующей основной таблице, находится решение задачи (7.5), (7.6).
Пусть двойственная задача имеет вид (7.8), (7.9).
Так как исходная задача (2.12), (2.13) имеет решение,то на основании рассмотренной теоремы о двойственности двойственная задачатакже разрешима.
Оптимальным опорным планом исходной является /> (см. п.4, п.6). При этом
/>;
; />.
Вычислим
/>.
На основании следствия из теоремы о двойственностиможно заключить, что /> являетсяоптимальным планом двойственной задачи, при котором />.Анализируя (m+1)-ю строку основной таблицы (см. табл. 6.3, шаг 5),можно убедиться в том, что оптимальный план двойственной задачи, сформированныйна основе теоремы о двойственности, совпадает с оптимальным планом, найденномпри решении исходной задачи вторым алгоритмом симплекс-метода. Это говорит отом, что оптимальный план задачи (7.8) — (7.9) найден верно.
9. Анализ результатов и выводы
В данной работе рассматриваются два способа решенияисходной задачи линейного программирования.
Первый заключается в том, что сначала решаетсявспомогательная задача (L-задача), позволяющая построить начальный опорныйплан, затем на основе этого найденного плана решается исходная задача(определяется ее оптимальный план). Второй способ является объединением двухэтапов и состоит в решении расширенной задачи (M-задачи), такжеприводящей к нахождению оптимального плана исходной задачи.
Вычислительную основу этих двух способов решениясоставляют соответственно первый и второй алгоритмы симплекс-метода. Один изпараметров, по которому может быть оценен любой итерационный алгоритм –количество шагов, приводящих к решению задачи или установлению ее неразрешимости.Для данной задачи наиболее эффективным методом оказался первый метод(L-задача+ исходная задача), т.к. он привел к решению за 4 шага, а второй метод (M-задача)за 5 шагов. Разница в числе шагов, вероятно, обусловлена неоднозначность выбораразрешающего элемента в исходной таблице L-задачи(3.2.1).
Сравнение количества вычислений на каждой итерацииприводит к следующим оценочным результатам рассматриваемых алгоритмов.Преимущественная часть вычислений на каждом шаге алгоритмов определяется размерностьюглавной части таблицы (в первом алгоритме) или основной таблицы (во второмалгоритме). В первом случае она имеет размерность (m+1)x(n+1), во втором — (m+1)x(m+1). Даже учитывая, что второй алгоритм требует построениявспомогательной таблицы, он оказывается более компактным.
Еще одно несомненное достоинство второго алгоритмазаключается в возможности определения оптимального плана двойственной задачи из(m+1)-й строки основной таблицы, соответствующейпоследней итерации, без всяких дополнительных вычислений.
Список литературы
Для подготовки данной работы были использованыматериалы с сайта www.monax.ru