Допустимое и оптимальное решения. Не единственность оптимального решения Основы симплекс-метода линейного программирования

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.

Размещено на http://www.allbest.ru/

1. В решении каких производственно-экономических проблем используются методы линейного программирования

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

2. Графический метод основан на геометрической интерпретации за дачи линейного программирования

1. Графически могут решаться:

Задачи, заданные в стандартной форме, содержащие не более двух переменных;

Задачи, заданные в канонической форме с числом свободных переменных (r - ранг матрицы системы ограничений);

Задачи общего вида, которые после приведения к канонической форме будут содержать не более двух свободных переменных.

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

3. Методика решения задач ЛП графическим методом

I.В ограничениях задачи заменить знаки неравенств знаками точных равенств и построить соответствующие прямые.

II. Найти и заштриховать полуплоскости, разрешенные каждым из ограничений-неравенств задачи. Для этого нужно подставить в конкретное неравенство координаты какой-либо точки [например, (0;0)], и проверить истинность полученного неравенства. Если неравенство истинное, то надо заштриховать полуплоскость, содержащую данную точку; иначе (неравенство ложное) надо заштриховать полуплоскость, не содержащую данную точку.

Поскольку и должны быть неотрицательными, то их допустимые значения всегда будут находиться выше оси и правее оси, т.е. в I-м квадранте.

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

III. Определить ОДР как часть плоскости, принадлежащую одновременно всем разрешенным областям, и выделить ее. При отсутствии ОДР задача не имеет решений.

IV. Если ОДР - не пустое множество, то нужно построить целевую прямую, т.е. любую из линий уровня (где L - произвольное число, например, кратное и, т.е. удобное для проведения расчетов). Способ построения аналогичен построению прямых ограничений.

V. Построить вектор, который начинается в точке (0;0) и заканчивается в точке. Если целевая прямая и вектор построены верно, то они будут перпендикулярны.

VI.При поиске максимума ЦФ необходимо передвигать целевую прямую в направлении вектора, при поиске минимума ЦФ - против направления вектора. Последняя по ходу движения вершина ОДР будет точкой максимума или минимума ЦФ. Если такой точки (точек) не существует, то можно сделать вывод о неограниченности ЦФ на множестве планов сверху (при поиске максимума) или снизу (при поиске минимум).

VII. Определить координаты точки max (min) ЦФ и вычислить значение ЦФ. Для вычисления координат оптимальной точки необходимо решить систему уравнений прямых, на пересечении которых находится.

4 . Как построить первоначальный опорный план задачи ЛП в симплексном методе и проверить его оптимальность

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

5 . Как определить переменную (вектор) для включения в базис и переменную (вектор) подлежащую исключению из базиса

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

Симплексное отношение (Q) = Элементы столбца свободных членов

Соответствующие элементы разрешающего столбца

Значения симплексного отношения заносятся в таблицу.

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

6 . Какой метод решения систем линейных уравнений лежит в основе симплекс-метода

Нахождение начального опорного решения и переход к следующему опорному решению проводятся на основе применения метода Жордана - Гаусса для системы линейных уравнений канонической формы, в которой должна быть предварительно записана исходная ЗЛП; направление перехода от одного опорного решения к другому выбирается при этом на основе критерия оптимальности (целевой функции) исходной задачи.

7. Опишите алгоритм симплекс-метода

Схема решения задачи линейного программирования симплексным методом состоит из следующих основных этапов. 1. Математическая формализация задачи; 2. Приведение системы ограничений к каноническому виду; 3. Поиск опорного решения и нахождение базиса задачи; 4. Построение первой симплексной таблицы; 5. Проверка плана на оптимальность; 6. Последовательное улучшение плана до получения оптимального.

8. Опишите правила построения двойственной задачи ЛП

Правила построения двойственных задач:

Упорядочивается запись исходной задачи (если целевая функция максимизируется, то ограничения неравенства должны быть вида <= если минимизируется то >=), выполнение этих условий достигается умножением соответствующих ограничений на -1.Если прямая задача решается на максимум то двойственная на минимум, и на оборот. К каждому ограничению прямой задачи соответствует переменная двойственной задачи и наоборот. Матрица системы ограничений двойственной задачи получается из матрицы системы ограничений прямой задачи транспонированием.Свободные члены системы ограничений прямой задачи являются коэффициентами при соответствующих переменных целевой функции двойственной и наоборот Если на переменную прямой задачи наложено условие не отрицательности то соответствующее ограничение двойственной задачи записывается как ограничение неравенства, если же нет то как ограничение равенства. Если какое либо ограничение прямой задачи записано как равенство, то на соответствующую переменную двойственной задачи условие не отрицательности не налагается.

9 . Какова экономическая интерпретация двойственных оценок

С экономической точки зрения двойственную задачу можно интерпретировать так:

какова должна быть цена единицы каждого из ресурсов, чтобы при заданных количествах ресурсов b i и величинах стоимости единицы продукции C j минимизировать общую стоимость затрат? А исходную задачу определим следующим, образом: сколько и какой продукции x j (j =1,2,…, n) необходимо произвести, чтобы при заданных стоимостях C j (j =1,2,…, n) единицы продукции и размерах имеющихся ресурсов b i (i =1,2,…, n) максимизировать выпуск продукции в стоимостном выражении.

1 0 . Каким образом определяются двойственные оценки из последней симплексной таблицы

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

1 1 . Сформулируйте задачу оптимального планирования производства и запишите ее в виде модели ЛП

Некоторое предприятие производит n типов продукции, затрачивая при этом m типов ресурсов. Известны следующие параметры: aij - количество i-го ресурса, необходимое для производства единичного количества j-й продукции; aij0 (i=1,…,m; j=1,…,n);

bi-запас i-го ресурса на предприятии, bi>0;

cj-цена единичного количества j-й продукции, cj>0.

Предполагается, что затраты ресурсов растут прямо пропорционально объему производства. Пусть xj - планируемый объем производства j-й продукции. Тогда допустимым является только такой набор производимой продукции x=(x1,x2,…,xn), при котором суммарные затраты каждого вида i-го ресурса не превосходят его запаса:

Кроме того, имеем следующее ограничение: xj0; j=1,…,n. (2)

Стоимость набора продукции x выражается величиной: (3)

Задача планирования производства ставится следующим образом: среди всех векторов x, удовлетворяющим ограничениям (1), (2), найти такой, при котором величина (3) принимает наибольшее значение.

