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

--PAGE_BREAK--<img width=«231» height=«24» src=«ref-1_298607046-439.coolpic» v:shapes="_x0000_i1037">                                                                   (1.2.1) при ограничениях <img width=«229» height=«195» src=«ref-1_298607485-860.coolpic» v:shapes="_x0000_i1038">                                                                    (1.2.2) <img width=«57» height=«25» src=«ref-1_298608345-246.coolpic» v:shapes="_x0000_i1039">,   где  <img width=«43» height=«25» src=«ref-1_298608591-228.coolpic» v:shapes="_x0000_i1040"> В этих выражениях:
<img width=«59» height=«25» src=«ref-1_298608819-257.coolpic» v:shapes="_x0000_i1041">  — объемы бензина А-го, В-го и С-го сорта соответственно.

Тогда

<img width=«52» height=«41» src=«ref-1_298609076-259.coolpic» v:shapes="_x0000_i1042">объёмная доля первой компоненты (алкилата) в бензине А.

<img width=«45» height=«41» src=«ref-1_298609335-244.coolpic» v:shapes="_x0000_i1043">объёмная доля первой компоненты (алкилата) в бензине В.

<img width=«45» height=«41» src=«ref-1_298609579-254.coolpic» v:shapes="_x0000_i1044">объёмная доля первой компоненты (алкилата) в бензине С.

 и т.д.

Целевая функция <img width=«20» height=«17» src=«ref-1_298609833-199.coolpic» v:shapes="_x0000_i1045"> выражает стоимость всей продукции в зависимости от объема производимого бензина каждого сорта. Таким образом, для получения максимальной стоимости продукции необходимо максимизировать целевую функцию <img width=«20» height=«17» src=«ref-1_298609833-199.coolpic» v:shapes="_x0000_i1046"> (1.2.1) с соблюдением всех условий задачи, которые накладывают ограничения (1.2.2) на <img width=«20» height=«17» src=«ref-1_298609833-199.coolpic» v:shapes="_x0000_i1047">.
2
.
 
Приведение задачи к канонической форме
Задача линейного программирования записана в канонической форме, если она формулируется следующим образом.

Требуется найти вектор <img width=«97» height=«24» src=«ref-1_298610430-293.coolpic» v:shapes="_x0000_i1048">, доставляющий максимум линейной форме

<img width=«149» height=«47» src=«ref-1_298610723-441.coolpic» v:shapes="_x0000_i1049">                                                                                        (2.1)

при условиях

<img width=«145» height=«47» src=«ref-1_298611164-426.coolpic» v:shapes="_x0000_i1050">                                                                                         (2.2)

<img width=«105» height=«28» src=«ref-1_298611590-320.coolpic» v:shapes="_x0000_i1051">                                                                                                   (2.3)

где <img width=«104» height=«27» src=«ref-1_298611910-320.coolpic» v:shapes="_x0000_i1052">
Перепишем исходную задачу (1.2.1) - (1.2.2):


<img width=«231» height=«24» src=«ref-1_298607046-439.coolpic» v:shapes="_x0000_i1053">                                                                   (2.4) при ограничениях <img width=«229» height=«195» src=«ref-1_298607485-860.coolpic» v:shapes="_x0000_i1054">                                                                    (2.5)
          <img width=«57» height=«25» src=«ref-1_298608345-246.coolpic» v:shapes="_x0000_i1055">,   где  <img width=«43» height=«25» src=«ref-1_298608591-228.coolpic» v:shapes="_x0000_i1056">                                                                                                         (2.6)

В канонической форме задачи линейного программирования необходимо, чтобы все компоненты искомого вектора Х были неотрицательными, а все остальные ограничения записывались в виде уравнений. Т.е. в задаче обязательно будут присутствовать условия вида (2.3) и 8 уравнений вида (2.2), обусловленных неравенствами (2.5), (2.6).

Число ограничений задачи, приводящих к уравнениям (2.2) можно уменьшить, если перед  приведением исходной задачи (2.4) - (2.6) к канонической форме мы преобразуем неравенства (2.6) к виду (2.3). Для этого перенесем свободные члены правых частей неравенств (2.6) в левые части. Таким образом, от старых переменных <img width=«16» height=«25» src=«ref-1_298614003-199.coolpic» v:shapes="_x0000_i1057"> перейдем к новым переменным<img width=«16» height=«24» src=«ref-1_298614202-198.coolpic» v:shapes="_x0000_i1058">, где <img width=«43» height=«25» src=«ref-1_298608591-228.coolpic» v:shapes="_x0000_i1059">:

