Logo GenDocs.ru

Поиск по сайту:  

Загрузка...

Лекции по теории принятия решений (ТПР) - файл 1.doc


Лекции по теории принятия решений (ТПР)
скачать (728 kb.)

Доступные файлы (1):

1.doc728kb.17.11.2011 04:18скачать

содержание
Загрузка...

1.doc

  1   2   3
Реклама MarketGid:
Загрузка...
Общая постановка задачи о принятии решения


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

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

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

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

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

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

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

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

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

3-й этап. Исследование влияния переменных на значение целевой функции. Этот этап предусматривает владение математическим аппаратом для решения математических, задач, возникающих на втором этапе процесса принятия, решения.

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

4-й этап. Сопоставление результатов вычислений, полученных на 3-м этапе, с моделируемым объектом, т. е. экспертная проверка результатов (критерий практики). Таким образом, на этом этапе устанавливается степень адекватности модели и моделируемого объекта в пределах точности исходной информации. Здесь возможны два случая:

  • ^ 1-й случай. Если результаты сопоставления неудовлетворительны (обычная ситуация на начальной стадии процесса моделирования), то переходят ко второму циклу процесса. При этом уточняется входная информация о моделируемом объекте и в случае необходимости уточняется постановка задачи (1-й этап), уточняется или строится заново математическая модель (2-й этап), решается соответствующая математическая задача (3-й этап) и, наконец, снова проводится сопоставление (4-й этап).

  • ^ 2-й случай. Если результаты сопоставления удовлетворительны, то модель принимается. Когда речь идет о неоднократном использовании на практике результатов вычислений, возникает задача подготовки модели к эксплуатации. Предположим, например, что целью моделирования является создание календарных планов производственной деятельности предприятия. Тогда эксплуатация модели включает в себя сбор и обработку информации, ввод обработанной информации в ЭВМ, расчеты на основе разработанных программ календарных планов и, наконец, выдачу результатов вычислений (в удобном для пользователей виде) для их использования в сфере производственной деятельности.

В математическом программировании можно выделить два направления.

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

Ко второму направлению – так называемому стохастическому программированию – относятся задачи, в которых исходная информация содержит элементы неопределенности, либо когда некоторые параметры задачи носят случайный характер с известными вероятностными характеристиками. Так, планирование производственной деятельности зачастую производится в условиях неполной информации о реальной ситуации, в которой будет выполняться план. Или, скажем, когда экстремальная задача моделирует работу автоматических устройств, которая сопровождается случайными помехами. Заметим, что одна из главных трудностей стохастического программирования состоит в самой постановке задач, главным образом из-за сложности анализа исходной информации.

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

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

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

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

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

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

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

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

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

^ Симплекс метод

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

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

Пусть требуется найти максимальное значение функции



при условиях



Здесь и – заданные постоянные числа

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

(22)

при условиях

(23)

(24)

где



Так как



то по определению опорного плана является опорным планом данной задачи (последние компонент вектора Х равны нулю). Этот план определяется системой единичных векторов которые образуют базис m-мерного пространства. Поэтому каждый из векторов а также вектор могут быть представлены в виде линейной комбинации векторов данного базиса. Пусть



Положим Так как векторы единичные, то и а



Теорема 5

(признак оптимальности опорного плана). Опорный план задачи (22) – (24) является оптимальным, если для любого j

Теорема 6.

Если для некоторого j=k и среди чисел нет положительных , то целевая функция (22) задачи (22) – (24) не ограничена на множестве ее планов.

Теорема 7.

Если опорный план Х задачи (22) – (24) невырожден и , но среди чисел есть положительные (не все ), то существует опорный план X' такой, что

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

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

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

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

В табл. 3 первые m строк определяются исходными данными задачи, а показатели (m+1)-й строки вычисляют. В этой строке в столбце вектора записывают значение целевой функции, которое она принимает при данном опорном плане, а в столбце вектора значение

Значение Zj находится как скалярное произведение вектора на вектор



Значение равно скалярному произведению вектора P0 на вектор :



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

1) для j=m+1, (при ). Поэтому в данном случае числа для всех j от 1 до n;