1 2 . Сформулируйте задачу оптимального состава смеси и запишите ее в виде модели ЛП

Пусть имеется m видов сырья, запасы которого составляют соответственно d1,…, dm. Из этого сырья необходимо составить смесь, содержащую n веществ, определяющих технические характеристики смеси. Известны величины aij (i =1,m; j =1, n) ,определяющие количество j-го вещества в единице i -го вида сырья, цена которого равна сi (i = 1,m), а также b j (j = 1,n) ?наименьшее допустимое количество j-го вещества в смеси.

Требуется получить смесь с заданными свойствами при наименьших затратах на исходные сырьевые материалы.

Цель задачи (целевая функция) - минимизировать суммарные затраты на сырье.

Найти вектор X = (x 1 , x 2, …, x n), удовлетворяющий системе ограничений:

и доставляющий целевой функции минимальное значение.

1 3 . Сформулируйте транспортную задачу ЛП и запишите ее модель

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

Исходная информация:

Mi - количество единиц груза в i-м пункте отправления (i = 1, 2, …, k);

Nj - потребность в j-м пункте назначения (j = 1, 2, …, l) (в единицах груза);

aij - стоимость перевозки единицы груза из i-гo пункта в j-й.

Обозначим через xij планируемое количество единиц груза для перевозки из i-ro пункта в j-й.

В принятых обозначениях:

Общая (суммарная) стоимость перевозок;

Количество груза, вывозимого из i-ro пункта;

Количество груза, доставляемого в j-и пункт.

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

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

при условиях:

Эта задача носит название замкнутой (закрытой, сбалансированной) транспортной модели. Заметим, что условие является естественным условием разрешимости замкнутой транспортной задачи.Более общей транспортной задачей является так называемая открытая (несбалансированная) транспортная модель:

при условиях:

1 4 . Какие модели транспортной задачи называются открытыми и как преобразовать открытую модель в закрытую?

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

Если, в модель вводится фиктивный (m+1)-й поставщик, для которого запас груза равен разности между суммарным спросом потребителей и фактическим запасом поставщиков. Все тарифы на доставку груза от фиктивного поставщика считают равным 0: . В транспортную таблицу добавляется одна строка.

В модель вводится фиктивный (n+1)-й потребитель, для которого потребность равна разности между суммарным запасом поставщиков. Все тарифы на доставку груза с фиктивными потребностями считают равными 0: . В транспортную таблицу добавляется один столбец.

15 . Метод потенциалов

Широко распространенным методом решения транспортных задач является метод потенциалов. Если допустимое решение (i=1,2,…,m; j=1,2,…n) транспортной задачи является оптимальным, то существуют потенциалы (числа) поставщиков (i=1,2,…,m)и потребителей (j=1,2,…,n). Опорное решение является оптимальным, если для всех векторов условий (клеток таблицы) оценки неположительные. Алгоритм решения транспортных задач методом потенциалов:

а) проверить выполнение необходимого и достаточного условия разрешимости задачи. Если задача имеет неправильный баланс, то вводится фиктивный поставщик или потребитель с недостающими запасами или запросами и нулевыми стоимостями перевозок. b) построить начальное опорное решение (методом минимальной стоимости или каким-либо другим методом), проверить правильность его построения по количеству занятых клеток (их должно быть m+n-1) и убедиться в линейной независимости векторов условий (используется метод вычеркивания). c) построить систему потенциалов, соответствующих опорному решению. Для этого решают систему уравнений, которая имеет бесконечное множество решений. Для нахождения частного решения системы одному из потенциалов (обычно тому, которому соответствует большее число занятых клеток) задают произвольно некоторое значение (чаще нуль). Остальные потенциалы однозначно определяются по формулам. d) проверить выполнения условия оптимальности для свободных клеток таблицы. Для этого вычисляют оценки для всех свободных клеток по формулам и те из них, которые больше нуля, записываются в левые нижние углы клеток. Если для всех свободных клеток, то вычисляют значение целевой функции и решение задачи заканчивается, так как полученное решение является оптимальным. Если же имеется хотя бы одна клетка с положительной оценкой, опорное решение не является оптимальным.

e) перейти к опорному решению, на котором значение целевой функции будет меньше. Для этого находят клетку таблицы задачи, которой соответствует наибольшая положительная оценка. Строят цикл, включающий в свой состав данную клетку и часть клеток, занятых опорным решением. В клетках цикла расставляют поочередно знаки «+» и «-», начиная с «+» в клетке с наибольшей положительной оценкой. Осуществляют сдвиг (перераспределение груза) по циклу на величину. Клетка со знаком «-», в которой достигается остается пустой. Если минимум достигается в нескольких клетках, то одна из них остается пустой, а в остальных проставляют базисные нули, чтобы число занятых клеток оставалось равным. Далее перейти к пункту 3 данного алгоритма.

МОДЕЛИ СЕТЕВОГО ПЛАНИРОВАНИЯ

1. Каковы цели применения методов СПУ? Охарактеризуйте область применения сетевых методов в с фере экономики

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

Система СПУ позволяет:

Формировать календарный план реализации некоторого комплекса работ; выявлять и мобилизовывать резервы времени, трудовые, материальные и денежные ресурсы; - осуществлять управление комплексом работ по принципу «ведущего звена» с прогнозированием и предупреждением возможных срывов в ходе работ; - повышать эффективность управления в целом при четком распределении ответственности между руководителями разных уровней и исполнителями работ; - четко отобразить объем и структуру решаемой проблемы, выявить с любой требуемой степенью детализации работы, образующие единый комплекс процесса разрешения проблемы; - - определить события, совершение которых необходимо для достижения заданных целей; - выявить и всесторонне проанализировать взаимосвязь между работами, так как в самой методике построения сетевой модели заложено точное отражение всех зависимостей, обусловленных состоянием объекта и условиями внешней и внутренней среды; - широко использовать вычислительную технику; - быстро обрабатывать большие массивы отчетных данных и обеспечивать руководство своевременной и исчерпывающей информацией о фактическом состоянии реализации программы; - - упростить и унифицировать отчетную документацию.

2. Что представляет собой сетевой график?

Сетевая модель -- это план выполнения некоторого комплекса взаимосвязанных работ, заданного в форме сети, графическое изображение которой называется сетевым графиком.

3. Что понимается под терминами работа и события, каки е разновидности работ Вы знаете ?