<img width=«112» height=«25» src=«ref-1_298614628-296.coolpic» v:shapes="_x0000_i1060">, <img width=«43» height=«25» src=«ref-1_298608591-228.coolpic» v:shapes="_x0000_i1061">.

Выразим теперь старые переменные через новые

<img width=«87» height=«25» src=«ref-1_298615152-272.coolpic» v:shapes="_x0000_i1062">, <img width=«43» height=«25» src=«ref-1_298608591-228.coolpic» v:shapes="_x0000_i1063">                                                                                          (2.7)

и подставим их в линейную форму (2.4) и в неравенства (2.5), (2.6). Получим
<img width=«380» height=«24» src=«ref-1_298615652-586.coolpic» v:shapes="_x0000_i1064">
<img width=«393» height=«192» src=«ref-1_298616238-1175.coolpic» v:shapes="_x0000_i1065">

                   <img width=«43» height=«24» src=«ref-1_298617413-227.coolpic» v:shapes="_x0000_i1066">, где <img width=«41» height=«25» src=«ref-1_298617640-228.coolpic» v:shapes="_x0000_i1067">.

Раскрывая скобки и учитывая, что

<img width=«332» height=«24» src=«ref-1_298617868-473.coolpic» v:shapes="_x0000_i1068">                                                   (2.8),

можем окончательно записать:
<img width=«227» height=«24» src=«ref-1_298618341-424.coolpic» v:shapes="_x0000_i1069">                                                                     (2.9)


    продолжение
--PAGE_BREAK--<img width=«255» height=«192» src=«ref-1_298618765-1169.coolpic» v:shapes="_x0000_i1070">                                                            (2.10)
          <img width=«45» height=«25» src=«ref-1_298619934-228.coolpic» v:shapes="_x0000_i1071">,   где  <img width=«43» height=«25» src=«ref-1_298608591-228.coolpic» v:shapes="_x0000_i1072">                                                                                                            (2.11)
Путем несложных преобразований задачу (1.2.1), (1.2.2) свели к задаче (2.9) - (2.11) с меньшим числом ограничений.
Для записи неравенств (2.10) в виде уравнений введем неотрицательные дополнительные переменные <img width=«105» height=«27» src=«ref-1_298620390-312.coolpic» v:shapes="_x0000_i1073">, и задача (2.9) - (2.11) запишется в следующей эквивалентной форме:
<img width=«227» height=«24» src=«ref-1_298618341-424.coolpic» v:shapes="_x0000_i1074">                                                                    (2.12)

<img width=«300» height=«192» src=«ref-1_298621126-1333.coolpic» v:shapes="_x0000_i1075">                          (2.13)

          <img width=«45» height=«25» src=«ref-1_298619934-228.coolpic» v:shapes="_x0000_i1076">,   где  <img width=«43» height=«25» src=«ref-1_298622687-226.coolpic» v:shapes="_x0000_i1077">                                                                              
Задача (2.12), (2.13) имеет каноническую форму.
3. Нахождение начального опорного плана с помощью
L
-задачи
Начальный опорный план задачи (2.1) - (2.3), записанной в канонической форме, достаточно легко может быть найден с помощью вспомогательной задачи (L-задачи):
<img width=«155» height=«45» src=«ref-1_298622913-433.coolpic» v:shapes="_x0000_i1078">                                                                                      (3.1)

<img width=«188» height=«47» src=«ref-1_298623346-464.coolpic» v:shapes="_x0000_i1079">                                                                              (3.2)

<img width=«133» height=«28» src=«ref-1_298623810-349.coolpic» v:shapes="_x0000_i1080">                                                                                            (3.3)
Начальный опорный план задачи (3.1) - (3.3) известен. Он состоит из компонент
<img width=«221» height=«28» src=«ref-1_298624159-440.coolpic» v:shapes="_x0000_i1081">                                                  
и имеет единичный базис Б = <img width=«97» height=«24» src=«ref-1_298624599-288.coolpic» v:shapes="_x0000_i1082">= E
.

Решая вспомогательную задачу первым алгоритмом симплекс-метода (описание алгоритма приводится в п.4), в силу ограниченности линейной формы <img width=«40» height=«25» src=«ref-1_298624887-245.coolpic» v:shapes="_x0000_i1083">сверху на множестве своих планов (<img width=«63» height=«25» src=«ref-1_298625132-273.coolpic» v:shapes="_x0000_i1084">) получим, что процесс решения через конечное число шагов приведет к оптимальному опорному плану вспомогательной задачи.