2) для некоторого j, и все соответствующие этому индексу величины

3) для некоторых индексов j, и для каждого такого j , по крайней мере, одно из чисел положительно.

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

Для определения вектора, подлежащего исключению из базиса, находят для всех Пусть этот минимум достигается при i=r. Тогда из базиса исключают вектор , а число называют разрешающим элементом.

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

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

(25)

а коэффициенты разложения векторов через векторы нового базиса, соответствующего новому опорному плану, – по формулам

(26)

После вычисления и согласно формулам (25) и (26) их значения заносят в табл. 4. Элементы -й строки этой таблицы могут быть вычислены либо по формулам

(27)

(28)

либо на основании их определения.

Таблица 3



Таблица 4



Наличие двух способов нахождения элементов -й строки позволяет осуществлять контроль правильности проводимых вычислений.

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

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

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

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

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

1) число, стоящее в исходной симплекс-таблице на месте искомого элемента новой симплекс-таблицы;

2) число, стоящее в исходной симплекс-таблице на пересечении строки, в которой находится искомый элемент новой симплекс-таблицы, и столбца, соответствующего вектору, вводимому в базис;

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

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

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

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

Итак, нахождение оптимального плана симплексным методом включает следующие этапы:

1. Находят опорный план.

2. Составляют симплекс-таблицу.

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

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

5. По формулам (25) – (28) определяют положительные компоненты нового опорного плана, коэффициенты разложения векторов Pj по векторам нового базиса и числа , . Все эти числа записываются в новой симплекс-таблице.

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

Пример 9.

Для изготовления различных изделий А, В и С предприятие использует три различных вида сырья. Нормы расхода сырья на производство одного изделия каждого вида, цена одного изделия А, В и С, а также общее количество сырья каждого вида, которое может быть использовано предприятием, приведены в табл. 5.

Таблица 5

Вид сырья

Нормы затрат сырья (кг) на одно изделие

Общее количество сырья (кг)

А

В

С

I

II

III

18

6

5

15

4

3

12

8

3

360

192

180

Цена одного изделия (руб.)

9

10

16




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

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

Решение. Составим математическую модель задачи. Искомый выпуск изделий ^ А обозначим через x1, изделий В – через , изделий С – через . Поскольку имеются ограничения на выделенный предприятию фонд сырья каждого вида, переменные должны удовлетворять следующей системе неравенств:

(29)

Общая стоимость произведенной предприятием продукции при условии выпуска x1 изделий А, изделий В и изделий С составляет

(30)

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

(31)

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

Запишем эту задачу в форме основной задачи линейного программирования. Для этого перейдем от ограничений-неравенств к ограничениям-равенствам. Введем три дополнительные переменные, в результате чего ограничения запишутся в виде системы уравнений



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

Преобразованную систему уравнений запишем в векторной форме:



где



Поскольку среди векторов имеются три единичных вектора, для данной задачи можно непосредственно записать опорный план. Таковым является план Х=(0; 0; 0; 360; 192; 180), определяемый системой трехмерных единичных векторов которые образуют базис трехмерного векторного пространства.

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



Для векторов базиса

Таблица 6

i

Базис

Сб

P0

9

10

16

0

0

0










P1

P2

Р3

p4

Р5

P6

1

2

3

4

P4

р5

p6

0

0

0

360

192

180

0

18

6

5

-9

15

4

3

-10

12

8

3

-16

1

0

0

0

0

1

0

0

0

0

1

0

Как видно из таблицы 6, значения всех основных переменных равны нулю, а дополнительные переменные принимают свои значения в соответствии с ограничениями задачи. Эти значения переменных отвечают такому “плану”, при котором ничего не производится, сырье не используется и значение целевой функции равно нулю (т. е. стоимость произведенной продукции отсутствует). Этот план, конечно, не является оптимальным.

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