Сетевые модели состоят из трех следующих элементов:

Работа (или задача) Событие (вехи) Связь (зависимость)

Работа (Activity) - это процесс, который необходимо выполнить для получения определенного (заданного) результата, как правило, позволяющего приступить к последующим действиям. Термины "задача" (Task) и "работа" могут быть идентичны, однако в некоторых случаях задачами принято называть выполнение действий, выходящих за рамки непосредственного производства, например "Экспертиза проектной документации" или "Переговоры с заказчиком". Иногда понятие "задача" используют для отображения работ самого низкого уровня иерархии. Событие (Node) - момент изменения состояния системы, в частности, момент начала или окончания любой работы по своей сути является событием, а каждая работа обязательно имеет начальное и конечное события. Работа - это действие или процесс, которые должны произойти для перехода от начального события к конечному. Некоторые события являются общими для нескольких работ, в этом случае свершение события является моментом времени, соответствующим завершению последней из работ, непосредственно предшествующих данному событию. Веха (Milestone) - разновидность события, характеризующая достижение значимых промежуточных результатов (отдельных этапов проекта). Связь (Link) - это логическая зависимость между сроками выполнения отдельных работ и наступления событий. Если для начала выполнения какой-либо работы необходимо завершение другой работы, говорят, что эти работы соединены связью (связаны). Связи по своему существу могут определяться технологией работ, либо их организацией. Соответственно различают технологические и организационные виды связей. Связи могут называться также зависимостями (Relationship), или фиктивными работами (Dummy Activity). Связям не требуются исполнители и прямые затраты времени, однако они могут характеризоваться продолжительностью растяжения (положительным, отрицательным или нулевым).

4. Опишите основные требования, которым долж ен удовлетворять сетевой график

При построении сетевого графика необходимо соблюдать ряд правил.

1. В сетевой модели не должно быть «тупиковых» событий, то есть событий, из которых не выходит ни одна работа, за исключением завершающего события. Здесь либо работа не нужна и её необходимо аннулировать, либо не замечена необходимость определённой работы, следующей за событием для свершения какого-либо последующего события. В таких случаях необходимо тщательное изучение взаимосвязей событий и работ для исправления возникшего недоразумения.

2. В сетевом графике не должно быть «хвостовых» событий (кроме исходного), которым не предшествует хотя бы одна работа. Обнаружив в сети такие события, необходимо определить исполнителей предшествующих им работ и включить эти работы в сеть.

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

4. Любые два события должны быть непосредственно связаны не более чем одной работой-стрелкой. Нарушение этого условия происходит при изображении параллельно выполняемых работ. Если эти работы так и оставить, то произойдёт путаница из-за того, что две различные работы будут иметь одно и то же обозначение. Однако содержание этих работ, состав привлекаемых исполнителей и количество затрачиваемых на работы ресурсов могут существенно отличаться.

5. Как определяются временные оценки работ и событий?

Начало и окончание любой работы описываются парой событий, которые называются начальным и конечным событиями. Поэтому для указания конкретной работы используют код работы Р i,j , состоящий из номеров начального (i-го) и конечного (j-го) событий (рис.1, а). На рис.1, б изображен пример кодирования работ и событий в принятых обозначениях: t ij - продолжительность работы Р i,j , t - ранний срок (ожидаемый момент) осуществления события, t * - поздний срок (предельный момент) осуществления события, n - номер события, n см - номер предшествующего (смежного) события.

Рис.1. Обозначение элементов сетевого графика: а - код работы; б - пример кодирования событий в принятых обозначениях; в - пример изображения события в принятых выше обозначениях.

На рис.1 в приведён пример изображения события в принятых выше обозначениях. Обозначим через множество работ, входящих в j-е событие, а через - множество работ, выходящих из i-го события. Ранний срок (ожидаемый момент) осуществления j-го события представляет собой момент времени, раньше которого событие произойти не может и рассчитывается по формуле

Поздний срок (предельный момент) осуществления i-го события показывает максимальную задержку во времени наступления данного события:

6. Раскройте содержание, метод определения и значение критического пути в моделях сетевого планирования

Критический путь - последовательность работ между начальными и конечными событиями сети, имеющих наибольшую продолжительность во времени. Минимальное время, необходимое для выполнения проекта, запланированного сетевым графиком, равно длине критического пути. Сетевой график может содержать не один, а несколько критических путей. Критическими называются также работы и события, расположенные на этом пути. Резервный интервал от t до t* для событий, лежащих на критическом пути, равен 0. Для завершающего события сетевого графика поздний срок свершения события должен равняться его раннему сроку, т. е. t п = t* п. Длина критического пути равна раннему сроку свершения завершающего события, т. е. t кр = t п = t* п.

ЗАДАЧИ ТЕОРИИ МАССОВОГО ОБСЛУЖИВАНИЯ

1. Какие системы исследуются при помощи теории массового обслуживания?

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

2. Привидите примеры систем массового обслуживан ия в экономике, на производстве

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

3. Как классифицируются системы массового обслуживания?

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

По времени пребывания требований в очереди до начала обслуживания системы делятся на три группы:

1) с неограниченным временем ожидания (с ожиданием),

2) с отказами;

3) смешанного типа.

4. Какими чертами обладает простейший поток?

Простейший поток обладает такими важными свойствами:

1) Свойством стационарности, которое выражает неизменность вероятностного режима потока по времени. Это значит, что число требований, поступающих в систему в равные промежутки времени, в среднем должно быть постоянным. Например, число вагонов, поступающих под погрузку в среднем в сутки должно быть одинаковым для различных периодов времени, к примеру, в начале и в конце декады.

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

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

При простейшем потоке требований распределение требований, поступающих в систему подчиняются закону распределения Пуассона:

вероятность того, что в обслуживающую систему за время t поступит именноk требований:

где. - среднее число требований, поступивших на обслуживание в единицу времени.

5. Какое распределение обычно имеет время обслуживания?

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

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

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

При показательном законе распределения времени обслуживания вероятность события, что время обслуживания продлиться не более чем t, равна:

гдеv - интенсивность обслуживания одного требования одним обслуживающим устройством, которая определяется из соотношения:

где- среднее время обслуживания одного требования одним обслуживающим устройством.

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

где n - количество обслуживающих устройств.

6. Какое практическое применение имеет теория массового обслуживания при анализе функционирования подразде лений производства?

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

