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

Введение.

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

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

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

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

2)   целевую функцию (функцию цели,показатель эф­фективности, критерий оптимальности, функционал зада­чи и др.).Целевая функция позволяет выбирать наилуч­ший вариант -из множества возможных.Наилучший ва­риант доставляет целевой функции экстремальное значе­ние. Этоможет быть прибыль, объем выпуска или реализации, затраты производства, издержкиобращения, уровень об­служивания или дефицитности, число комплектов, отходы ит. д.;

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

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

Начало линейномупрограммированию было положено в 1939 г. советским математиком-экономистом Л.В. Кан­торовичем в работе «Математические методы организации и планированияпроизводства». Появление этой работы открыло новый этап в применении математикив эконо­мике. Спустя десять лет американский математик Дж. Данциг разработалэффективный метод решения данного класса задач — симплекс-метод. Общая идея симплексногометода (ме­тода последовательного улучшения плана) для решения ЗЛП состоитв следующем:

1)   умение находить начальный опорныйплан;

2)   наличие признака оптимальностиопорного пла­на;

3)   умение переходить к нехудшемуопорному плану.

§1.Задача линейного программирования  и />свойства/> ее решений.

1.1 Понятие линейного программирования. Линейное про­граммирование—разделматематического программирования, применяемый при разработке методов отысканияэкстремума линейных функций нескольких переменных при линейных дополни­тельныхограничениях, налагаемых на переменные. По типу решаемых задач его методыразделяются на уни­версальные и специальные. С помощью универсальных методовмогут решаться любые задачи линейного про­граммирования (ЗЛП).Специальные методы учитывают особенности модели задачи, ее целевой функции исистемы ограничений.

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

Формы записи задачилинейного программирования:

Общей задачей линейногопрограммирования называют задачу

/>  (1)

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

/>  (2)

/>  (3)

/>       (4)

/>     (5)

/> — произвольные />   (6)

где /> — заданные действительныечисла; (1) – целевая функция; (1) – (6) –ограничения;

/> - план задачи.

1.2 Свойства решений.

Пусть ЗПЛ представлена вследующей записи:

/>          (7)

/>     (8)

/>                     (9)

Чтобы задача (7) – (8)имела решение, системе её ограничений (8) должна быть совместной. Это возможно,если  r этой системы не больше числанеизвестных n. Случай r>n вообще невозможен. При r= n система имеет единственное решение, которое будет при/>оптимальным. В этом случаепроблема выбора оптимального решения теряет смысл. Выясним структуру координатугловой точки много­гранных решений. Пусть r<n. В этом случае система векторов />содержит базис —максимальную линейно независимую подсистему векторов, через которую любойвектор системы может быть выражен как ее линей­ная комбинация. Базисов, вообщеговоря, может быть несколько, но не более />.Каждый из них состоит точно из rвекторов. Переменные ЗЛП, соответствующие r век­торам базиса, называют, как известно, базисными иобо­значают БП. Остальные n – r переменныхбудут свобод­ными, их обозначают СП. Неограничивая общности, будем считать, что базис составляют первые m векторов />.Этому базису соответствуют базисные переменные />,а свобод­ными будут переменные />.

Если свободные переменныеприравнять нулю, а базис­ные переменные при этом примут неотрицательные значе­ния,то полученное частное решение системы (8) назы­вают опорным решением (планом).

 

Теорема. Если система векторов /> содер­жит m линейно независимых векторов />, то допустимый план />   (10) является крайней точкой многогранникапланов.

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

 

§2.Графический способ решения ЗЛП.

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

Пусть дана задача

/>           (11)

/>         (12)

/>                         (13)

Дадим геометрическуюинтерпретацию элементов этой задачи. Каждое из ограничений (12), (13) задает наплоскости />некоторую полуплоскость. Полу­плоскость— выпуклое множество. Но пересечение любого числа выпуклых множеств являетсявыпуклым множест­вом. Отсюда следует, что область допустимых решений задачи(11) — (13)  есть выпуклое множество.

Перейдем к геометрическойинтерпретации целевой функции. Пусть область допустимых решений ЗЛП — не­пустоемножество, например многоугольник />.