Пусть <img width=«120» height=«29» src=«ref-1_298625405-326.coolpic» v:shapes="_x0000_i1085">— оптимальный опорный план вспомогательной задачи. Тогда <img width=«107» height=«25» src=«ref-1_298625731-312.coolpic» v:shapes="_x0000_i1086"> является опорным планом исходной задачи. Действительно, все дополнительные переменные <img width=«112» height=«27» src=«ref-1_298626043-317.coolpic» v:shapes="_x0000_i1087">. Значит, <img width=«24» height=«20» src=«ref-1_298626360-208.coolpic» v:shapes="_x0000_i1088">удовлетворяет условиям исходной задачи, т.е. является некоторым планом задачи (2.12) - (2.13). По построению план <img width=«24» height=«20» src=«ref-1_298626360-208.coolpic» v:shapes="_x0000_i1089">является также опорным.
3.1. Постановка
L
-задачи
Вспомогательная задача для нахождения начального опорного плана задачи (2.12) - (2.13) в канонической форме состоит в следующем.

Требуется обратить в максимум

<img width=«79» height=«27» src=«ref-1_298626776-285.coolpic» v:shapes="_x0000_i1090">

при условиях

<img width=«364» height=«192» src=«ref-1_298627061-1347.coolpic» v:shapes="_x0000_i1091">

<img width=«45» height=«25» src=«ref-1_298619934-228.coolpic» v:shapes="_x0000_i1092">,   где  <img width=«43» height=«25» src=«ref-1_298628636-229.coolpic» v:shapes="_x0000_i1093">.

<img width=«272» height=«41» src=«ref-1_298628865-586.coolpic» v:shapes="_x0000_s1027">     продолжение
--PAGE_BREAK--
рассматривая в качестве исходного опорного плана план

Здесь добавление только одной дополнительной переменной <img width=«19» height=«24» src=«ref-1_298629451-202.coolpic» v:shapes="_x0000_i1094"> (вместо пяти) обусловлено тем, что исходная задача уже содержит четыре единичных вектора условий А4, А5, А6, А7.
3.2. Решение
L
-задачи
Решение L-задачи будем проводить в соответствии с первым алгоритмом симплекс-метода (описание алгоритма приводится в п.4). Составим таблицу, соответствующую исходному опорному плану (0-й итерации).

Т.к. Б0 = <img width=«219» height=«25» src=«ref-1_298629653-436.coolpic» v:shapes="_x0000_i1095">— базис, соответствующий известному опорному плану<img width=«271» height=«41» src=«ref-1_298630089-576.coolpic» v:shapes="_x0000_i1096">, является единичной матрицей, то коэффициенты разложения векторов Аjпо базису Б0

<img width=«207» height=«27» src=«ref-1_298630665-429.coolpic» v:shapes="_x0000_i1097">.

Значение линейной формы <img width=«23» height=«20» src=«ref-1_298631094-205.coolpic» v:shapes="_x0000_i1098"> и оценки <img width=«67» height=«28» src=«ref-1_298631299-270.coolpic» v:shapes="_x0000_i1099"> для заполнения (m+1)-й строки таблицы определяются следующими соотношениями:

<img width=«155» height=«45» src=«ref-1_298631569-424.coolpic» v:shapes="_x0000_i1100">,

<img width=«177» height=«45» src=«ref-1_298631993-452.coolpic» v:shapes="_x0000_i1101">.

Отсюда получим:
<img width=«457» height=«41» src=«ref-1_298632445-708.coolpic» v:shapes="_x0000_i1102">;

<img width=«374» height=«43» src=«ref-1_298633153-636.coolpic» v:shapes="_x0000_i1103">;

<img width=«297» height=«43» src=«ref-1_298633789-488.coolpic» v:shapes="_x0000_i1104">;

…

<img width=«244» height=«24» src=«ref-1_298634277-358.coolpic» v:shapes="_x0000_i1105">.
Весь процесс решения задачи приведен в табл. 3.2.1, которая состоит из 2 частей, отвечающих-й (исходная таблица) и 1-йитерациям.

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

