Симплекс метод при решении экономических задач

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

В столбце Б_х, в пятой позиции базиса место вектора А₉ занимает вектор А₁. Соответствующий ему коэффициент линейной формы С₄₁ = 0 помещаем в столбец С_х. Главная часть таблицы 1 заполняется по данным таблицы 0 в соответствии с рекуррентными формулами. Так как все , то опорный план является решением L-задачи. Наибольшее значение линейной формы равно .

 

Таблица 4 

 

 

 

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

 

Поскольку , где

 - оптимальный опорный план L-задачи, то

 является начальным опорным планом исходной задачи (2.12) - (2.13).

 

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

 

Описание I алгоритма

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

Таблица 5

 

			C		…		…		…		+
N			B		…		…		…		t
1					…		…		…
l					…		…		…
m					…		…		…
m+1	–	–			…		…		…		–

 

Заполнение таблицы, соответствующей  исходному опорному плану (0-й итерации). Пусть  некоторый опорный план задачи (2.1) - (2.3) с базисом . Тогда – базисные компоненты, а – небазисные компоненты.

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

(в случае, если Б₀ является единичной матрицей, ) и находим оценки . Далее определяем значение линейной формы

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

В первом столбце N таблицы указываются номера строк. Номера первых m строк совпадают с номерами позиций базиса. Во втором столбце С_х записываются коэффициенты линейной формы при базисных переменных. Столбец Б_х содержит векторы базиса . В столбце В записываются базисные переменные опорного плана. Столбцы содержат коэффициенты разложения соответствующих векторов условий по векторам базиса. Все вышесказанное относится только к первым m строкам таблицы. Последняя (m+1)-я строка таблицы заполняется последовательно значением линейной формы F и оценками . Позиции таблицы, которые не должны заполняться, прочеркиваются.

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

Порядок вычислений в  отдельной итерации:

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

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

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

Просматривается (m+1)-я строка таблицы ν. Если все , то опорный план, полученный после ν-й итерации, является оптимальным (случай 1), завершаем решение задачи. Пусть теперь имеются отрицательные оценки. Проверяем знаки элементов столбцов с . Наличие по крайней мере одного столбца , для которого и все , свидетельствует о неразрешимости задачи (случай 2). Установив это, прекращаем вычисления.

Если в каждом столбце  , для которого , содержится хотя бы один положительный коэффициент , то опорный план является неоптимальным (случай 3). Переходим ко II этапу.

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

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

.

После этого заполняется  последний столбец таблицы ν – столбец t. В него записываются отношения базисных переменных (элементы столбца В) к соответствующим составляющим (элементы столбца A_k). Т.е. заполняются только те позиции, для которых . Если , то в позиции i столбца t записывается . Вектор базиса , на котором достигается t₀,

,

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

Столбец A_k , отвечающий вектору, вводимому в базис, и l-я строка, соответствующая вектору , исключаемому из базиса, называется соответственно разрешающим столбцом и разрешающей строкой. Элемент , расположенный на пересечении разрешающего столбца и разрешающей строки, называется разрешающим элементом.

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

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

.

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

.

Здесь

.

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

4.8 Решение исходной задачи

Весь процесс решения исходной задачи (2.12) - (2.13) приведен в табл. 6. Заполнение таблиц, отвечающих последующим итерациям, происходит в соответствии с описанным выше первым алгоритмом.

Таблица 6 

 

Решение исходной задачи (2.12) - (2.13) получено за 3 итерации. Оптимальный план ее равен и .

Найденное решение  задачи  в канонической форме (2.12) - (2.13) соответствует решению (3.1) общей задачи линейного программирования (2.9) - (2.11), записанной для новых переменных . Для общей задачи из (2.9) следует, что (3.2).

Вернемся к задаче (1.1), (1.2) со старыми переменными . Учитывая (3.1) и (3.2) из (2.7) и (2.8) получим

 

        (3.3)

и

.                (3.4)

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

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

• Алкитата тыс.л.
• Крекинг-бензина тыс.л.
• Бензина прямой перегонки тыс.л.
• Изопентона тыс.л.

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

• Алкитата тыс.л.
• Крекинг-бензина тыс.л.
• Бензина прямой перегонки тыс.л.
• Изопентона тыс.л.

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

• Алкитата тыс.л.
• Крекинг-бензина тыс.л.
• Бензина прямой перегонки тыс.л.

               Изопентона  тыс.л.

 

 

       

 

 

Заключение

 

Развитие современного общества характеризуется повышением технического уровня, усложнением организационной структуры производства, углублением общественного разделения труда, предъявлением высоких требований к методам планирования производственной деятельности. В этих условиях только научный подход к экономике предприятий позволит обеспечить высокие темпы развития промышленности. Научного подхода требует и решение тактических и стратегических задач.

В настоящее время  новейшие достижения математики и современной вычислительной техники находят все более широкое применение как в экономических исследованиях и планировании, так и в других задачах. Уже накоплен большой опыт постановки и решения экономических и тактических задач с помощью математических методов. Особенно успешно развиваются методы оптимального управления. Экономика и производство развивается быстро там, где широко используются математические методы.

Целью данной работы являлась оптимизация структуры сырья  на нефтеперерабатывающем заводе при  планировании выпуска нефтепродуктов.

В курсовой работе математически  проведено обоснование структуры  сырья при производстве готового продукта. Таким образом, получена максимальная цена продукции. На основе применения симплекс метода показана оптимальная  модель производства продукции на нефтеперерабатывающем заводе.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Список литературы:

 

1. Малыхин В.И. Математическое моделирование экономики. -М: УРАО, 2004.
2. Путилин А.Б. , Вычислительная техника и программирование в измерительных информационных системах. – Дрофа, 2006 
3. Тихонов А. Н., Костомаров Л. П. Вводные лекции по прикладной математике. М., Наука, 2002.
4. Колемаев В.А.  Математическая экономика. -М.: Инфра-М, 2006.
5. Воеводин В. В., Вычислительная математика и структура алгоритмов 
   - М.: Изд-во МГУ,  2006