/>

 Выберем произвольноезначение целевой функ­ции/>.Получим />. Это уравнение пря­мой линии. В точках прямой NМ целевая функция сохра­няет одно и то жепостоянное значение />. Считая в ра­венстве(11) /> параметром, получимуравнение семей­ства параллельных прямых, называемых линиями уровня целевойфункции (линиями постоянного значения).

Найдём частныепроизводные целевой функции по /> и />

/>           (14)

/>           (15)

Частная производная (14) ((15)) функции пока­зывает скорость ее возрастания вдоль данной оси. Следо­вательно,/> и />— скоростивозрастания /> соответст­венно вдоль осей /> и />. Вектор /> называ­ется градиентомфункции. Он показывает направление наискорейшего возрастания целевой функции:

/>

Вектор —/>  указывает направлениенаискорейшего убывания целевой функции. Его называют антигра­диентом.

Вектор />перпендикулярен к прямым /> семейства  />

Из геометрической интерпретации элементов ЗЛП вы­текаетследующий порядок ее графического решения.

1.         С учетом системыограничений строим область до­пустимых решений />

2.         Строим вектор /> наискорейшего возра­станияцелевой функции — вектор градиентного направ­ления.

3.         Проводимпроизвольную линию уровня  /> 

4.         При решениизадачи на максимум перемещаем ли­нию уровня /> внаправлении вектора /> так, чтобы онакасалась области допустимых решений в ее крайнем по­ложении (крайней точке).В случае решения задачи на минимум линию уровня /> перемещают вантиградиентном направлении

5.         Определяемоптимальный план /> и экстре­мальноезначение целевой функции />.

 

§3.Симплексный метод.

Общая идея симплексного метода (ме­тодапоследовательного улучшения плана) для решения ЗЛП состоит

1)   умение находить начальный опорныйплан;

2)   наличие признака оптимальностиопорного пла­на;

3)   умение переходить к нехудшемуопорному плану.

Пусть ЗЛП представлена системойограничений в каноническом виде:

/>.

Говорят, что ограничение ЗЛП имеетпредпочтительный вид, если при неотрицательной правой части />левая часть ограниченийсодержит переменную, входящую с коэффициентом, равным единице, а в остальныеограничения равенства — с коэффициентом, равным нулю.

Пусть система ограничений имеет вид

/>

Сведем задачу к каноническому виду.Для этого прибавим к левым частям неравенств дополнительные переменные />    />. Получим систему, эквивалентнуюисходной:

/>,

 которая имеет предпочтительный вид

/>.

В целевую функцию дополнительныепеременные вводятся с коэффициентами, равными нулю /> />.

Пусть далее система ограничений имеетвид

/>

Сведём её к эквивалентной вычитаниемдополнительных переменных />    />из левых частей неравенствсистемы. Получим систему

/>

Однако теперь система ограничений неимеет предпочтительного вида, так как дополнительные переменные /> входят в левую часть (при />) с коэффициентами, равными–1. Поэтому, вообще говоря, базисный план /> неявляется допустимым. В этом случае вводится так называемый искусственный базис.К левым частям ограниче­ний-равенств, не имеющих предпочтительного вида, добав­ляютискусственные переменные />. Вцелевую функцию переменные />, вводятс коэффициентом М в случае реше­ния задачи на минимум и с коэффициентом -М дляза­дачи на максимум, где М — большое положительное число. Полученная задачаназывается М-задачей, соот­ветствующей исходной. Она всегда имеет предпочти­тельныйвид.

Пусть исходная ЗЛП имеет вид

/>             (1)

/>         (2)

/>    />                  (3)

причём ни одно из ограничений неимеет предпочтительной переменной. М-задача запишется так:

/>           (4)

/>                      (5)

/>    />,/> , />                 (6)

Задача (4)-(6) имеет предпочтительныйплан. Её начальный опорный план имеет вид

/>

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

 

Теорема. Если в оптимальном плане

/>                  (7) 

М-задачи (4)-(6) все искусственныепеременные />  />, то план /> является оптимальным планомисходной задачи (1)-(3).