Так, число – 9 означает, что при включении в план производства одного изделия ^ А обеспечивается увеличение выпуска продукции на 9 руб. Если включить в план производства по одному изделию В и С, то общая стоимость изготовляемой продукции возрастет соответственно на 10 и 16 руб. Поэтому с экономической точки зрения наиболее целесообразным является включение в план производства изделий С. Это же необходимо сделать и на основании формального признака симплексного метода, поскольку максимальное по абсолютной величине отрицательное число стоит в 4-й строке столбца вектора ^ Р3. Следовательно, в базис введем вектор Р3. определяем вектор, подлежащий исключению из базиса. Для этого находим

Найдя число мы тем самым с экономической точки зрения определили, какое количество изделий С предприятие может изготовлять с учетом норм расхода и имеющихся объемов сырья каждого вида. Так как сырья данного вида соответственно имеется 360, 192 и 180 кг, а на одно изделие С требуется затратить сырья каждого вида соответственно 12, 8 и 3 кг, то максимальное число изделий С, которое может быть изготовлено предприятием, равно т. е. ограничивающим фактором для производства изделий ^ С является имеющийся объем сырья II вида. С учетом его наличия предприятие может изготовить 24 изделия С. При этом сырье II вида будет полностью использовано.

Следовательно, вектор ^ Р5 подлежит исключению из базиса. Столбец вектора Р3 к 2-я строка являются направляющими. Составляем таблицу для II итерации (табл. 7).

Таблица 7

i

Базис

Сб

Р0

9

10

16

0

0

0










P1

P2

P3

p4

p5

Р6

1

2

3

4

P4

p3

p6

0

16

0

72

24

108

384

9

3/4

11/4

3

9

1/2

3/2

-2

0

1

0

0

1

0

0

0

-3/2

1/8

-3/8

2

0

0

1

0

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

Для определения остальных элементов табл. 7 применяем правило треугольника. Эти элементы могут быть вычислены и непосредственно по рекуррентным формулам.

Вычислим элементы табл. 7, стоящие в столбце вектора Р0. Первый из них находится в 1-й строке этого столбца. Для его вычисления находим три числа:

1) число, стоящее в табл. 6 на пересечении столбца вектора ^ Р0 и 1-й строки (360);

2) число, стоящее в табл. 6 на пересечении столбца вектора P3 и 1-й строки (12);

3) число, стоящее в табл. 7 на пересечении столбца вектора Р0 и 2-й строки (24).

Вычитая из первого числа произведение двух других, находим искомый элемент: 360 – 12 х 24=72; записываем его в 1-й строке столбца вектора Р0 табл. 7.

Второй элемент столбца вектора Р0 табл. 7 был уже вычислен ранее. Для вычисления третьего элемента столбца вектора ^ Р0 также находим три числа. Первое из них (180) находится на пересечении 3-й строки и столбца вектора Р0 табл. 6, второе (3) – на пересечении 3-й строки и столбца вектора P3 табл. 6, третье (24) – на пересечении 2-й строки и столбца вектора Р0 табл. 8. Итак, указанный элемент есть 180 – 24 х 3=108. Число 108 записываем в 3-й строке столбца вектора Р0 табл. 7.

Значение F0 в 4-й строке столбца этого же вектора можно найти двумя способами:

1) по формуле , т.е.

2) по правилу треугольника; в данном случае треугольник образован числами 0, -16, 24. Этот способ приводит к тому же результату: 0 - (-16) х 24=384.

При определении по правилу треугольника элементов столбца вектора Р0 третье число, стоящее в нижней вершине треугольника, все время оставалось неизменным и менялись лишь первые два числа. Учтем это при нахождении элементов столбца вектора P1 табл. 7. Для вычисления указанных элементов первые два числа берем из столбцов векторов P1 и Р3 табл. 6, а третье число – из табл. 7. Это число стоит на пересечении 2-й строки и столбца вектора P1 последней таблицы. В результате получаем значения искомых элементов: 18 – 12 х (3/4) =9; 5 – 3 х (3/4) = 11/4.

Число в 4-й строке столбца вектора P1 табл. 7 можно найти двумя способами:

1) по формуле Z11=(C,P1)-C1 имеем

2) по правилу треугольника получим

Аналогично находим элементы столбца вектора P2.

Элементы столбца вектора Р5 вычисляем по правилу треугольника. Однако построенные для определения этих элементов треугольники выглядят иначе.

