Рефетека.ру / Математика

Курсовая работа: Решение задач линейной оптимизации симплекс – методом

Курсовая работа по дисциплине «Численные методы оптимизации»

Выполнил: ст.гр.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 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) в канонической форме состоит в следующем.

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

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

при условиях

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

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

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

рассматривая в качестве исходного опорного плана план

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

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

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

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

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

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

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

0

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

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

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

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

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 могут быть и отрицательными.

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

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

  1. • Решение задач линейной оптимизации симплекс - методом
  2. • Использование табличного симплекс-метода для решения задач ...
  3. • Табличный симплекс-метод
  4. • Решение задач линейного программирования симплекс ...
  5. • Решение задачи линейного программирования симплекс-методом
  6. • Задача обработки решёток
  7. • Решение задач линейного программирования симплекс ...
  8. • Решения задачи планирования производства ...
  9. • Задача обработки решеток
  10. • Экономико-математические методы и прикладные модели
  11. • Симплекс метод в форме презентации
  12. • Применение симплекс-метода
  13. • Графический метод и симплекс-метод решения задач линейного ...
  14. • Решения задач линейного программирования ...
  15. • Решение задачи линейного программирования ...
  16. • Решение транспортной задачи линейного ...
  17. • Использование линейного программирования для решения ...
  18. • Линейное программирование
  19. • Решение задач линейного программирования
Рефетека ру refoteka@gmail.com