Среди оценок <img width=«80» height=«28» src=«ref-1_298634635-284.coolpic» v:shapes="_x0000_i1106"> имеются отрицательные. Значит, исходный опорный план не является оптимальным. Перейдем к новому базису. В базис будет введен вектор А1 с наименьшей оценкой <img width=«72» height=«23» src=«ref-1_298634919-249.coolpic» v:shapes="_x0000_i1107">. Значения tвычисляютсядля всех позиций столбца t(т.к. все элементы разрешающего столбца положительны). Наименьший элемент <img width=«77» height=«24» src=«ref-1_298635168-271.coolpic» v:shapes="_x0000_i1108"> достигается на пятой позиции базиса. Значит, пятая строка является разрешающей строкой, и вектор А9 подлежит исключению из базиса.

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

В столбце Бх, в пятой позиции базиса место вектора А9занимает вектор А1. Соответствующий ему коэффициент линейной формы С41 = 0 помещаем в столбец Сх. Главная часть таблицы 1 заполняется по данным таблицы 0 в соответствии с рекуррентными формулами. Так как все <img width=«48» height=«25» src=«ref-1_298635439-235.coolpic» v:shapes="_x0000_i1109">, то опорный план <img width=«303» height=«41» src=«ref-1_298635674-673.coolpic» v:shapes="_x0000_i1110"> является решением L-задачи. Наибольшее значение линейной формы равно <img width=«151» height=«25» src=«ref-1_298636347-374.coolpic» v:shapes="_x0000_i1111">.
Таблица 3.2.1 
<img width=«661» height=«201» src=«ref-1_298636721-3349.coolpic» v:shapes="_x0000_i1112">
3.3. Формирование начального опорного плана исходной задачи линейного программирования из оптимального плана
L
-задачи
Поскольку <img width=«151» height=«25» src=«ref-1_298636347-374.coolpic» v:shapes="_x0000_i1113">, где <img width=«341» height=«41» src=«ref-1_298640444-653.coolpic» v:shapes="_x0000_i1114"> <img width=«77» height=«41» src=«ref-1_298641097-321.coolpic» v:shapes="_x0000_i1115"> — оптимальный опорный план L-задачи, то <img width=«251» height=«41» src=«ref-1_298641418-527.coolpic» v:shapes="_x0000_i1116">  <img width=«111» height=«41» src=«ref-1_298641945-404.coolpic» v:shapes="_x0000_i1117">является начальным опорным планом исходной задачи (2.12) - (2.13).
4. Решение исходной задачи
I
алгоритмом симплекс-метода
Описание
I
алгоритма

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


    продолжение
--PAGE_BREAK--


Заполнение таблицы, соответствующей исходному опорному плану (0-й итерации). Пусть <img width=«108» height=«25» src=«ref-1_298654194-316.coolpic» v:shapes="_x0000_i1177"> некоторый опорный план задачи (2.1) - (2.3) с базисом <img width=«117» height=«25» src=«ref-1_298654510-316.coolpic» v:shapes="_x0000_i1178">. Тогда <img width=«105» height=«28» src=«ref-1_298654826-323.coolpic» v:shapes="_x0000_i1179"> – базисные компоненты, а <img width=«108» height=«27» src=«ref-1_298655149-321.coolpic» v:shapes="_x0000_i1180"> – небазисные компоненты.

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

<img width=«149» height=«28» src=«ref-1_298655470-387.coolpic» v:shapes="_x0000_i1181"> (в случае, если Б0является единичной матрицей, <img width=«109» height=«27» src=«ref-1_298655857-318.coolpic» v:shapes="_x0000_i1182">)


и находим оценки <img width=«181» height=«45» src=«ref-1_298656175-446.coolpic» v:shapes="_x0000_i1183">. Далее определяем значение линейной формы

<img width=«221» height=«47» src=«ref-1_298656621-548.coolpic» v:shapes="_x0000_i1184">

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

В первом столбце N таблицы указываются номера строк. Номера первых mстрок совпадают с номерами позиций базиса. Во втором столбце Сх записываются коэффициенты <img width=«23» height=«25» src=«ref-1_298657169-206.coolpic» v:shapes="_x0000_i1185">линейной формы при базисных переменных. Столбец Бх содержит векторы базиса <img width=«23» height=«25» src=«ref-1_298657375-206.coolpic» v:shapes="_x0000_i1186">. В столбце В записываются базисные переменные <img width=«21» height=«25» src=«ref-1_298657581-198.coolpic» v:shapes="_x0000_i1187"> опорного плана. Столбцы <img width=«81» height=«28» src=«ref-1_298657779-293.coolpic» v:shapes="_x0000_i1188">содержат коэффициенты <img width=«19» height=«25» src=«ref-1_298658072-203.coolpic» v:shapes="_x0000_i1189">разложения соответствующих векторов условий <img width=«20» height=«25» src=«ref-1_298643788-207.coolpic» v:shapes="_x0000_i1190"> по векторам базиса. Все вышесказанное относится только к первым mстрокам таблицы. Последняя (m+1)-я строка таблицы заполняется последовательно значением линейной формы Fи оценками <img width=«83» height=«28» src=«ref-1_298658482-287.coolpic» v:shapes="_x0000_i1191">. Позиции таблицы, которые не должны заполняться, прочеркиваются.

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

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

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

Каждая итерация состоит из двух этапов.

I
этап:проверка исследуемого опорного плана на оптимальность.

Просматривается (m+1)-ястрока таблицы ν. Если все <img width=«105» height=«28» src=«ref-1_298658769-308.coolpic» v:shapes="_x0000_i1192">, то опорный план, полученный после ν-й итерации, является оптимальным(случай 1), завершаем решение задачи. Пусть теперь имеются отрицательные оценки. Проверяем знаки элементов <img width=«19» height=«25» src=«ref-1_298659077-203.coolpic» v:shapes="_x0000_i1193"> столбцов <img width=«21» height=«25» src=«ref-1_298659280-208.coolpic» v:shapes="_x0000_i1194"> с <img width=«48» height=«25» src=«ref-1_298659488-234.coolpic» v:shapes="_x0000_i1195">. Наличие по крайней мере одного столбца <img width=«21» height=«25» src=«ref-1_298659280-208.coolpic» v:shapes="_x0000_i1196">, для которого <img width=«48» height=«25» src=«ref-1_298659488-234.coolpic» v:shapes="_x0000_i1197"> и все <img width=«104» height=«28» src=«ref-1_298660164-320.coolpic» v:shapes="_x0000_i1198">, свидетельствует о неразрешимости задачи (случай 2). Установив это, прекращаем вычисления.

Если в каждом столбце <img width=«21» height=«25» src=«ref-1_298659280-208.coolpic» v:shapes="_x0000_i1199">, для которого <img width=«48» height=«25» src=«ref-1_298659488-234.coolpic» v:shapes="_x0000_i1200">, содержится хотя бы один положительный коэффициент <img width=«19» height=«25» src=«ref-1_298659077-203.coolpic» v:shapes="_x0000_i1201">, то опорный план является неоптимальным (случай 3). Переходим ко IIэтапу.

II
этап:построение нового опорного плана с большим значением линейной формы.

Определяется векторAk, который должен быть введен в базис, из следующего условия

<img width=«111» height=«31» src=«ref-1_298661129-306.coolpic» v:shapes="_x0000_i1202">.

После этого заполняется последний столбец таблицы ν – столбец t. В него записываются отношения базисных переменных <img width=«21» height=«25» src=«ref-1_298661435-200.coolpic» v:shapes="_x0000_i1203"> (элементы столбца В) к соответствующим составляющим <img width=«21» height=«24» src=«ref-1_298661635-204.coolpic» v:shapes="_x0000_i1204"> (элементы столбца Ak). Т.о. заполняются только те позиции, для которых <img width=«47» height=«24» src=«ref-1_298661839-231.coolpic» v:shapes="_x0000_i1205">. Если <img width=«47» height=«24» src=«ref-1_298662070-236.coolpic» v:shapes="_x0000_i1206">, то в позиции iстолбца tзаписывается <img width=«29» height=«15» src=«ref-1_298662306-197.coolpic» v:shapes="_x0000_i1207">. Вектор базиса <img width=«24» height=«25» src=«ref-1_298662503-207.coolpic» v:shapes="_x0000_i1208">, на котором достигается t0,

<img width=«120» height=«53» src=«ref-1_298662710-398.coolpic» v:shapes="_x0000_i1209">,

подлежит исключению из базиса (если t0достигается на нескольких векторах, то из базиса исключается любой из них).

Столбец Ak, отвечающий вектору, вводимому в базис, и l-я строка, соответствующая вектору<img width=«23» height=«25» src=«ref-1_298648082-207.coolpic» v:shapes="_x0000_i1210">
, исключаемому из базиса, называется соответственно разрешающим столбцом и разрешающей строкой. Элемент <img width=«21» height=«24» src=«ref-1_298663315-205.coolpic» v:shapes="_x0000_i1211">, расположенный на пересечении разрешающего столбца и разрешающей строки, называется разрешающим элементом.