При вычислении элемента 1-й строки указанного столбца получается треугольник, образованный числами 0,12 и 1/8. Следовательно, искомый элемент равен 0 – 12 х (1/8) = -3/2. Элемент, стоящий в 3-й строке данного столбца, равен 0 - 3 х (1 /8) = -3/8.

По окончании расчета всех элементов табл. 7 в ней получены новый опорный план и коэффициенты разложения векторов через базисные векторы P4, P3, P6 и значения и . Как видно из этой таблицы, новым опорным планом задачи является план X=(0; 0; 24; 72; 0; 108). При данном плане производства изготовляется 24 изделия С и остается неиспользованным 72 кг сырья 1 вида и 108 кг сырья III вида. Стоимость всей производимой при этом плане продукции равна 384 руб. Указанные числа записаны в столбце вектора Р0 табл. 7. Как видно, данные этого столбца по-прежнему представляют собой параметры рассматриваемой задачи, хотя они претерпели значительные изменения. Изменились данные и других столбцов, а их экономическое содержание стало более сложным. Так, например, возьмем данные столбца вектора Р2. Число 1/2 во 2-й строке этого столбца показывает, на сколько следует уменьшить изготовление изделий С, если запланировать выпуск одного изделия В. Числа 9 и 3/2 в 1-й и 3-й строках вектора P2 показывают соответственно, сколько потребуется сырья I и II вида при включении в план производства одного изделия В, а число – 2 в 4-й строке показывает, что если будет запланирован выпуск одного изделия В, то это обеспечит увеличение выпуска продукции в стоимостном выражении на 2 руб. Иными словами, если включить в план производства продукции одно изделие В, то это потребует уменьшения выпуска изделия С на 1/2 ед. и потребует дополнительных затрат 9 кг сырья I вида и 3/2 кг сырья III вида, а общая стоимость изготовляемой продукции в соответствии с новым оптимальным планом возрастет на 2 руб. Таким образом, числа 9 и 3/2 выступают как бы новыми “нормами” затрат сырья I и III вида на изготовление одного изделия В (как видно из табл. 6, ранее они были равны 15 и 3), что объясняется уменьшением выпуска изделий С.

Такой же экономический смысл имеют и данные столбца вектора ^ Р1 табл. 7. Несколько иное экономическое содержание имеют числа, записанные в столбце вектора Р5. Число 1/8 во 2-й строке этого столбца, показывает, что увеличение объемов сырья II вида на 1 кг позволило бы увеличить выпуск изделий С на 1/8 ед. Одновременно потребовалось бы дополнительно 3/2 кг сырья I вида и 3/8 кг сырья III вида. Увеличение выпуска изделий С на 1/8 ед. приведет к росту выпуска продукции на 2 руб.

Из изложенного выше экономического содержания данных табл. 7 следует, что найденный на II итерации план задачи не является оптимальным. Это видно и из 4-й строки табл. 7, поскольку в столбце вектора P2 этой строки стоит отрицательное число – 2. Значит, в базис следует ввести вектор P2, т. е. в новом плане следует предусмотреть выпуск изделий В. При определении возможного числа изготовления изделий В следует учитывать имеющееся количество сырья каждого вида, а именно: возможный выпуск изделий В определяется для , т. е. находим



Следовательно, исключению из базиса подлежит вектор Р4 иными словами, выпуск изделий В ограничен имеющимся в распоряжении предприятия сырьем I вида. С учетом имеющихся объемов этого сырья предприятию следует изготовить 8 изделий В. Число 9 является разрешающим элементом, а столбец вектора P2 и 1-я строка табл. 7 являются направляющими. Составляем таблицу для III итерации (табл. 8).

Таблица 8

i

Базис

Сб

P0

9

10

16

0

0

0










P1

P2

P3

p4

p5

Р6

1

2

3

4

P2

P3

Р6

10

16

0

8

20

96

400

1

1/4

5/4

5

1

0

0

0

0

1

0

0

1/9

-1/18

-1/6

2/9

-1/6

5/24

-1/8

5/3

0

0

1

0