МОДЕЛИ МЕЖОТРАСЛЕВОГО БАЛАНСА

1. Область применения межотрас левых и межпродуктовых балансов

Межотраслевой баланс (МОБ, метод «затраты-выпуск») -- экономико-математическая балансовая модель, характеризующая межотраслевые производственные взаимосвязи в экономике страны. Характеризует связи между выпуском продукции в одной отрасли и затратами, расходованием продукции всех участвующих отраслей, необходимым для обеспечения этого выпуска. Межотраслевой баланс составляется в денежной и натуральной формах.

2. Что показывает и отражают балансовые модели?

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

3. Дайте характерис тику разделов балансовой модели

В схеме МОБ по методологии СНС, как и в известной открытой статистической модели, выделяются три основные части (квадранты): внутренний (или первый) квадрант (I); боковое (или правое) крыло (II квадрант); нижнее крыло (III квадрант). IV квадрант не разрабатывается. Общая схема МОБ имеет следующий вид:

Внутренний (или первый) квадрант (I) характеризует взаимосвязи отраслей, отражает промежуточное потребление; во II квадранте приводится структура конечного использования валового внутреннего продукта (ВВП); в III квадранте показывается структура валовой добавленной стоимости по элементам. В I квадранте («шахматная таблица») по строкам и колонкам записываются отрасли экономики. В колонках I квадранта по каждой отрасли представлены затраты на производство продукции, работ, услуг (стоимость сырья, материалов, топлива, энергии, услуг), а по строкам показывается, как распределяется продукция каждой отрасли между всеми отраслями. В правой части МОБ (// квадрант) строки соответствуют отраслям-потребителям. Колонки представляют собой категории конечного использования: конечное потребление (расходы на конечное потребление домашних хозяйств, государственного управления и некоммерческих организаций, обслуживающих домашние хозяйства), валовое накопление (валовое накопление основного капитала, изменение запасов материальных оборотных средств, чистое приобретение ценностей), сальдо экспорта-импорта товаров и услуг. В III квадранте представлена стоимостная структура ВВП. Колонки III квадранта соответствуют отраслям-производителям, а строки -- основным стоимостным компонентам валовой добавленной стоимости (оплата труда наемных работников, валовая прибыль, валовой смешанный доход, налоги и субсидии, связанные с производством) и налогам и субсидиям на продукты. Таким образом, если рассматривать данные МОБ по вертикали, то по колонкам показывается стоимостная структура выпуска продукции отдельных отраслей, который состоит из промежуточного потребления (I квадрант) и валовой добавленной стоимости (III квадрант), а по горизонтали -- по строкам -- натурально-вещественный состав продукции, которая расходуется на промежуточное потребление (I квадрант) и конечное использование (II квадрант). Для каждой отрасли экономики ресурсы продуктов равны их использованию.Четвертый раздел располагается под вторым. Он характеризует перераспределительные отношения в экономике, осуществляемые через финансово-кредитную систему. В плановых расчетах четвертый раздел, как правило, не используется, и поэтому в пределах нашего курса рассматриваться не будет.

4 . Дайте характеристику методов формирования коэффициентов прямых затрат в балансовых моделях. Как вычисляются эти коэффициенты?

Логические коэффициенты, или, как их еще называют, коэффициенты прямых внутрипроизводственных затрат аij показывают, какое количество продукта i-й отрасли надо затратить на производство единицы валового продукта j-й отрасли. Коэффициенты прямых затрат считаются постоянными величинами в статических межотраслевых моделях.Каким образом можно получить значения коэффициентов аij? Есть два основных пути.

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

где Xij и Xj взяты из отчетного баланса.

2. Нормативный. Строится модель отрасли межотраслевого баланса. В этой модели отрасль рассматривается как совокупность отдельных производств, для каждого из которых уже разработаны нормативы затрат. Если заранее знать, какую продукцию будут выпускать производства отрасли, то по нормативам затрат можно рассчитать среднеотраслевые коэффициенты прямых затрат.

Определив коэффициенты аij, можно использовать систему (4) для решения сформулированных выше задач 1 - 3.

Технологические коэффициенты аij обладают следующими свойствами:

ИГРОВЫЕ МОДЕЛИ В ЭКОНОМИКЕ

1. Какие причины вызывают неопределенность результатов игры?

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

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

2. Как определить нижнюю и верхнюю цену матричной игры и какое соотношение существует между ними?

Рассмотрим игру m Ч n с матрицей и определим наилучшую среди стратегий A 1 , A 2 , …, А m . Выбирая стратегию А i игрок А должен рассчитывать, что игрок В ответит на нее той из стратегий B j , для которой выигрыш для игрока А минимален (игрок В стремится «навредить» игроку А).Обозначим через б наименьший выигрыш игрока А при выборе им стратегии А; для всех возможных стратегий игрока В (наименьшее число в i-й строке платежной матрицы).Назовем б нижней ценой игры, или максимальным выигрышем (максимином). Это гарантированный выигрыш игрока А при любой стратегии игрока В. Следовательно,

Стратегия, соответствующая максимину, называется максиминной стратегией. Игрок В заинтересован в том, чтобы уменьшить выигрыш игрока А; выбирая стратегию B j , он учитывает максимально возможный при этом выигрыш для А. Назовем В верхней ценой игры, или минимаксным выигрышем (минимаксом). Это гарантированный проигрыш игрока В. Следовательно, .

Стратегия, соответствующая минимаксу, называется минимаксной стратегией. Принцип, диктующий игрокам выбор наиболее «осторожных» минимаксной и максиминной стратегий, называется принципом минимакса. Этот принцип следует из разумного предположения, что каждый игрок стремится достичь цели, противоположной цели противника.Если верхняя и нижняя цены игры совпадают, то общее значение верхней и нижней цены игры б = в = н называется чистой ценой игры, или ценой игры.

3. Сформулируйте основн ую теорему теории матричных игр

Основная теорема теории Матричные игры (теорема Неймана о минимаксе) утверждает, что в любой Матричные игры существуют оптимальные смешанные стратегии х*, у*, на которых достигаемые «минимаксы» равны (общее их значение есть значение игры).

Или Для матричной игры с любой матрицей А величины и равны между собой, т.е.

Более того, существует хотя бы одна ситуация в смешанных стратегиях, для которой выполняется соотношение

4.Какие существуют методы упрощения игр?

Первый метод, используемый для уменьшения размерности матрицы, основан на одном из важнейших понятий в теории игр - понятии доминирования стратегий.

Если i-я строка поэлементно не меньше (?) j-й строки, то говорят, что i-я строка доминирует над j-й строкой. Поэтому игрок A не использует j-ю стратегию, так как его выигрыш при i-й стратегии не меньше, чем при j-й стратегии, вне зависимости от того, как играет игрок B. Аналогично, если i-й столбец поэлементно не меньше (?) j-го столбца, то говорят, что j-й столбец доминирует над i-м столбцом. Поэтому игрок B не использует i-ю стратегию, так как его проигрыш (равный выигрышу игрока A) при j-й стратегии не больше (?), чем при i-й стратегии, вне зависимости от того, как играет игрок A. Стратегии, над которыми доминируют другие стратегии, надо отбросить и приписать им нулевые вероятности. На цене игры это никак не скажется. Зато размер матрицы игры понизится. С этого и нужно начинать решение игры. Частный случай доминирования является дублирование стратегий . Если платёжная матрица игры содержит несколько одинаковых строк (столбцов), то из них оставляем только одну строку, а остальные строки (столбцы) отбрасываем. Отброшенным стратегиям припишем нулевые вероятности.Упрощение (уменьшение размерности) платёжных матриц за счёт исключения заведомо невыгодных чистых стратегий возможно в силу справедливости следующей Теоремы о доминирующих стратегиях :

Пусть I - игра, в матрице которой i -я стратегия первого игрока доминирует над i +1, а G - игра, матрица которой получена из матрицы I исключением i + 1 стратегии (строки). Тогда:

1. цена игры I равна цене игры G;

2. оптимальная смешенная стратегия Q * = (q 1 * ,q 2 * ,…,q n *) второго игрока в игре G является также его оптимальной смешанной стратегией в игре I;

3. если P * = (p 1 * ,p 2 * ,…,p i * , p* i+2 ,…, p m *) оптимальная смешенная стратегия первого игрока в игре G, то его смешенная стратегия P * = (p 1 * ,p 2 * ,…,p i * , p* i+2 ,…, p m *) является оптимальной в игре I.

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

5. Геометрические методы решения игр с матрицами 2_ _n и m 2 и их применение

Решение игры в смешанных стратегиях допускает наглядную геометрическую интерпретацию. Геометрический метод решения игры включает следующие этапы. 1. В декартовой системе координат по оси абсцисс откладывается отрезок А1А2, длина которого равна 1 (рис. 2.1.). Левый конец отрезка точка x = 0 соответствует стратегии A1, правый, где х = 1,0 -- стратегии А2. Все промежуточные точки этого отрезка соответствуют смешанным стратегиям S1 = (p1, p2). 2. По оси ординат от точки O откладываются выигрыши при стратегии А1. 3. На линии, параллельной оси ординат, от точки 1 откладываются выигрыши при стратегии А2 .Пусть имеется игра с платежной матрицей:

Если игрок II применяет стратегию В1, то выигрыш игрока I при использовании чистых стратегий А1 и А2 составляет соответственно a11 = 0,4 и a21 = 0,6. Соединим эти точки прямой В1В1 . Если игрок I при стратегии В1 применяет смешанную стратегию, то средний выигрыш, определяемый по формуле математического ожидания g1 = a11p1 + a21p2, изображается ординатой точки N на прямой B1B1. Прямая B1B1 называется стратегией В1. Ордината любой точки отрезка B1B1 равна величине выигрыша игрока I при применении им стратегии A1 и А2 с соответствующими вероятностями p1 и p2.Аналогично строим отрезок В2В2, соответствующий применению игроком II стратегии В2 .Ординаты точек отрезка определяют средний стратегий А1 и А2 с соответствующими вероятностями p1 и p2 и равных g2 = a12p1 + a22p2.

6. На чем основана связь матричной игры и задачи линейного программирования?

Первоначально развитие теории стратегических матричных игр осуществлялось параллельно и независимо от линейного программирования. Позже было установлено, что стратегическая матричная игра может быть сведена к паре двойственных задач линейного программирования. Решив одну из них, получаем оптимальные стратегии игрока 1; решив другую, получаем оптимальные стратегии игрока 2. Математическое соответствие между стратегическими матричными играми и линейным программированием было установлено Дж. Б. Данцигом, сформулировавшим и доказавшим в 1951 г. основную теорему теории игр.

Теорема. Каждая матричная игра с нулевой суммой всегда имеет решение в смешанных стратегиях, т.е. существуют такое число v и такие стратегии U* и W* игроков 1 и 2 соответственно, что выполняются неравенства:

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

7. В чем состоит отличие игры с природой?

Отличительная особенность игры с природой состоит в том, что в ней сознательно действует только один из участников, в большинстве случаев называемый игроком 1. Игрок 2 (природа) сознательно против игрока 1 не действует, а выступает как не имеющий конкретной цели и случайным образом выбирающий очередные «ходы» партнер по игре. Поэтому термин «природа» характеризует некую объективную действительность, которую не следует понимать буквально, хотя вполне могут встретиться ситуации, в которых «игроком» 2 действительно может быть природа (например, обстоятельства, связанные с погодными условиями или с природными стихийными силами).

8. Перечислите основные критерии решения игр с природой и каковы расчетные формулы для этих критериев.

Критерий Байеса .

По критерию Байеса за оптимальные принимается та стратегия (чистая) A i , при которой максимизируется средний выигрыш a или минимизируется средний риск r.

Считаем значения?(a ij p j)

Критерий Лапласа .

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

q 1 = q 2 = ... = q n = 1/n.

Критерий Вальда .

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

a = max(min a ij)

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

Критерий Севиджа .

a = min(max r ij)

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

Критерий Гурвица .

Критерий Гурвица является критерием пессимизма - оптимизма. За (оптимальную принимается та стратегия, для которой выполняется соотношение:

где s i = y min(a ij) + (1-y)max(a ij)

При y = 1 получим критерий Вальде, при y = 0 получим - оптимистический критерий (максимакс).

Критерий Гурвица учитывает возможность как наихудшего, так и наилучшего для человека поведения природы. Как выбирается y? Чем хуже последствия ошибочных решений, тем больше желание застраховаться от ошибок, тем y ближе к 1.

Критерий максимакса .

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

Практические задания

Задание № 1

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

Определим максимальное значение целевой функции F(X) = 2x 1 + 5x 2 + 6x 3 при следующих условиях-ограничений.

7x 1 + 8x 2 + 3x 3 ?81

4x 1 + x 2 + 6x 3 ?68

5x 1 + x 2 + 7x 3 ?54

Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме).

В 1-м неравенстве смысла (?) вводим базисную переменную x 4 . В 2-м неравенстве смысла (?) вводим базисную переменную x 5 . В 3-м неравенстве смысла (?) вводим базисную переменную x 6 .

7x 1 + 8x 2 + 3x 3 + 1x 4 + 0x 5 + 0x 6 = 81

4x 1 + 1x 2 + 6x 3 + 0x 4 + 1x 5 + 0x 6 = 68

5x 1 + 1x 2 + 7x 3 + 0x 4 + 0x 5 + 1x 6 = 54

Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:

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

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

Решим систему уравнений относительно базисных переменных: x 4 , x 5 , x 6

Полагая, что свободные переменные равны 0, получим первый опорный план:

X1 = (0,0,0,81,68,54)

Базисное решение называется допустимым, если оно неотрицательно.

Переходим к основному алгоритму симплекс-метода.

Итерация №0.

1. Проверка критерия оптимальности.

Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.

2. Определение новой базисной переменной.

В качестве ведущего выберем столбец, соответствующий переменной x 3 , так как это наибольший коэффициент по модулю.

...

Подобные документы

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

    курсовая работа , добавлен 05.10.2014

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

    контрольная работа , добавлен 09.04.2012

    Решение задачи линейного программирования графическим способом. Определение экстремальной точки. Проверка плана на оптимальность. Правило прямоугольников. Анализ и корректировка результатов решения задач линейного программирования симплексным методом.

    контрольная работа , добавлен 04.05.2014

    Симплекс-метод решения задач линейного программирования. Элементы теории игр. Системы массового обслуживания. Транспортная задача. Графоаналитический метод решения задач линейного программирования. Определение оптимальной стратегии по критерию Вальде.

    контрольная работа , добавлен 24.08.2010

    История создания средств цифровой вычислительной техники. Методы и модели линейного программирования. Экономическая постановка задачи. Выбор метода реализации задачи. Особенности выбора языка программирования. Решение задачи сетевым методом планирования.

    курсовая работа , добавлен 19.02.2015

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

    учебное пособие , добавлен 15.06.2015

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

    лекция , добавлен 15.06.2004

    Экономико-математическая модель получения максимальной прибыли, её решение графическим методом. Алгоритм решения задачи линейного программирования симплекс-методом. Составление двойственной задачи и её графическое решение. Решение платёжной матрицы.

    контрольная работа , добавлен 11.05.2014

    Графическое решение задач линейного программирования. Решение задач линейного программирования симплекс-методом. Возможности практического использования математического программирования и экономико-математических методов при решении экономических задач.

    курсовая работа , добавлен 02.10.2014

    Основные понятия моделирования. Общие понятия и определение модели. Постановка задач оптимизации. Методы линейного программирования. Общая и типовая задача в линейном программировании. Симплекс-метод решения задач линейного программирования.

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

2) Допустимое множество - выпуклый ограниченный многогранник.

    Допустимое множество - выпуклое неограниченное многогранное множество.

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