После выделения разрешающего элемента заполняется (ν+1)-я таблица. В l-е позиции столбцов Бх, Сх вносятся соответственно Ак, Ск, которые в (ν+1)-й таблице обозначаются как <img width=«23» height=«25» src=«ref-1_298648082-207.coolpic» v:shapes="_x0000_i1212">, <img width=«24» height=«25» src=«ref-1_298663727-208.coolpic» v:shapes="_x0000_i1213">. В остальные позиции столбцов Бх, Сх вносятся те же параметры, что и в таблице ν.

Далее заполняется главная часть (ν+1)-й таблицы. Прежде всего происходит заполнение ее l-йстроки в соответствии с рекуррентной формулой

<img width=«144» height=«51» src=«ref-1_298663935-430.coolpic» v:shapes="_x0000_i1214">.

Рекуррентная формула для заполнения i-й строки (ν+1)-й таблицы имеет вид

<img width=«423» height=«49» src=«ref-1_298664365-759.coolpic» v:shapes="_x0000_i1215">.

Здесь

<img width=«351» height=«28» src=«ref-1_298665124-574.coolpic» v:shapes="_x0000_i1216">.

Заполнение главной части (ν+1)-й таблицы завершает (ν+1)-ю итерацию. Последующие итерации проводятся аналогично. Вычисления продолжаются до тех пор, пока не будет получен оптимальный план либо будет установлено, что исследуемая задача неразрешима.
Решение исходной задачи

Весь процесс решения исходной задачи (2.12) - (2.13) приведен в табл. 4.2.

Заполнение таблицы, отвечающей 0-й итерации, происходит на основе табл. 3.2.1 (см. итерацию 1) следующим образом. Главная часть таблицы 0-й итерации исходной задачи (за исключением (m+1)-й строки) полностью повторяет главную часть таблицы заключительной итерации L-задачи без столбца А9. Также без изменений остается столбец базисных векторов Бх. Строка С коэффициентов линейной формы исходной задачи и столбец Сх коэффициентов при базисных переменных заполняются исходя из (2.12). С учетом новых коэффициентов С пересчитываются значение линейной формы Fи оценки <img width=«79» height=«28» src=«ref-1_298665698-279.coolpic» v:shapes="_x0000_i1217">.

Заполнение таблиц, отвечающих последующим итерациям, происходит в соответствии с описанным выше первым алгоритмом.
Таблица 4.2 

<img width=«673» height=«400» src=«ref-1_298665977-6025.coolpic» v:shapes="_x0000_i1218">
Решение исходной задачи(2.12) - (2.13) получено за 3итерации. Оптимальный план ее равен <img width=«244» height=«41» src=«ref-1_298672002-475.coolpic» v:shapes="_x0000_i1219"> и <img width=«191» height=«24» src=«ref-1_298672477-412.coolpic» v:shapes="_x0000_i1220">.

Найденное решение <img width=«24» height=«20» src=«ref-1_298626360-208.coolpic» v:shapes="_x0000_i1221"> задачи  в канонической форме (2.12) - (2.13) соответствует решению <img width=«129» height=«41» src=«ref-1_298673097-370.coolpic» v:shapes="_x0000_i1222"> (4.1) общей задачи линейного программирования (2.9) - (2.11), записанной для новых переменных <img width=«71» height=«27» src=«ref-1_298673467-273.coolpic» v:shapes="_x0000_i1223">. Для общей задачи из (2.9) следует, что <img width=«128» height=«21» src=«ref-1_298673740-333.coolpic» v:shapes="_x0000_i1224"> (4.2).

Вернемся к задаче (1.2.1), (1.2.2) со старыми переменными <img width=«71» height=«27» src=«ref-1_298674073-278.coolpic» v:shapes="_x0000_i1225">. Учитывая (4.1) и (4.2) из (2.7) и (2.8) получим
<img width=«199» height=«109» src=«ref-1_298674351-648.coolpic» v:shapes="_x0000_i1226">                                                                                     (4.3)

и

<img width=«265» height=«25» src=«ref-1_298674999-446.coolpic» v:shapes="_x0000_i1227">.                                                                  (4.4)

            Таким образом, для получения максимальной цены (142750 руб.) всей продукции необходимо произвести:

-         450 тыс.л. бензина А из полуфабрикатов в следующих количествах:

-       Алкитата <img width=«88» height=«41» src=«ref-1_298675445-314.coolpic» v:shapes="_x0000_i1228">тыс.л.

-       Крекинг-бензина <img width=«104» height=«41» src=«ref-1_298675759-341.coolpic» v:shapes="_x0000_i1229">тыс.л.

-       Бензина прямой перегонки <img width=«104» height=«41» src=«ref-1_298676100-342.coolpic» v:shapes="_x0000_i1230">тыс.л.