В табл. 8 сначала заполняем элементы 1-й строки, которая представляет собой строку вновь вводимого в базис вектора Р2. Элементы этой строки получаем из элементов 1-й строки табл. 7 делением последних на разрешающий элемент (т.е. на 9). При этом в столбце Сб данной строки записываем .

Затем заполняем элементы столбцов векторов базиса и по правилу треугольника вычисляем элементы остальных столбцов. В результате в табл. 8 получаем новый опорный план X=(0; 8; 20; 0; 0; 96) и коэффициенты разложения векторов через базисные векторы и соответствующие значения и

Проверяем, является ли данный опорный план оптимальным или нет. Для этого рассмотрим 4-ю строку, табл. 8. В этой строке среди чисел нет отрицательных. Это означает, что найденный опорный план является оптимальным и

Следовательно, план выпуска продукции, включающий изготовление 8 изделий В и 20 изделий С, является оптимальным. При данном плане выпуска изделий полностью используется сырье I и II видов и остается неиспользованным 96 кг сырья III вида, а стоимость производимой продукции равна 400 руб.

Оптимальным планом производства продукции не предусматривается изготовление изделий ^ А. Введение в план выпуска продукции изделий вида А привело бы к уменьшению указанной общей стоимости. Это видно из 4-й строки столбца вектора P1, где число 5 показывает, что при данном плане включение в него выпуска единицы изделия А приводит лишь к уменьшению общей величины стоимости на 5 руб.

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

Таблица 9

i

Базис

Сб

Р0

9

10

16

0

0

0













P1

P2

P3

p4

p5

Р6

1

2

3

4

1

2

3

4

1

2

3

4

P4

р5

p6

P4

p3

p6

P2

p3

p6

0

0

0

0

16

0

0

16

0

360

192

180

0

72

24

108

384

8

20

96

400

18

6

5

-9

9

3/4

11/4

3

1

1/4

5/4

5

15

4

3

-10

9

1/2

3/2

-2

1

0

0

0

12

8

3

-16

0

1

0

0

0

1

0

0

1

0

0

0

1

0

0

0

1/9

-1/18

-1/6

2/9

0

1

0

0

-3/2

1/8

-3/8

2

-1/6

5/24

-1/8

5/3

0

0

1

0

0

0

1

0

0

0

1

0

Пример 10.

Найти максимум функции при условиях



Решение. Систему уравнений задачи запишем в векторной форме:



где



Так как среди векторов имеется три единичных вектора, то для данной задачи можно непосредственно найти опорный план. Таковым является план Х=(0, 0, 20, 24; 0; 18). Составляем симплексную таблицу (табл. 10) и проверяем, является ли данный опорный план оптимальным.

Таблица 10

i

Базис

Сб

Р0

2

-6

0

0

5

0













P1

P2

P3

p4

p5

Р6

1

2

3

4

p3

P4

p6

0

0

0

20 24 18

0

-2

-1

3

-2

1

-2

-1

6

1

0

0

0

0

1

0

0

1

3

-12

-5

0

0

1

0

Как видно из табл. 10, исходный опорный план не является оптимальным. Поэтому переходим к новому опорному плану. Это можно сделать, так как в столбцах векторов P1 и p5, 4-я строка которых содержит отрицательные числа, имеются положительные элементы. Для перехода к новому опорному плану введем в базис вектор p5 и исключим из базиса вектор p4. Составляем таблицу II итерации.

Таблица 11

i

Базис

Сб

Р0

2

-6

0

0

5

0













P1

P2

P3

p4

p5

Р6

1

2

3

p3

P5

p6

0

5

0

12

8

114

40

-5/3

-1/3

-1

-11/3

5/3

-2/3

-9

8/3

1

0

0

0

-1/3

1/3

4

5/3

0

1

0

0

0

0

1

0

Как видно из табл. 11, новый опорный план задачи не является оптимальным, так как в 4-й строке столбца вектора P1 стоит отрицательное число -11/3. Поскольку в столбце этого вектора нет положительных элементов, данная задача не имеет оптимального плана.


Пример 1