Возможные случаи оптимальных решений (планов) задачи линейного программирования.

1) Задача не имеет оптимальных решений .

Данный случай может возникнуть: либо тогда, когда допустимое множество решений пусто ("не из чего выбирать" оптимальный план),

либо когда допустимое множество представляет собой неограниченное многогранное множество, и целевая функция на нем неограниченно возрастает (если L  max) или неограниченно убывает (при L min).

2) Задача имеет единственное решение (единственный оптимальный план).

Это решение обязательно совпадает с одной из вершин допустимого множества.

3) Задача имеет бесконечное множество оптимальных решений, заданное некоторым линейным образованием - ребром, гранью, гипергранью и т.д. Среди точек этого линейного образования имеются и вершины допустимого множества.

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

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

В следующем параграфе рассмотренные общие положения будут проиллюстрированы на примере задачи линейного программирования с двумя переменными.

    1. Графоаналитический способ решения задач линейного программирования

Графоаналитический (графический) способ решения задач линейного программирования обычно используется для решения задач с двумя переменными, когда ограничения выражены неравенствами, а также задач, которые могут быть сведены к таким задачам.

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

(1.7)

где с 1 , с 2 , а i 1 , а i 2 , b i - заданные действительные числа; знаки в неравенствах произвольны; целевая функция либо максимизируется, либо минимизируется.