-       Изопентона <img width=«88» height=«41» src=«ref-1_298675445-314.coolpic» v:shapes="_x0000_i1231">тыс.л.

-         <img width=«41» height=«41» src=«ref-1_298676756-255.coolpic» v:shapes="_x0000_i1232"> тыс.л. бензина В из полуфабрикатов в следующих количествах:

-       Алкитата <img width=«111» height=«41» src=«ref-1_298677011-365.coolpic» v:shapes="_x0000_i1233">тыс.л.

-       Крекинг-бензина <img width=«104» height=«41» src=«ref-1_298677376-346.coolpic» v:shapes="_x0000_i1234">тыс.л.

-       Бензина прямой перегонки <img width=«97» height=«41» src=«ref-1_298677722-341.coolpic» v:shapes="_x0000_i1235">тыс.л.

-       Изопентона <img width=«104» height=«41» src=«ref-1_298677376-346.coolpic» v:shapes="_x0000_i1236">тыс.л.

-         300 тыс.л. бензина В из полуфабрикатов в следующих количествах:

-       Алкитата <img width=«79» height=«41» src=«ref-1_298678409-290.coolpic» v:shapes="_x0000_i1237">тыс.л.

-       Крекинг-бензина <img width=«79» height=«41» src=«ref-1_298678409-290.coolpic» v:shapes="_x0000_i1238">тыс.л.

-       Бензина прямой перегонки <img width=«93» height=«41» src=«ref-1_298678989-309.coolpic» v:shapes="_x0000_i1239">тыс.л.

-       Изопентона <img width=«100» height=«41» src=«ref-1_298679298-326.coolpic» v:shapes="_x0000_i1240">тыс.л.
5. Формирование М-задачи
Далеко не всегда имеет смысл разделять решение задачи линейного программирования на два этапа – вычисление начального опорного плана и определение оптимального плана. Вместо этого решается расширенная задача (М-задача). Она имеет другие опорные планы (один из них всегда легко указать), но те же решения (оптимальные планы), что и исходная задача.

Рассмотрим наряду с исходной задачей (2.1) - (2.3) в канонической форме следующую расширенную задачу (М-задачу):
<img width=«224» height=«47» src=«ref-1_298679624-561.coolpic» v:shapes="_x0000_i1241">                                                                     (5.1)

<img width=«188» height=«47» src=«ref-1_298623346-464.coolpic» v:shapes="_x0000_i1242">                                                                              (5.2)

<img width=«129» height=«28» src=«ref-1_298680649-344.coolpic» v:shapes="_x0000_i1243">.                                                                                            (5.3)

Здесь М>0 – достаточно большое число.

Начальный опорный план задачи (5.1) - (5.3) имеет вид

<img width=«221» height=«28» src=«ref-1_298624159-440.coolpic» v:shapes="_x0000_i1244">

Переменные <img width=«89» height=«27» src=«ref-1_298681433-293.coolpic» v:shapes="_x0000_i1245"> называются искусственными переменными.

Таким образом, исходная задача линейного программирования с неизвестным заранее начальным опорным планом сводится к М-задаче, начальный опорный план которой известен. В процессе решения этой расширенной задачи можно либо вычислить оптимальный план задачи (2.1) - (2.3), либо убедиться в ее неразрешимости, если оказывается неразрешимой М-задача.
В соответствии с вышеизложенным имеем: требуется решить задачу (2.12), (2.13), записанную в канонической форме. Введем искусственную неотрицательную переменную х9 и рассмотрим расширенную М-задачу

<img width=«285» height=«27» src=«ref-1_298681726-516.coolpic» v:shapes="_x0000_i1246">                                          (5.4)

при условиях

<img width=«364» height=«192» src=«ref-1_298627061-1347.coolpic» v:shapes="_x0000_i1247">                      (5.5)

<img width=«45» height=«25» src=«ref-1_298619934-228.coolpic» v:shapes="_x0000_i1248">,   где  <img width=«43» height=«25» src=«ref-1_298628636-229.coolpic» v:shapes="_x0000_i1249">.

где М – сколь угодно большая положительная  величина.
Как и в L-задаче, добавление только одной искусственной переменной <img width=«19» height=«24» src=«ref-1_298629451-202.coolpic» v:shapes="_x0000_i1250"> (вместо пяти) обусловлено тем, что исходная задача уже содержит четыре единичных вектора условий А4, А5, А6, А7.