Для того чтобы решить задачу сограничениями, не имеющими предпочтительного вида, вводят искусственный базис ирешают расширенную М-задачу, которая имеет начальный опорный план />

Решение исходной задачи симплекснымметодом путем введения искусственных переменных /> называетсясим­плексным методом с искусственным базисом.

Если в результате применениясимплексного метода к расширенной задаче получен оптимальный план, в кото­ромвсе искусственные переменные />, то егопервые n компоненты дают оптимальный планисходной задачи.

 

Теорема.Если в оптимальномплане М-задачи хотя бы одна из искусственных переменных отлична от нуля, тоисходная задача не имеет допустимых планов, т. е. ее условия несовместны.

3.1 Признакиоптимальности.

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

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

§4. Понятие двойственности.

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

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

                    />          (1)

                    />         (2)

                     />  />                                  (3)

Предположимдалее, что с самого начала при изучении вопроса об использовании отходовосновного производст­ва на предприятии появилась возможность реализации ихнекоторой организации. Необходимо установить прикидочные оценки (цены) на этиотходы. Обозначим их />.

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

1)   общую стоимость отходов сырьяпокупающая организация стремится мини­мизировать;

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

Эти требования форма­лизуются в видеследующей ЗЛП.

Требование 1 покупающей организации –минимизация покупки: />           (4)

Требование 2 предприятия,реализующего отходы сырья, можно сформулировать в виде системы ограничений.Предприятие откажется от выпуска каждой единицы продукции первого вида, если />, где левая часть означаетвыручку за сырьё идущее на единицу продукции первого вида; правая – её цену.

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

/>         (5)

По смыслу задачи оценки не должныбыть отрицательными:

/>                          (6)

Переменные />  /> называют двойственнымиоценками или объективно обусловленными оценками.

Задачи (1)-(3) и (4)-(6) называютпарой взаимно двойственных ЗПЛ.

Между прямой и двойственной задачамиможно установить следующую взаимосвязь:

1.    Если прямая задача на максимум, тодвойственная к ней — на минимум, и наоборот.

2.    Коэффициенты /> целевой функции прямойзадачи являются свободными членами ограничений двойственной задачи.

3.    Свободные члены /> ограничений прямой задачиявляются коэффициентами целевой функции двойст­венной.

4.    Матрицы ограничений прямой идвойственной задач являются транспонированными друг к другу.

5.    Если прямая задача на максимум, то еесистема ограничений представляется в виде неравенств типа />. Двойственная задачарешается на минимум, и ее система ограничений имеет вид неравенств типа />.

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

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

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