Каждое из неравенств (1.7) системы ограничений задачи геометрически определяет полуплоскость соответственно с граничными прямыми
;i =1,…,m . В том случае, если система неравенств (1.7) совместна, допустимая область решений задачи есть множество точек, принадлежащих всем указанным полуплоскостям. Так как множество точек пересечения данных полуплоскостей – выпуклое, то областью допустимых значений является выпуклое множество, которое называютмногоугольником решений. Стороны этого многоугольника лежат на прямых, уравнения которых получаются из исходной системы ограничений заменой знаков неравенств на знаки равенств.

Множеством допустимых решений для данной частной задачи может быть:

    пустая область;

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

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

Практическая реализация решения задачи линейного программирования (1.6) – (1.7) на основе ее геометрической интерпретации включает следующие этапы:

1. Построить прямые, уравнения которых получаются в результате замены в ограничениях (1.7) знаков неравенств на знаки равенств.

2. Найти полуплоскости, определяемые каждым из ограничений.

Соответствующая полуплоскость может быть найдена подстановкой в неравенство координат какой-нибудь «простой» точки - (0,0), (0,1) или (1,0). Главное - чтобы эта точка не принадлежала границе полуплоскости. Если после подстановки неравенство окажется справедливым, то выбирается та полуплоскость, где содержится эта точка. Если неравенство не справедлива, то выбирается альтернативная полуплоскость.

3. Определить многоугольник решений, как пересечение найденных полуплоскостей.

4. Построить градиент целевой функции, т.е. вектор
, координатами которого служат коэффициенты целевой функцииL .

Этот вектор определяет направление наискорейшего возрастания целевой функции.

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

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

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

