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

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

Выполнил: ст.гр.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 тыс.л.

Сводная таблица условий задачи:

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

Заполнение таблицы, соответствующей исходному опорному плану (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