6. Решение М-задачи
II
алгоритмом симплекс-метода
Описание
II
алгоритма
Второй алгоритм(или метод обратной матрицы) симплекс метода основан на ином способе вычисления оценок <img width=«21» height=«25» src=«ref-1_298684248-200.coolpic» v:shapes="_x0000_i1251"> векторов условий Аj, чем в первом алгоритме.

Рассматривается задача линейного программирования в канонической форме(2.1) - (2.3). Пусть Х – опорный план с базисом <img width=«116» height=«25» src=«ref-1_298684448-320.coolpic» v:shapes="_x0000_i1252">. Все параметры, необходимые для оценки плана на оптимальность и перехода к лучшему плану, можно получить, преобразовывая от шага к шагу элементы матрицы <img width=«181» height=«27» src=«ref-1_298684768-402.coolpic» v:shapes="_x0000_i1253">.

Действительно, зная обратную матрицу <img width=«27» height=«25» src=«ref-1_298685170-216.coolpic» v:shapes="_x0000_i1254">, можно получить базисные составляющие опорного плана:

<img width=«164» height=«27» src=«ref-1_298685386-376.coolpic» v:shapes="_x0000_i1255">

и вычислить оценки векторов условий относительно текущего базиса

<img width=«243» height=«45» src=«ref-1_298685762-514.coolpic» v:shapes="_x0000_i1256">,                                                               (6.1)

предварительно определив вектор-строку <img width=«99» height=«24» src=«ref-1_298686276-297.coolpic» v:shapes="_x0000_i1257"> по формуле

<img width=«71» height=«25» src=«ref-1_298686573-265.coolpic» v:shapes="_x0000_i1258">

или

<img width=«211» height=«45» src=«ref-1_298686838-493.coolpic» v:shapes="_x0000_i1259">.                                                                       (6.2)

Здесь <img width=«119» height=«25» src=«ref-1_298687331-308.coolpic» v:shapes="_x0000_i1260">— вектор-строка из коэффициентов линейной формы, отвечающих базисным переменным.

Оценки <img width=«21» height=«25» src=«ref-1_298687639-201.coolpic» v:shapes="_x0000_i1261"> позволяют установить оптимальность  рассматриваемого опорного плана и определить вектор Ак, вводимый в базис. Коэффициенты <img width=«21» height=«24» src=«ref-1_298661635-204.coolpic» v:shapes="_x0000_i1262"> разложения вектора Ак по текущему базису вычисляются по формуле

<img width=«173» height=«25» src=«ref-1_298688044-396.coolpic» v:shapes="_x0000_i1263">.

Как и в I алгоритме, вектор, подлежащий исключению из базиса, определяется величиной

<img width=«119» height=«53» src=«ref-1_298688440-423.coolpic» v:shapes="_x0000_i1264">.

Таким образом при втором алгоритме на каждом шаге запоминаются базисные компоненты <img width=«81» height=«28» src=«ref-1_298688863-286.coolpic» v:shapes="_x0000_i1265">, обратная матрица <img width=«27» height=«25» src=«ref-1_298685170-216.coolpic» v:shapes="_x0000_i1266">, значение линейной формы F(X)и вектор Y, соответствующие текущему опорному плану Х. Элементы столбцов матрицы <img width=«27» height=«25» src=«ref-1_298685170-216.coolpic» v:shapes="_x0000_i1267"> удобно рассматривать как коэффициенты <img width=«21» height=«25» src=«ref-1_298689581-215.coolpic» v:shapes="_x0000_i1268"> разложения единичных векторов <img width=«77» height=«28» src=«ref-1_298689796-290.coolpic» v:shapes="_x0000_i1269"> по векторам базиса. Рекуррентные формулы, связывающие параметры двух последовательных итераций

<img width=«152» height=«49» src=«ref-1_298690086-465.coolpic» v:shapes="_x0000_i1270">;                                                                                      (6.3)

<img width=«440» height=«49» src=«ref-1_298690551-826.coolpic» v:shapes="_x0000_i1271">.              (6.3)

Здесь

<img width=«436» height=«28» src=«ref-1_298691377-679.coolpic» v:shapes="_x0000_i1272">.
Результаты вычислений сводятся в основные таблицы (вида табл. 6.1) и вспомогательную таблицу (вида табл. 6.2); столбцы В, е1, …, еm основных таблиц (все m+1 позиций) называют главной частью этих таблиц. Столбец Аk – разрешающий столбец, строка l – разрешающая строка.
Таблица 6.1                                                   Таблица 6.2


--PAGE_BREAK--