Заканчивая рассмотрение геометрической интерпретации задачи (1.6) – (1.7), отметим, что при нахождении ее решения могут встретиться случаи, изображенные на рис. 1.1 – 1.3. Рис. 1.1 характеризует такой случай, когда целевая функция принимает оптимальное значение в единственной точке А, одной из вершин допустимого множества. На рис. 1.2 оптимальное значение целевая функция принимает в любой точке отрезка АВ. На рис. 1.3 изображен случай, когда оптимальное значение целевой функции недостижимо.

Рис. 1.1. Оптимум функции L достижим в точке А

Рис. 1.2. Оптимум функцииL достигается в любой точке отрезка АB

Рис. 1.3. Оптимум функции L недостижим

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

Постановка задачи

В публикациях рассматривались решения прямых задач оптимизации методом линейного программирования и был предложен обоснованный выбор решателя scipy. optimize.

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

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

Оптимальные значения стоимости материала и труда будут оцениваться по их вкладу в целевую функцию. В результате будут получены «объективно обусловленные оценки» сырья и рабочей силы, которые не совпадают с рыночными ценами.

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

Учитывая высокий уровень математической подготовки подавляющего большинства пользователей данного ресурса не стану приводить балансовые уравнения с верхними и нижними ограничениями и введением для перехода к равенствам дополнительных переменных. Поэтому сразу приведу обозначения используемых в решении переменных:
N – количество видов производимых изделий;
m– количество видов используемого сырья;
b_ub - вектор имеющихся ресурсов размерности m;
A_ub – матрица размерности m×N, каждый элемент которой является расходом ресурса вида i на производство единицы изделия вида j;
с - вектор прибыли от производства единицы изделия каждого вида;
x – искомые объёмы производимых изделий каждого вида (оптимальный план производства) обеспечивающие максимальную прибыль.

Функция цели
maxF(x)=c×x

Ограничения
A×x≤b

Численные значения переменных:
N=5; m=4; b_ub = ; A_ub = [, , ,]; c = .

Задачи
1.Найти x для обеспечения максимальной прибыли
2. Найти использованные ресурсы при выполнении п.1
3. Найти остатки ресурсов (если они есть) при выполнении п.1


