Реферат: Решение задач линейной оптимизации симплекс – методом

Министерство образования РФ и РТ.

Казанский Государственный Университет им. А.Н. Туполева.

_______________________________________________


Курсовая работа по дисциплине

«Численные методы оптимизации»


Решение задач линейной оптимизациисимплекс – методом.

Выполнил: ст.гр.4408  КалинкинА.А.

                                                                                     

Проверил: Мурга О.К.

 

 

г. Казань 2001г.

Содержание

 

1. Постановка задачи

 

1.1. Физическая  постановка задачи

1.2. Математическая постановка задачи

2. Приведение задачи к канонической форме

 

3. Нахождение начального опорного плана с помощью L-задачи

 

3.1. Постановка L-задачи

3.2. Решение L-задачи

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

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

 

5. Формирование М-задачи

 

6. Решение М-задачи вторым алгоритмом симплекс-метода

 

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

 

8. Формирование оптимального решения двойственной задачи на основе теоремы о двойственности

 

9. Анализ результатов и выводы


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 150

1.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. Элементы /> и /> определяются скалярнымипроизведениями (Cxej) и (CxB)соответственно. Нулевая итерация заканчивается заполнением нулевойдополнительной строки вспомогательной таблицы с оценками />.

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

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

/>.

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

1)   все /> -задача неразрешима;

2)  /> хотя бы для одного 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)-й строки основнойтаблицы, соответствующей последней итерации, без всяких дополнительныхвычислений.

еще рефераты
Еще работы по математике