Предприятие изготавливает и продает краску двух видов: для внутренних и внешних работ. Для производства краски используется два исходных продукта A и B. Расходы продуктов A и B на 1 т. соответствующих красок и запасы этих продуктов на складе приведены в таблице:



Исходный

Расход продуктов (в тоннах на 1 т. краски)

Запас продукта на

продукт

краска для внутренних работ

краска для внешних работ

складе

( тонн )

A

1

2

3

B

3

1

3


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

Рассмотрим поэтапное решение этой задачи симплекс- методом, который состоит из этапов: 1. Составление математической модели задачи.2. Приведение задачи к стандартному виду, т. е. выражение целевой функции и базисных переменных через свободные переменные. 3.Составление первой симплекс-таблицы. 4. Максимальное увеличение свободных переменных, входящих в целевую функцию со знаком «+» ,не выходя за пределы ОДР.


^ I. Составление математической модели задачи.

1) Переменные задачи.

Обозначим: x1 - количество производимой краски для

внутренних работ;

x2 - соответствующее количество краски

для наружных работ.

2) Ограничения, которым должны удовлетворять переменные задачи:

x1 , x2 0;

по расходу продукта A: x1 + 2x2 3;

по расходу продукта B: 3x1 + x2 3;

В левых частях последних двух неравенств определены расходы продуктов A и B, а в правых частях неравенств записаны запасы этих продуктов.

^ 3) Целевая функция задачи.

Обозначим Z доход от продажи краски (в тысячах рублей), тогда целевая функция задачи записывается так:

Z = 2x1 + x2 ,

таким образом, задача состоит в том, чтобы найти max Z=2x1+x2 , при ограничениях:

x1 + 2x2 3 (A)

3x1 + x2 3 (B)

x1 , x2 0 .

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


^ 2 Приведение задачи к стандартному виду.

Вводя вспомогательные (балансовые) переменные x3 и x4 в левые части неравенств (А) и (В), запишем ограничения в виде уравнений:

x1 + 2x2 + x3 = 3 (A)

3x1 + x2 + x4 = 3 (B)

Целевая функция Z = 2x1 + x2 при приведении задачи к стандартному виду записывается так:

Z - 2x1 - x2 = 0 (С)

2) Составление первой симплекс-таблицы.

Симплекс-таблица составляется из коэффициентов при x1, x2, x3, x4 и чисел, стоящих в правых частях уравнений-ограничений задачи: в первой строке записываются элементы уравнения (А), во второй - (В). В последней строке симплекс-таблицы записываются коэффициенты и правая часть целевой функции (С). Таким образом, симплекс-таблица содержит две строки коэффициентов (по числу ограничений задачи) и строку коэффициентов целевой функции. Число столбцов в симплекс-таблице равно числу переменных задачи плюс один столбец правых частей (b):


X1

X2

X3

X4

b

1

2

1

0

3

3

1

0

1

3

-2

-1

0

0

0


Переменные, для которых столбцы коэффициентов состоят из одной единицы и нулей, называются базисными (В приведенном примере x3 и x4 - базисные переменные). Число базисных переменных равно числу ограничений задачи и не меняется при симплекс-преобразовании. Остальные переменные называются свободными (x1 и x2).

Симплекс-таблица определяет частное решение системы уравнений-ограничений :

x1 +2x2 + x3 = 3 (A)

3x1 +x2 + x4 = 3 (A)


при котором свободные переменные равны нулю (x1=0, x2=0), а базисные переменные равны правым частям соответствующих строк (x3=3, x4=3).

Значение целевой функции Z всегда равно числу, стоящему в правом нижнем углу таблицы (Z=2*0+1*0=0). Первая симплекс-таблица соответствует начальному решению задачи ЛП (х1=0, х2=0, x3=3, x4=3, Z=0). Это решение соответствует вершине А многоугольника допустимых решений ABCD на рис.3.

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

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

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

Для первой симплекс-таблицы разрешающим столбцом является первый столбец (свободная переменная x1 будет преобразована в базисную). Среди отношений коэффициентов столбца b к коэффициентам разрешающего столбца: 3/1 и 3/3 минимальным будет отношение 3/3: разрешающей строкой будет вторая строка (базисная переменная x4 будет преобразована в свободную).


