Xreferat.com » Рефераты по математике » Решение задач линейной оптимизации симплекс – методом

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

А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 , отвечающий вектору, вводимому в базис, и 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, соответствующие текущему опорному плану Х. Элементы столбцов матрицы Решение задач линейной оптимизации симплекс – методом удобно рассматривать как коэффициенты Решение задач линейной оптимизации симплекс – методом разложения единичных векторов

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.
Подробнее

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: