Министерство образования и науки Российской Федерации Дальневосточная Государственная Социально-Гуманитарная Академия КУРСОВАЯ РАБОТА по дисциплине: «Математическая экономика » на тему: «Применение симплекс метода в задаче оптимизации структуры сырья при планировании выпуска продукции». Руководитель работы Исполнитель Студента III курса
Факультета: Математики и информатики. Специальность: ПИвЭ Биробиджан 2006 СОДЕРЖАНИЕ ВВЕДЕНИЕ 1. СУЩНОСТЬ ПЛАНИРОВАНИЯ ВЫПУСКА ПРОДУКЦИИ 2. ПОСТАНОВКА ЗАДАЧИ ОПТИМИЗАЦИИ 3. СИМПЛЕКС МЕТОД 4. РЕШЕНИЕ ЗАДАЧИ ОПТИМИЗАЦИИ СИМПЛЕКС-МЕТОДОМ 18 ЗАКЛЮЧЕНИЕ 34 ЛИТЕРАТУРА 35
ВВЕДЕНИЕ В процессе хозяйственной деятельности сырьевая база предприятия занимает одно из центральных мест, поэтому вопрос об оптимизации сырья на предприятии при планировании выпускаемой продукции актуален в настоящее время. Актуальность данной темы также заключается в том, что в процессе производственной деятельности все предприятия сталкиваются с проблемой нехватки сырья, а также с тем, что выпускаемая продукция должна быть адекватна с экономической точки зрения, другими словами чтобы её можно было выгодно
продать и чтобы она соответствовала запросам покупателя. Учитывая всевозрастающую ограниченность ресурсов, очень важно добиваться их максимально эффективного использования. План должен быть разработан настолько умело, чтобы использование ограниченных ресурсов было оптимальным. Существует много причин, заставляющих промышленные предприятия занимаются оптимизацией структуры сырья: – улучшение финансовых показателей – повышение уровня производства – наращивание объемов
производства. Планирование выпуска продукции также имеет огромное значение для предприятия, оно тесно взаимосвязано с сырьевой базой предприятия. Деятельность по разработке планов охватывает все стороны жизни, все этапы деятельности организации. На этапе планирования определяются все необходимые параметры достижения целей — время, потребности в трудовых, материально-технических и финансовых ресурсах, сроки поставки сырья, материалов, оборудования и т. д. Принятые в плане решения должны обеспечить достижение
целей организации в запланированные сроки с минимальными издержками при требуемом качестве. Данная курсовая работа состоит из теоретической и практической частей. В теоретической части рассматривается планирование выпуска продукции на предприятии, структура используемого сырья и постановка задачи оптимизации. В практической части рассматривается задача оптимизации структуры сырья при планировании выпуска продукции на примере нефтеперерабатывающего завода, с учетом ограничений
выпуска, продиктованными экономическими факторами. Целью данной работы является оптимизация структуры сырья на нефтеперерабатывающем заводе при планировании выпуска нефтепродуктов. Объектом исследования нефтеперерабатывающий завод, его сырьевая политика. Предмет – сырьевая структура предприятия при планировании выпуска продукции. 1. СУЩНОСТЬ ПЛАНИРОВАНИЯ ВЫПУСКА ПРОДУКЦИИ. Сущность планирования продукции состоит в обосновании целей
и способов их достижения на основе выявления комплекса задач и работ, а также определения эффективных методов и способов, ресурсов всех видов, необходимых для выполнения этих задач и установления их взаимодействия. Оптимизация структуры сырья при планировании выпуска продукции является существенным источником резервов увеличения суммы прибыли. Логично предположить, что предприятию выгодно увеличивать доли тех изделий, которые приносят максимальную прибыль. Но всегда следует помнить о ряде ограничений, не позволяющих
отказаться от менее рентабельной продукции: 1) Потенциальный спрос на продукцию достаточно динамичен и дифференцирован во времени и пространстве. Те изделия и торговые марки, которые востребованы в данный момент времени, могут потерять свою потребительскую привлекательность через некоторые промежутки времени; 2) Основные производственные фонды нуждаются в постоянной эксплуатации, наладке и обслуживании. Простои оборудования – это всегда неблагоприятный фактор для производства.
Планом выпуска продукции определяются: 1) Количественные показатели производства: октановое число, число нефтяных полуфабрикатов; 2) Объем реализации, ожидаемый в планируемом периоде. Этот показатель определяется на основе объема выпуска продукции и ожидаемой средней цены реализации 1 учетной единицы продукции. Ожидаемая средняя цена реализации определяется на основе ретроспективного анализа данных за предыдущие несколько лет с учетом ожидаемых и текущих темпов инфляции.
Для каждого периода, охватываемого планом, необходимо определить две переменные: объём производства в данный период; количество ресурсов, используемых в данный период. План выпуска продукции отражает номенклатуру и ассор¬тимент производства продукции в соответствии с планом реали¬зации, обязательствами предприятия и экономическими условиями. Планирование выпускаемой продукции включает реше¬ние ряда задач.
Прежде всего, планируется номенклатура, ассортимент и объем выпуска продукции. Номенклатура производства представляет собой перечень изделий (готовых изделий, полуфаб¬рикатов и т. п.), подлежащих изготовлению на предприятии в плановом периоде. Ассортимент продукции характеризует соотно¬шение удельных весов отдельных видов изделий в общем, выпуске продукции. Номенклатура, ассортимент и объем изготовляемой предприятием продукции устанавливаются на
основе централизо¬ванного задания по поставкам важнейших видов продукции и портфеля заказов предприятия с учетом его специализации. При этом учитываются и договоры по коопе¬рированным поставкам, заключенные предприятием. На примере нефтеперерабатывающего предприятия ситуация не осложняется тем, что номенклатура выпускаемой продукции достаточно обширна (ассортиментный перечень насчитывает 3 вида наименований бензина различной октановой ёмкости), завод оснащен большим количеством оборудования различного профиля и назначения.
Целесообразно совершенствовать структуру выпуска только той продукции, удельный вес которой в общем объеме выпуска достаточно высок. Необходимым условием увеличения количества производства определенных изделий является универсальность оборудования для их производства. План выпуска продукции может повлиять на величину целого ряда издержек, в том числе: издержки хранения готовой продукции; издержки ведения портфеля отложенных заказав; издержки, связанные с внеурочной работой
или простоем работников; издержки, связанные с передачей части работ субподрядчикам; издержки, связанные с наймом и увольнением работников. Задача оптимизации структуры сырья при планировании выпуска продукции должна решаться на каждом промышленном предприятии, которое заинтересовано в максимизации прибыли от продажи выпускаемой продукции. Такая задача является задачей линейного программирования. С помощью симплекс метода будем искать решение такой задачи на нефтеперерабатывающем заводе.
2. ПОСТАНОВКА ЗАДАЧИ ОПТИМИЗАЦИИ Для решения задачи оптимизации выявляется тот параметр, который определяет степень совершенства решения возникшей проблемы. Этот параметр обычно называют целевой функцией или критерием качества. В экономических задачах это, как правило максимизация прибыли. Далее устанавливается совокупность величин, которые определяют целевую функцию. Наконец, формулируются все ограничения, которые должны учитываться при решении задачи.
После этого строится математическая модель, заключающаяся в установлении аналитической зависимости целевой функции от всех аргументов и аналитической формулировки сопутствующих задаче ограничений. Итак, пусть в результате формализации прикладной задачи установлено, что целевая функция , где множество Х – обобщение ограничений, его называют множеством допустимых решений. Существо проблемы оптимизации заключается в поиске на множестве
Х – множестве допустимых решений такого решения , при котором целевая функция f достигает наименьшего или наибольшего значения. Составной частью методов оптимизации является линейное программирование. 3. Симплекс метод Решение любой задачи линейного программирования можно найти симплексным методом. Прежде чем применять указанный метод, следует записать исходную задачу в форме основной задачи линейного программирования, если она не имеет такой формы записи.
Симплексный метод решения задачи линейного программирования основан на переходе от одного опорного плана к другому, при котором значение целевой функции возрастает (при условии, что данная задача имеет оптимальный план и каждый ее опорный план является невырожденным). Указанный переход возможен, если известен какой-нибудь исходный опорный план. Рассмотрим задачу, для которой этот план можно непосредственно записать.
Пусть требуется найти максимальное значение функции при условиях Здесь и – заданные постоянные числа Векторная форма данной задачи имеет следующий вид: найти максимум функции (22) при условиях (23) (24) где Так как то по определению опорного плана является опорным планом данной задачи (последние компонент вектора Х равны нулю). Этот план определяется системой единичных векторов которые образуют базис m-мерного пространства.
Поэтому каждый из векторов а также вектор могут быть представлены в виде линейной комбинации векторов данного базиса. Пусть Положим Так как векторы – единичные, то и а Теорема 5 (признак оптимальности опорного плана). Опорный план задачи (22) – (24) является оптимальным, если для любого j Теорема 6. Если для некоторого j=k и среди чисел нет положительных , то целевая функция (22) задачи (22) – (24) не ограничена на множестве ее планов.
Теорема 7. Если опорный план Х задачи (22) – (24) невырожден и , но среди чисел есть положительные (не все ), то существует опорный план X’ такой, что Сформулированные теоремы позволяют проверить, является ли найденный опорный план оптимальным, и выявить целесообразность перехода к новому опорному плану. Исследование опорного плана на оптимальность, а также дальнейший вычислительный процесс удобнее вести,
если условия задачи и первоначальные данные, полученные после определения исходного опорного плана, записать так, как показано в табл. 3. В столбце С6 этой таблицы записывают коэффициенты при неизвестных целевой функции, имеющие те же индексы, что и векторы данного базиса. В столбце записывают положительные компоненты исходного опорного плана, в нем же в результате вычислений получают положительные компоненты оптимального плана.
Столбцы векторов представляют собой коэффициенты разложения этих векторов по векторам данного базиса. В табл. 3 первые m строк определяются исходными данными задачи, а показатели (m+1)-й строки вычисляют. В этой строке в столбце вектора записывают значение целевой функции, которое она принимает при данном опорном плане, а в столбце вектора – значение Значение Zj находится как скалярное произведение вектора на вектор
Значение равно скалярному произведению вектора P0 на вектор : После заполнения таблицы 3 исходный опорный план проверяют на оптимальность. Для этого просматривают элементы -й строки таблицы. В результате может иметь место один из следующих трех случаев: 1) для j=m+1, (при ). Поэтому в данном случае числа для всех j от 1 до n;
2) для некоторого j, и все соответствующие этому индексу величины 3) для некоторых индексов j, и для каждого такого j , по крайней мере, одно из чисел положительно. В первом случае на основании признака оптимальности исходный опорный план является оптимальным. Во втором случае целевая функция не ограничена сверху на множестве планов, а в третьем случае можно перейти от исходного плана к новому опорному плану, при котором значение целевой функции увеличится.
Этот переход от одного опорного плана к другому осуществляется исключением из исходного базиса какого-нибудь из векторов и введением в него нового вектора. В качестве вектора, вводимого в базис, можно взять любой из векторов имеющий индекс j, для которого . Пусть, например, и решено ввести в базис вектор Для определения вектора, подлежащего исключению из базиса, находят для всех Пусть этот минимум достигается при i=r.
Тогда из базиса исключают вектор , а число называют разрешающим элементом. Столбец и строку, на пересечении которых находится разрешающий элемент, называют направляющими. После выделения направляющей строки и направляющего столбца находят новый опорный план и коэффициенты разложения векторов через векторы нового базиса, соответствующего новому опорному плану. Это легко реализовать, если воспользоваться методом
Жордана–Гаусса. При этом можно показать, что положительные компоненты нового опорного плана вычисляются по формулам (25) а коэффициенты разложения векторов через векторы нового базиса, соответствующего новому опорному плану, – по формулам (26) После вычисления и согласно формулам (25) и (26) их значения заносят в табл. 4. Элементы -й строки этой таблицы могут быть вычислены либо по формулам (27) (28) либо на основании их определения. Таблица 3 Таблица 4 Наличие двух способов нахождения элементов -й строки позволяет осуществлять
контроль правильности проводимых вычислений. Из формулы (27) следует, что при переходе от одного опорного плана к другому наиболее целесообразно ввести в базис вектор , имеющий индекс j, при котором максимальным по абсолютной величине является число . Однако с целью упрощения вычислительного процесса в дальнейшем будем вектор, вводимый в базис, определять, исходя из максимальной абсолютной величины отрицательных чисел . Если же таких чисел несколько, то в базис будем вводить вектор, имеющий такой же индекс, как
и максимальное из чисел , определяемых данными числами Итак, переход от одного опорного плана к другому сводится к переходу от одной симплекс-таблицы к другой. Элементы новой симплекс-таблицы можно вычислить как с помощью рекуррентных формул (25)-(28), так и по правилам, непосредственно вытекающим из них. Эти правила состоят в следующем. В столбцах векторов, входящих в базис, на пересечении строк и столбцов одноименных векторов проставляются
единицы, а все остальные элементы данных столбцов полагают равными нулю. Элементы векторов и в строке новой симплекс-таблицы, в которой записан вектор, вводимый в базис, получают из элементов этой же строки исходной таблицы делением их на величину разрешающего элемента. В столбце в строке вводимого вектора проставляют величину , где k – индекс вводимого вектора. Остальные элементы столбцов вектора и новой симплекс-таблицы вычисляют по правилу треугольника.
Для вычисления какого-нибудь из этих элементов находят три числа: 1) число, стоящее в исходной симплекс-таблице на месте искомого элемента новой симплекс-таблицы; 2) число, стоящее в исходной симплекс-таблице на пересечении строки, в которой находится искомый элемент новой симплекс-таблицы, и столбца, соответствующего вектору, вводимому в базис; 3) число, стоящее в новой симплекс-таблице на пересечении столбца, в котором стоит искомый элемент,
и строки вновь вводимого в базис вектора (как отмечено выше, эта строка получается из строки исходной симплекс-таблицы делением ее элементов на разрешающий элемент). Эти три числа образуют своеобразный треугольник, две вершины которого соответствуют числам, находящимся в исходной симплекс-таблице, а третья – числу, находящемуся в новой симплекс-таблице. Для определения искомого элемента новой симплекс-таблицы из первого числа вычитают произведение второго
и третьего. После заполнения новой симплекс-таблицы просматривают элементы -й строки. Если все , то новый опорный план является оптимальным. Если же среди указанных чисел имеются отрицательные, то, используя описанную выше последовательность действий, находят новый опорный план. Этот процесс продолжают до тех пор, пока либо не получают оптимальный план задачи, либо не устанавливают ее неразрешимость.
При нахождении решения задачи линейного программирования мы предполагали, что эта задача имеет опорные планы и каждый такой план является невырожденным. Если же задача имеет вырожденные опорные планы, то на одной из итераций одна или несколько переменных опорного плана могут оказаться равными нулю. Таким образом, при переходе от одного опорного плана к другому значение функции может остаться прежним. Более того, возможен случай, когда функция сохраняет свое значение в течение нескольких итераций, а
также возможен возврат к первоначальному базису. В последнем случае обычно говорят, что произошло зацикливание. Однако при решении практических задач этот случай встречается очень редко, поэтому мы на нем останавливаться не будем. Итак, нахождение оптимального плана симплексным методом включает следующие этапы: 1. Находят опорный план. 2. Составляют симплекс-таблицу. 3. Выясняют, имеется ли хотя бы одно отрицательное число .
Если нет, то найденный опорный план оптимален. Если же среди чисел имеются отрицательные, то либо устанавливают неразрешимость задачи, либо переходят к новому опорному плану. 4. Находят направляющие столбец и строку. Направляющий столбец определяется наибольшим по абсолютной величине отрицательным числом , а направляющая строка – минимальным из отношений компонент столбца вектора к положительным компонентам направляющего столбца. 5.
По формулам (25) – (28) определяют положительные компоненты нового опорного плана, коэффициенты разложения векторов Pj по векторам нового базиса и числа , . Все эти числа записываются в новой симплекс-таблице. 6. Проверяют найденный опорный план на оптимальность. Если план не оптимален и необходимо перейти к новому опорному плану, то возвращаются к этапу 4, а в случае получения оптимального плана или установления неразрешимости процесс решения задачи заканчивают.
4. Решение задачи линейной оптимизации симплекс – методом. 4.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 4.2. Математическая постановка задачи Исходя из условий задачи, необходимо максимизировать следующую целевую функцию: (1.1) ПРИ ОГРАНИЧЕНИЯХ (1.2) , где В этих выражениях: – объемы бензина А-го, В-го и С-го сорта соответственно. Тогда объёмная доля первой компоненты (алкилата) в бензине А. объёмная доля первой компоненты (алкилата) в бензине
В. объёмная доля первой компоненты (алкилата) в бензине С. и т.д. Целевая функция выражает стоимость всей продукции в зависимости от объема производимого бензина каждого сорта. Таким образом, для получения максимальной стоимости продукции необходимо максимизировать целевую функцию (1.1) с соблюдением всех условий задачи, которые накладывают ограничения (1.2) на . 4.3. Приведение задачи к канонической форме Задача линейного программирования записана в канонической
форме, если она формулируется следующим образом. Требуется найти вектор , доставляющий максимум линейной форме (2.1) при условиях (2.2) (2.3) где Перепишем исходную задачу (1.1) – (1.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.1), (1.2) свели к задаче (2.9) – (2.11) с меньшим числом ограничений. Для записи неравенств (2.10) в виде уравнений введем неотрицательные дополнительные переменные , и задача (2.9) – (2.11) запишется в следующей эквивалентной форме: (2.12) (2.13) , где Задача (2.12), (2.13) имеет каноническую форму. 4.4.
Постановка L-задачи Вспомогательная задача для нахождения начального опорного плана задачи (2.12) – (2.13) в канонической форме состоит в следующем. Требуется обратить в максимум при условиях , где . рассматривая в качестве исходного опорного плана план Здесь добавление только одной дополнительной переменной (вместо пяти) обусловлено тем, что исходная задача уже содержит четыре единичных вектора условий
А4, А5, А6, А7. 4.5. Решение 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-задачи. Наибольшее значение линейной формы равно .
Таблица 1 4.7. Формирование начального опорного плана исходной задачи линейного программирования из оптимального плана L-задачи. Поскольку , где – оптимальный опорный план L-задачи, то является начальным опорным планом исходной задачи (2.12) – (2.13). 4.8. Решение исходной задачи I алгоритмом симплекс-метода Описание I алгоритма Симплекс-метод позволяет, отправляясь от некоторого исходного опорного плана и
постепенно улучшая его, получить через конечное число итераций оптимальный план или убедиться в неразрешимости задачи. Каждой итерации соответствует переход от одной таблицы алгоритма к следующей. Таблица, отвечающая опорному плану в ν-й итерации имеет вид табл. Таблица 2 C … … … + N B … … … t 1 … … … l … … … m … … … m+1 – – … … … – Заполнение таблицы, соответствующей исходному опорному плану (0-й итерации).
Пусть некоторый опорный план задачи (2.1) – (2.3) с базисом . Тогда – базисные компоненты, а – небазисные компоненты. Вычисляем коэффициенты разложения векторов Аj по базису Б0 (в случае, если Б0 является единичной матрицей, ) и находим оценки . Далее определяем значение линейной формы Полученные результаты записываем в таблицу 2
В первом столбце 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)-ю итерацию. Последующие итерации проводятся аналогично. Вычисления продолжаются до тех пор, пока не будет получен
оптимальный план либо будет установлено, что исследуемая задача неразрешима. 4.9 Решение исходной задачи Весь процесс решения исходной задачи (2.12) – (2.13) приведен в табл. 2 Заполнение таблицы, отвечающей 0-й итерации, происходит на основе табл. 1 (см. итерацию 1) следующим образом. Главная часть таблицы 0-й итерации исходной задачи (за исключением (m+1)-й строки) полностью повторяет главную часть таблицы заключительной итерации
L-задачи без столбца А9. Также без изменений остается столбец базисных векторов Бх. Строка С коэффициентов линейной формы исходной задачи и столбец Сх коэффициентов при базисных переменных заполняются исходя из (2.12). С учетом новых коэффициентов С пересчитываются значение линейной формы F и оценки . Заполнение таблиц, отвечающих последующим итерациям, происходит в соответствии с описанным
выше первым алгоритмом. Таблица 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 тыс.л. бензина В из полуфабрикатов в следующих количествах: – Алкитата тыс.л. – Крекинг-бензина тыс.л. – Бензина прямой перегонки тыс.л. Изопентона тыс.л. ЗАКЛЮЧЕНИЕ Развитие современного общества характеризуется повышением технического уровня, усложнением организационной структуры производства, углублением общественного разделения труда, предъявлением высоких требований к методам планирования производственной деятельности.
В этих условиях только научный подход к экономике предприятий позволит обеспечить высокие темпы развития промышленности. Научного подхода требует и решение тактических и стратегических задач. В настоящее время новейшие достижения математики и современной вычислительной техники находят все более широкое применение как в экономических исследованиях и планировании, так и в других задачах. Этому способствует развитие таких разделов математики как математическое программирование, теория игр,
теория массового обслуживания, а также бурное развитие быстродействующей электронно-вычислительной техники. Уже накоплен большой опыт постановки и решения экономических и тактических задач с помощью математических методов. Особенно успешно развиваются методы оптимального управления. Экономика и производство развивается быстро там, где широко используются математические методы. Список литературы: 1. Тихонов А. Н Костомаров Л. П.
Вводные лекции по прикладной математике. М Наука, 1984. 2. Колемаев В.А. Математическая экономика. -М.: Инфра-М, 1998. 3. Малыхин В.И. Математическое моделирование экономики. -М: УРАО, 1998. 4. Васильев Ю.Н. Прогнозирование и перспективное планирование в промышленности Л.: Лениздат 1973. 5. Ершов А.Т Карандаев И.С Шананин
Н.А. Планирование производства и линейное программирование. МИУ, М 1981.