/>  (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 2400

/>

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

 

/> /> /> /> /> /> /> /> /> />

Решение.

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

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

/>

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

/>

/>

/>

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

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

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

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

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

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

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

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

/>

/>

/>

/>

/>

/>

/>

/>

65 70 60 120

/>

4800 4 2 2 8 1

/>

2400 2 10 6 1

/>

1500 1 2 1 1

/>

-65 -70 -60 -120 1

/>

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

/>

2400 2 6 1

/>

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

/>

72000 -5 -40 -30 15 2

/>

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

/>

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

/>

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

/>

84000 5 10 15 5

Выпишем из таблицы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< 1500. Этоозначает, что расход ресурса /> мень­шеего запаса, т. е. ресурс /> избыточный.Именно поэтому в оптималь­ном плане /> двойственнойзадачи оценка /> этого ресурсаравна нулю.

А вот оценки /> и /> ресурсов /> и /> выражаются положительнымичислами 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. Программа и расчеты.

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

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

usescrt;

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

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

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

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

label5,15,20,10;

varb,cb:array[1..m] of real;c,x,e:array[1..50] of real;a:array[1..m,1..50] ofreal;

   s0,max,mb,s1:real;i,j,k,i0,j0,m21,nm1,n1:integer; Bi:array[1..m] of integer;

begin

    clrscr;

    writeln;

    writeln (' Симплексный метод решения задачи линейного программирования:');

    writeln;

    writeln (' Проведем некоторые преобразования с данной задачей:');

    writeln;

    writeln (' Подготовьте матрицу: сначала равенства, потом неравенства вида >=и неравенства  вида <=;');

    writeln (' Целевая функция должна быть на минимум (привести ее к такому виду);');

    writeln (' Вектор b должен состоять только из положительных элементов (привестиего к та-  кому виду);');

    writeln(' Введите матрицу А ',m,'*',n,' построчно:');

    for i:=1 to m

        do begin for j:=1 to n

                     do read (a[i,j]);

                     readln

                 end;

    writeln (' Введите в виде строки вектор b, состоящий из ',m,' компонент:');

    for i:=1 to m

        do read (b[i]);

    writeln(' Введите теперь вектор с, состоящий из ',n,' компонент:');

    for i:=1 to n

         do read (c[i]);

    m21:=m2-m1+n;nm1:=n+m-m1;n1:=n+m-m1+m2;

    for i:=1 to m

        do for j:=n+1 to n1

               do a[i,j]:=0;

    {переход к равенствам в неравенствах >=}

    for i:=m1+1 to m2

        do a[i,n+i-m1]:=-1;

    {переход к равенствам в неравенствах <=}

    for i:=m2+1 to m

        do a[i,m21+i-m2]:=1;

    {создание искуственного базиса}

    for i:=1 to m2

        do a[i,nm1+i]:=1;

        {ввод mb в вектор с}

    mb:=12345;

    for i:=n+1 to nm1

        do c[i]:=0;

    for i:=nm1+1 to n1

        do c[i]:=mb;

    {выписать cb}

    for i:=1 to m2

        do begin cb[i]:=mb; Bi[i]:=nm1+i end;

    for i:=m2+1 to m

        do begin Bi[i]:=m21+i-m2;

                 cb[i]:=0;

           end;

    for i:=1 to n1

        do x[i]:=0;

    writeln(' Решение задачи:');

    {применяем симплексный метод, вычисляем оценки}

    5: for j:=1 to n1

           do begin s0:=0;

                    for i:=1 to m

                        do s0:=s0+cb[i]*a[i,j];

                    e[j]:=s0-c[j]

              end;

    max:=e[1];j0:=1;

    for i:=2 to n1

        do if e[i]>max

              then begin max:=e[i];

                         j0:=i

                   end;

    {получили столбец с максимальной оценкой}

    if max<=0

       then begin for i:=1 to m

                      do x[Bi[i]]:=b[i];

                                       goto 15

            end;

    s1:=a[1,j0];

    for i:=2 to m

        do if s1<a[i,j0]

              then s1:=a[i,j0];

    if s1<=0

       then goto 10;

    s1:=mb;

    for i:=1 to m

        do if a[i,j0]>0

              then if s1>b[i]/a[i,j0]

                      then begin

                                 s1:=b[i]/a[i,j0];

                                 i0:=i

                           end;

    {главный элемент a[i0,j0]}

    s0:=a[i0,j0]; Bi[i0]:=j0;

    for j:=1 to n1

        do a[i0,j]:=a[i0,j]/s0;

    b[i0]:=b[i0]/s0;

    for i:=1 to m

        do if i<>i0

              then begin s1:=-a[i,j0];

                         b[i]:=b[i]+b[i0]*s1;

                         for j:=1 to n1

                             do a[i,j]:=a[i,j]+a[i0,j]*s1

                   end;

     cb[i0]:=c[j0];

     goto 5;

     10: writeln(' Нет оптимального плана, функция неограничена');

     goto 20;

     {просмотр иск. переменных}

     15: for i:=nm1+1 to n1

             do if x[i]>0

                   then begin writeln(' Пустое множество планов');

                              goto 20

                        end;

     for i:=1 to n

         do writeln(' x[',i,']=',x[i]:7:4);

     20:readkey

end.

Содержание

Введение………………………………………………………………………………1                                                                                                                            

§1. Задача линейного программирования и свойства еёрешений…………….…4

§2. Графический способ решения

      задачи линейного программирования……………………………………….…6

§3. Симплексный метод……………………………………………………………..8

§4. Понятие двойственности……………………………………………………….11

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

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

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

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

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