Для определения максимума (по умолчанию определяется минимум коэффициенты целевой функции нужно записать с отрицательным знаком c = [-25, -35,-25,-40,-30] и проигнорировать знак минус перед прибылью.

Используемые при выводе результатов обозначения:
x – массив значений переменных, доставляющих минимум (максимум) целевой функции;
slack – значения дополнительных переменных. Каждая переменная соответствует ограничению-неравенству. Нулевое значение переменной означает, что соответствующее ограничение активно;
success – True, если функции удалось найти оптимальное решение;
status – статус решения:
0 – поиск оптимального решения завершился успешно;
1 – достигнут лимит на число итераций;
2 – задача не имеет решений;
3 – целевая функция не ограничена.
nit – количество произведенных итераций.

Листинг решения прямой задачи оптимизации

#!/usr/bin/python # -*- coding: utf-8 -*- import scipy from scipy.optimize import linprog # загрузка библиотеки ЛП c = [-25, -35,-25,-40,-30] # список коэффициентов функции цели b_ub = # список объёмов ресурсов A_ub = [, # матрица удельных значений ресурсов , , ] d=linprog(c, A_ub, b_ub) # поиск решения for key,val in d.items(): print(key,val) # вывод решения if key=="x": q=#использованные ресурсы print("A_ub*x",q) q1= scipy.array(b_ub)-scipy.array(q) #остатки ресурсов print("b_ub-A_ub*x", q1)


Результаты решения задачи
nit 3
status 0

success True
x [ 0. 0. 18.18181818 22.72727273 150. ]
A_ub*x
b_ub-A_ub*x [ 0. 0. 0. 90.90909091]
fun -5863.63636364
slack [ 0. 0. 0. 90.90909091]

Выводы

  1. Найден оптимальный план по видам продукции
  2. Найдено фактическое использование ресурсов
  3. Найден остаток не использованного четвёртого вида ресурса [ 0. 0 0.0 0.0 90.909]
  4. Нет необходимости в вычислениях по п.3, так как тот же результат выводить в переменной slack

Решение двойственной задачи о оптимальной производственной программе

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

Введём новое назначение искомой переменной x как некоторой «теневой» цены, определяющей ценность данного ресурса в отношении прибыли от реализации выпускаемой продукции.

C – вектор имеющихся ресурсов;
b_ub – вектор прибыли от производства единицы изделия каждого вида;
A_ub_T– транспонированная матрица A_ub.

Функция цели
minF(x)=c×x

Ограничения
A_ub_T ×x≥ b_ub

Численные значения и соотношения для переменных:
с = ; A_ub_T transpose(A_ub); b_ub = .

Задача:
Найти x показывающий ценность для производителя каждого вида ресурсов.

Особенности решения с библиотекой scipy. optimize
Для замены ограничений сверху на ограничения с низу необходимо умножить на минус единицу обе части ограничения – A_ub_T ×x≥ b_ub… Для этого исходные данные записать в виде: b_ub = [-25, -35,-25,-40,-30]; A_ub_T =- scipy.transpose(A_ub).

Листинг решения двойственной задачи оптимизации

#!/usr/bin/python # -*- coding: utf-8 -*- import scipy from scipy.optimize import linprog A_ub = [, , , ] c= b_ub = [-25, -35,-25,-40,-30] A_ub_T =-scipy.transpose(A_ub) d=linprog(c, A_ub_T, b_ub) for key,val in d.items(): print(key,val)


Результаты решения задачи
nit 7
message Optimization terminated successfully.
fun 5863.63636364
x [ 2.27272727 1.81818182 6.36363636 0. ]
slack [ 5.45454545 2.27272727 0. 0. 0. ]
status 0
success True

Выводы

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

Результаты сравнения прямой и двойственной задачи

  1. Двойственная задача расширяет возможности планирования выпуска продукции, но средствами scipy. optimize решается за вдвое большее чем прямая количество итераций.
  2. Переменная slack выводит информацию об активности ограничений в виде неравенств, что может быть использовано, например, для анализа остатков сырья.
  3. Прямая задача является задачей максимизации, а двойственная - задачей минимизации, и наоборот.
  4. Коэффициенты функции цели в прямой задаче являются ограничениями в двойственной задаче.
  5. Ограничения в прямой задаче становятся коэффициентами функции цели в двойственной.
  6. Знаки неравенств в ограничениях меняются на противоположные.
  7. Матрица системы равенств транспонируется.
Ссылки

Составляющие математической модели

Основой для решения экономических задач являются математические модели.

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

Составление математической модели включает:
  • выбор переменных задачи
  • составление системы ограничений
  • выбор целевой функции

Переменными задачи называются величины Х1, Х2, Хn, которые полностью характеризуют экономический процесс. Обычно их записывают в виде вектора: X=(X1, X2,...,Xn).

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

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

В общем случае задача линейного программирования может быть записана в таком виде:

Данная запись означает следующее: найти экстремум целевой функции (1) и соответствующие ему переменные X=(X1, X2,...,Xn) при условии, что эти переменные удовлетворяют системе ограничений (2) и условиям неотрицательности (3).

Допустимым решением (планом) задачи линейного программирования называется любой n-мерный вектор X=(X1, X2,...,Xn), удовлетворяющий системе ограничений и условиям неотрицательности.

Множество допустимых решений (планов) задачи образует область допустимых решений (ОДР).

Оптимальным решением (планом) задачи линейного программирования называется такое допустимое решение (план) задачи, при котором целевая функция достигает экстремума.

Пример составления математической моделиЗадача использования ресурсов (сырья)

Условие: Для изготовления n видов продукции используется m видов ресурсов. Составить математическую модель.

Известны:

  • bi (i = 1,2,3,...,m) - запасы каждого i-го вида ресурса;
  • aij (i = 1,2,3,...,m; j=1,2,3,...,n) - затраты каждого i-го вида ресурса на производство единицы объема j-го вида продукции;
  • cj (j = 1,2,3,...,n) - прибыль от реализации единицы объема j-го вида продукции.

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

Решение:

Введем вектор переменных X=(X1, X2,...,Xn), где xj (j = 1,2,...,n) - объем производства j-го вида продукции.

Затраты i-го вида ресурса на изготовление данного объема xj продукции равны aijxj, поэтому ограничение на использование ресурсов на производство всех видов продукции имеет вид:
Прибыль от реализации j-го вида продукции равна cjxj, поэтому целевая функция равна:

Ответ - Математическая модель имеет вид:

Каноническая форма задачи линейного программирования

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

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

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

Каноническая задача линейного программирования в координатной записи имеет вид:

Каноническая задача линейного программирования в матричной записи имеет вид:

  • А - матрица коэффициентов системы уравнений
  • Х - матрица-столбец переменных задачи
  • Ао - матрица-столбец правых частей системы ограничений

Нередко используются задачи линейного программирования, называемые симметричными, которые в матричной записи имеют вид:

Приведение общей задачи линейного программирования к канонической форме

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

Это может быть сделано следующим образом:

Возьмем линейное неравенство a1x1+a2x2+...+anxn≤b и прибавим к его левой части некоторую величину xn+1, такую, что неравенство превратилось в равенство a1x1+a2x2+...+anxn+xn+1=b. При этом данная величина xn+1 является неотрицательной.

Рассмотрим все на примере.

Пример 26.1

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

Решение:
Перейдем к задаче на отыскивание максимума целевой функции.
Для этого изменим знаки коэффициентов целевой функции.
Для превращения второго и третьего неравенств системы ограничений в уравнения введем неотрицательные дополнительные переменные x4 x5 (на математической модели эта операция отмечена буквой Д).
Переменная х4 вводится в левую часть второго неравенства со знаком "+", так как неравенство имеет вид "≤".
Переменная x5 вводится в левую часть третьего неравенства со знаком "-", так как неравенство имеет вид "≥".
В целевую функцию переменные x4 x5 вводятся с коэффициентом. равным нулю.
Записываем задачу в каноническом виде:

Рассмотрим основную задачу линейного программирования (ОЗЛП): найти неотрицательные значения переменных x1, x2, …, xn, удовлетворяющие m условиям - равенствам

и обращающие в максимум линейную функцию этих переменных

Для простоты предположим, что все условия (1) линейно независимы (r=m), и будем вести рассуждения в этом предположении.

Назовём допустимым решением ОЗЛП всякую совокупность неотрицательных значений x1, x2, …, xn, удовлетворяющую условиям (1).Оптимальным назовём то из допустимых решений, которое обращает в максимум функцию (2). Требуется найти оптимальное решение.

Всегда ли эта задача имеет решение? Нет, не всегда.

ЗЛП неразрешима (не имеет оптимального решения):

Из-за несовместности системы ограничений. Т.е. система не имеет ни одного решения, как показано на рисунке 1.

Рисунок 1 - Несовместность системы ограничений

Из-за неограниченности целевой функции на множестве решений. Другими словами при решении ЗЛП на max значение целевой функции стремится к бесконечности, а в случае ЗЛП на min - к минус бесконечности, как показано на рисунке 2.

Рисунок 2 - Неограниченность целевой функции на множестве решений

ЗЛП разрешима:

Множество решений состоит из одной точки. Она же и является оптимальной, как показано на рисунке 3.

Рисунок 3 - Множество решений состоит из одной точки

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

Рисунок 4 - Единственное оптимальное решение

Оптимальное решение ЗЛП не единственно. Вектор N перпендикулярен к одной из сторон множества решений. В этом случае оптимальной является любая точка на отрезке АВ, как показано на рисунке 5.

Рисунок 5 - Оптимальное решение не единственно

Решение задач линейного программирования симплекс-методом

Симплекс-метод - алгоритм решения задачи ЛП, реализующий перебор угловых точек области допустимых решений в направлении улучшения значения целевой функции С. Симплекс-метод является основным в линейном программировании.

Использование этого метода в дипломном проекте для решения задачи ЛП обусловлено следующими факторами:

Метод является универсальным, применимым к любой задаче линейного программирования в канонической форме;

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

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

Так как число вершин многогранника ограничено, то за конечное число шагов гарантируется нахождение оптимального значения или установление того факта, что задача неразрешима.

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

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

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

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

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

Таким образом, применение симплексного метода распадается на два этапа:

Нахождение допустимого базисного решения системы ограничений или установление факта ее несовместности;

Нахождение оптимального решения в случае совместности системы ограничений.

Алгоритм перехода к следующему допустимому решению следующий:

В строке коэффициентов целевой функции выбирается наименьшее отрицательное число при отыскании максимума. Порядковый номер коэффициента - . Если такового нет, то исходное базисное решение является оптимальным;

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

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

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

Условие оптимальности плана при решении задачи на максимум: среди коэффициентов целевой функции нет отрицательных элементов .