X1

X2

X3

X4

b

1

3

2

1

1

0

0

1

3

3

-2

-1

0

0

0




На пересечении разрешающего столбца и разрешающей строки находится разрешающий элемент.

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

При этом допускается выполнение только двух операций со строками симплекс таблицы:

а) разрешающую строку можно делить (умножать) на любое число;

б) из любой строки можно вычитать элементы разрешающей строки или к любой строке можно прибавлять элементы разрешающей строки.

Выполним преобразование первой симплекс-таблицы.

1) Делим элементы разрешающей строки на 3:


X1

X2

X3

X4

b

1

1

2

1/3

1

0

0

1/3

3

1

-2

-1

0

0

0


2) Из элементов первый строки вычитаем элементы второй (разрешающей) строки:



X1

X2

X3

X4

b

0

1

5/3

1/3

1

0

-1/3

1/3

2

1

-2

-1

0

0

0


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


X1

X2

X3

X4

b

0

1

5/3

1/3

1

0

-1/3

1/3

2

1

0

-1/3

0

2/3

2


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

базисные переменные: x1=1, x3=2

свободные переменные: x2=0, x4=0.

Точка с координатами x1=1, x2=0 – это вершина D (см. рис.3). Значение целевой функции Z(D)=2.

Так как в строке коэффициентов целевой функции есть отрицательный коэффициент (-1/3 во втором столбце), то преобразование продолжается. Второй столбец является разрешающим (свободная переменная x2 переводится в базисную), минимальным среди отношений: и является первое число, следовательно разрешающей строкой является первая строка (базисная переменная x3 переводится в свободную).


X1

X2

X3

X4

b

0

1

5/3

1/3

1

0

-1/3

1/3

2

1

0

-1/3

0

2/3

2




Выполнив симплекс-преобразование, получим:



X1

X2

X3

X4

b

0

1

1

0

3/5

0

-1/5

1/3

6/5

3/5

0

0

1/5

3/5

12/5


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

Оптимальное решение таково:

базисные переменные: x1*=3/5=0.6; x2*=6/5=1.2;

свободные переменные: x3*=0; x4*=0.

Точка с координатами x1*=0.6 и x2*=1.2 это вершина С (см. рис.3)

Максимальное значение дохода (целевой функции):

Z*(С) = 12/5 = 2.4


^ ТРАНСПОРТНАЯ ЗАДАЧА

Теоретическое введение

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

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

^ Исходные параметры модели ТЗ

1)     n – количество пунктов отправления, m – количество пунктов назначения.

2)      – запас продукции в пункте отправления () [ед. прод.].

3)      – спрос на продукцию в пункте назначения () [ед. прод.].

4)      – тариф (стоимость) перевозки единицы продукции из пункта отправления в пункт назначения [руб./ед. прод.].

^ Искомые параметры модели ТЗ

1)      – количество продукции, перевозимой из пункта отправления в пункт назначения [ед. прод.].

2)      – транспортные расходы на перевозку всей продукции [руб.].

^ Этапы построения модели

I.             Определение переменных.

II.          Проверка сбалансированности задачи.

III.       Построение сбалансированной транспортной матрицы.

IV.      Задание ЦФ.

V.         Задание ограничений.

^ Транспортная модель

;



(1)

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

^ Таблица 1

Общий вид транспортной матрицы


Пункты

отправления,

Пункты потребления,

Запасы,

ед. прод.











, [руб./ед. прод.]













































Потребность

ед. прод.











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

.

(2)

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

.

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

.

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

^ Задача о назначениях – частный случай ТЗ. В задаче о назначениях количество пунктов отправления равно количеству пунктов назначения. Объемы потребности и предложения в каждом из пунктов назначения и отправления равны 1. Примером типичной задачи о назначениях является распределение работников по различным видам работ, минимизирующее суммарное время выполнения работ.

Переменные задачи о назначениях определяются следующим образом


  1   2   3



Скачать файл (728 kb.)

Поиск по сайту:  

© gendocs.ru
При копировании укажите ссылку.
обратиться к администрации