Xreferat.com » Рефераты по экономико-математическому моделированию » Анализ экономических задач симплексным методом

Анализ экономических задач симплексным методом

alt="" width="334" height="401" align="ABSMIDDLE" />. Двойственная задача решается на минимум, и ее система ограничений имеет вид неравенств типа .

  • Число ограничений прямой задачи равно числу пере­менных двойственной, а число ограничений двойствен­ной — числу переменных прямой.

  • Все переменные в обеих задачах неотрицательны.

    Теорема. Для любых допустимых планов и прямой и двойственной ЗЛП справедливо неравенство , т.е.

    (7) – основное неравенство теории двойственности.

    Теорема. (критерий оптимальности Канторовича)

    Если для некоторых допустимых планов и пары двойственных задач выполняется неравенство , то и являются оптимальными планами соответствующих задач.

    Теорема. (малая теорема двойственности)

    Для су­ществования оптимального плана любой из пары двойст­венных задач необходимо и достаточно существование допустимого плана для каждой из них.


    §5. Основные теоремы двойственности

    и их экономическое содержание

    Теорема.

    Если одна из двойственных задач имеет оптимальное решение, то и другая имеет оптимальное решение, причем экстремальные значения целевых функ­ций равны: . Если одна из двойственных задач неразрешима вследствие неограниченности целевой функции на множестве допустимых решений, то система ограничений другой задачи противоречива.

    Экономическое содержание первой теоремы двойствен­ности состоит в следующем: если задача определения оптимального плана, максимизирующего выпуск продук­ции, разрешима, то разрешима и задача определения оценок ресурсов. Причем цена продукции, полученной при реализации оптимального плана, совпадает с суммар­ной оценкой ресурсов. Совпадение значений целевых функций для соответствующих планов пары двойственных задач достаточно для того, чтобы эти планы были опти­мальными. Это значит, что план производства и вектор оценок ресурсов являются оптимальными тогда и только тогда, когда цена произведенной продукции и суммарная оценка ресурсов совпадают. Оценки выступают как инструмент балансирования затрат и результатов. Двойст­венные оценки, обладают тем свойством, что они гаранти­руют рентабельность оптимального плана, т. е. равенство общей оценки продукции и ресурсов, и обусловливают убыточность всякого другого плана, отличного от опти­мального. Двойственные оценки позволяют сопоставить и сбалансировать затраты и результаты системы.


    Теорема. (о дополняющей нежесткости )

    Для того, чтобы планы и пары двойственных задач были оптимальны, необходимо и достаточно выполнение условий:

    (1)

    (2)

    Условия (1), (2) называются условиями допол­няющей нежесткости. Из них следует: если какое-либо ограничение одной из задач ее оптимальным планом обра­щается в строгое неравенство, то соответствующая компо­нента оптимального плана двойственной задачи должна равняться нулю; если же какая-либо компонента опти­мального плана одной из задач положительна, то соответ­ствующее ограничение в двойственной задаче ее опти­мальным планом должно обращаться в строгое равенство.

    Экономически это означает, что если по некоторому оптимальному плану производства расход i -го ресурса строго меньше его запаса , то в оптимальном плане соответствующая двойственная оценка единицы это­го ресурса равна нулю. Если же в некотором оптимальном плане оценок его i -я компонента строго больше нуля, то в оптимальном плане производства расход соответствую­щего ресурса равен его запасу. Отсюда следует вывод: двойственные оценки могут служить мерой дефицитности ресурсов. Дефицитный ресурс (полностью используемый по оптимальному плану производства) имеет положитель­ную оценку, а ресурс избыточный (используемый не полно­стью) имеет нулевую оценку.


    Теорема .(об оценках). Двойственные оценки пока­зывают приращение функции цели, вызванное малым из­менением свободного члена соответствующего ограниче­ния задачи математического программирования, точнее

    (3)


    §6. Примеры экономических задач


    5.1 Задача о наилучшем использовании ресурсов. Пусть некоторая производственная единица (цех, завод, объеди­нение и т. д.), исходя из конъюнктуры рынка, технических или технологических возможностей и имеющихся ресур­сов, может выпускать n различных видов продукции (то­варов), известных под номерами, обозначаемыми индек­сом j . Ее будем обозначать . Предприятие при производстве этих видов продукции должно ограни­чиваться имеющимися видами ресурсов, технологий, дру­гих производственных факторов (сырья, полуфабрикатов, рабочей силы, оборудования, электроэнергии и т. д.). Все эти виды ограничивающих факторов называют ингре­диентами . Пусть их число равно m; припишем им индекс i . Они ограничены, и их количества равны соответственно условных единиц. Таким обра­зом, - вектор ресурсов. Известна экономическая выгода (мера полезности) производства продукции каждого вида, исчисляемая, скажем, по отпуск­ной цене товара, его прибыльности, издержкам произ­водства, степени удовлетворения потребностей и т. д. При­мем в качестве такой меры, например, цену реализации

    , т. е. —вектор цен. Известны также технологические коэффициенты , кото­рые указывают, сколько единиц i–го ресурса требуется для производства единицы продукции j-го вида. Матрицу коэффициентов называют технологической и обо­значают буквой А. Имеем . Обозначим через план производства, показывающий, какие виды товаров нужно произво­дить и в каких количествах, чтобы обеспечить предприя­тию максимум объема реализации при имеющихся ре­сурсах.

    Так как - цена реализации единицы j'-й продукции, цена реализованных единиц будет равна , а общий объем реализации

    Это выражение — целевая функция, которую нужно мак­симизировать.

    Так как - расход i-го ресурса на производство единиц j-й продукции, то, просуммировав расход i-го ресурса на выпуск всех n видов продукции, получим общий расход этого ресурса, который не должен превосхо­дить единиц:

    Чтобы искомый план был реализован, наряду с ограничениями на ресурсы нужно наложить условие неотрицательности на объёмы выпуска продукции:

    .

    Таким образом, модель задачи о наилучшем использовании ресурсов примет вид:

    (1)

    при ограничениях:

    (2)

    (3)

    Так как переменные входят в функцию и систему ограничений только в первой степени, а показатели являются постоянными в планируемый период, то (1)-(3) – задача линейного программирования.


    5.2 Задача о смесях.

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

    5.3 Задача о раскрое материалов.

    Сущность задачи об оптимальном раскрое состоит в разработке таких техно­логически допустимых планов раскроя, при которых полу­чается необходимый комплект заготовок, а отходы (по длине, площади, объему, массе или стоимости) сводятся к минимуму. Рассмотрим простейшую модель раскроя по одному измерению. Более сложные постановки ведут к задачам целочисленного программирования.

    5.4 Транспортная задача.

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

    5.5 Задача о размещении заказа.

    Речь идет о задаче рас­пределения заказа (загрузки взаимозаменяемых групп оборудования) между предприятиями (цехами, станками, исполнителями) с различными производственными и тех­нологическими характеристиками, но взаимозаменяемыми в смысле выполнения заказа. Требуется составить план размещения заказа (загрузки оборудования), при кото­ром с имеющимися производственными возможностями заказ был бы выполнен, а показатель эффективности до­стигал экстремального значения.


    §7. Анализ задачи об оптимальном использовании сырья.


    Исходя из специализации и своих технологических возможностей предприятие может выступать четыре вида продукции. Сбыт любого количества обеспечен. Для изготовления этой продукции используются трудовые ресурсы, полуфабрикаты и станочное оборудование. Общий объём ресурсов, расход каждого ресурса за единицу продукции, приведены в таблице 1. Требуется определить план выпуска, доставляющий предприятию максимум прибыли. Выполнить после оптимизационный анализ решения и параметров модели.


    Ресурсы Выпускаемая продукция

    Объём

    Ресурсов

    Трудовые ресурсы, чел-ч 4 2 2 8 4800

    Полуфабрикаты, кг 2 10 6 0 2400

    Станочное оборудование, станко-ч 1 0 2 1 1500
    Цена единицы продукции, р. 65 70 60 120

    Решение.

    Пусть - объёмы продукции планируемый к выпуску; - сумма ожидаемой выручки.

    Математическая модель пря мой задачи:

    Математическая модель двойственной задачи:

    По условиям примера найти:

    1. Ассортимент выпускаемой продукции, обеспечивающий предприятию максимум реализации (максимум выручки)

    2. Оценки ресурсов, используемых при производстве продукции.


    Симплексным методом решаем прямую задачу, модель которой составлена выше в таблице1.

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

    Основные переменные показывают, что продукциюи выпускать нецелесообразно, а продукции следует произвести 400 ед., - 500 ед.

    Дополнительные переменные и показывают, что ресурсы используются полностью , а вот равенство свидетельствует о том, что 200 единиц продукции осталось неиспользованным.


    Номера ит. БП Сб

    65 70 60 120 0 0 0
    0

    0 4800 4 2 2 8 1 0 0

    0 2400 2 10 6 0 0 1 0

    0 1500 1 0 2 1 0 0 1

    0 -65 -70 -60 -120 0 0 0
    1

    120 600 1/2 1/4 1/4 1 1/8 0 0

    0 2400 2 0 6 0 0 1 0

    0 900 1/2 -1/4 7/4 0 -1/8 0 1

    72000 -5 -40 -30 0 15 0 0
    2

    120 500 5/12 -1/6 0 1 1/8 -1/24 0

    60 400 1/3 5/3 1 0 0 1/6 0

    0 200 -1/12 -19,6 0 0 -1/8 -7/24 1

    84000 5 10 0 0 15 5 0

    Выпишем из таблицы2. Компоненты оптимального плана двойственной задачи – двойственные оценки. В канонической форме прямой задачи переменные - являются свободными, а дополнительные переменные - базисными. В канонической форме двойственной задачи свободными будут переменные - а базисными

    Соответствие между переменными примет вид

    Учитывая это соответствие, выпишем из индексной строки последней итерации компоненты искомого плана - двойственные оценки.

    min f = max Z =84000.

    Запишем это неравенство в развернутой форме:

    48000*15 + 2400*5 + 1500*0 = 65*0 + 70*0 + 60*400 + 120*500

    Учитывая, что компонеты представляют собой оценки ресурсов заключаем:

    При оптимальном плане оценка ресурсов, затраченных на выпуск продукции, совпадает с оценкой произведенной продукции.

    Теперь установим степень дефицитно­сти используемых ресурсов и обоснуем рентабельность оптимального плана.

    Мы нашли оптимальный план выпуска продукции. При этом плане третье ограничение прямой задачи выполняется как строгое неравенство:

    0+2-400+500= 1300 мень­ше его запаса, т. е. ресурс избыточный. Именно поэтому в оптималь­ном плане двойственной задачи оценка этого ресурса равна нулю.

    А вот оценки и ресурсов и выражаются положительными числами 15 и 5, что свидетельствует о дефицитности этих ресурсов: они при оптимальном плане используются полностью. В самом деле, ограни­чения по этим ресурсам выполняются как строгие равен­ства: 4.0+2.0+2.400+8.500=4800, 2-0+10.0+6.400=2400.

    Поскольку 15>5, ресурс считается более дефицитным, чем ресурс .

    На основе теоремы (о дополняющей нежесткости) нетрудно объяснить, почему не вошла в опти­мальный план продукция и : первое и второе ограничения двой­ственной задачи выполняются как строгие неравенства: 4-15+2-5+0>65, 2-15+10*5>70.

    Это означает, что оценки ресурсов, расходуемых на изготовление единицы продукции и , превышают оценки единицы этой продукции. Понятно, что такую продукцию выпу­скать предприятию невыгодно. Что же касается продукции и , то выпуск ее оправдан, поскольку оценка израсходо­ванных ресурсов совпадает с оценкой произведенной продукции: 2*15+ +6*5+2*0=60, 8*15+0=120.

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

    Рассмотрим возможность дальней­шего совершенствования оптимального ассортимента выпускаемой про­дукции.

    Выше установлено, что ресурсы и являются дефицитными. В связи с этим на основе теоремы (об оценках) можно утверждать, что на каждую единицу ресурса , введенную дополнительно в производ­ство, будет получена дополнительная выручка , численно равная . В самом деле, при получаем . По тем же причинам каждая дополнительная единица ресурсаобеспечит прирост выручки, равный 5 р. Теперь становится понятно, почему ресурс считается более дефицитным по сравнению с ресурсом : он может содействовать получению большей выручки.

    Что же касается избыточного ресурса , то увеличение его запаса не приведет к росту выручки, поскольку . Из приве­денных рассуждений следует, что оценки ресурсов позволяют совершен­ствовать план выпуска продукции.

    Выясним экономический смысл оценок продукции ,,,.

    По оптимальному плану выпускать следует продукцию и . Оценки и этих видов продукции равны нулю. Что это означает, практически станет ясно, если представить оцен­ки в развернутой записи:

    Таким образом, нулевая оценка показывает, что эта продукция является неубыточной, поскольку оценка ресурсов, расходуемых на вы­пуск единицы такой продукции, совпадает с оценкой единицы изготовлен­ной продукции.

    Что же касается продукции и являющейся, как установлено выше, убыточной, а потому и не вошедшей в оптимальный план, то для ее оценок и получаем:

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


    §8. Программа и расчеты.


    {Программа составлена для решения задачи линейного программирования

    симплексным методом}

    uses crt;

    const n=2;{число неизвестных исходной задачи}

    m=3;{число ограничений}

    m1=0;{последняя строка равенств}

    m2=1;{последняя строка неравенств вида >=}

    label 5,15,20,10;

    var

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

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

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