Xreferat.com » Рефераты по математике » Лабораторные работы по Основам теории систем

Лабораторные работы по Основам теории систем

по сравнению с предлагаемой ценой в 2 у.е.). Решив новую задачу без производства олова и свинца, мы безусловно выйдем за границы области устойчивости двойственных оценок. Кроме того, сменится решение: двойственная оценка цинка увеличится до 3 и новое значение целевой функции понизится до 4 у.е. Вычтем из этих затрат на производство сплава доход от получения олова и цинка: . Это значит, что на производство сплава мы не только не тратим средств, но и получаем прибыль 1,9 у.е.

С увеличением двойственной оценки цинка становится выгодно покупать его. Но мы располагаем суммой денег только 3 у.е. и можем закупить на них 1,5 тонн вместо 2 необходимых. Теперь нам нужно производить только 0,5 тонны цинка. На второй итерации мы получаем такое же решение: критерий равен 4 у.е. и двойственная оценка цинка, которого мы производим 3 тонны, равна 4.

Таким образом, мы получили оптимальное решение расходования выделенных 3 у.е.: "закупать" с доплатой 4 тонны олова и 5 тонн свинца и покупать по цене 2 у.е. 1,5 тонны цинка. При таком плане предприятие получит прибыль от производства сплава в размере 1,9 у.е.

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

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

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

а).

Тогда оптимальная симплекс-таблица будет иметь вид:


4 4,5 5,8 6 7,5 0 0 0 0 0

Св

Б.П.

X1

X2

X3

X4

X5

X6

X7

X8

X9

X10

В
4,5

X2

1,4 1 0 0 0 2 0 0 -0,2 0 0,4
0

X8

0,12 0 0 0,2 0,3 0,6 0 1 -0,46 0 0,12
5,8

X3

-0,4 0 1 1 1 -2 0 0 1,2 0 0,6
0

X7

0,12 0 0 0,2 0,3 -0,4 1 0 0,54 -1 0,32

F

0 0

0 0

0

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

=> ,

Это значит, что цена первого ресурса может меняться от нуля (бесплатный, недефицитный ресурс) до 4,514 у.е. (отрицательный коэффициент в целевой функции в данном случае не имеет экономического смысла, т.к. свидетельствует о получении ресурса с доплатой. В этом случае ресурс выступает в роли антиблага). Критерий изменится на .

б)


4 4,5 5,8 6 7,5 0 0 0 0 0

Св

Б.П.

X1

X2

X3

X4

X5

X6

X7

X8

X9

X10

В
4,5

X2

1,4 1 0 0 0 2 0 0 -0,2 0 0,4
0

X8

0,12 0 0 0,2 0,3 0,6 0 1 -0,46 0 0,12
5,8

X3

-0,4 0 1 1 1 -2 0 0 1,2 0 0,6
0

X7

0,12 0 0 0,2 0,3 -0,4 1 0 0,54 -1 0,32

F

0 0

0 0

0

=> ,

Коэффициент критерия может меняться от 5,75 у.е. за одну тонну третьего сырья до 6 у.е. При этом решение будет оставаться оптимальным, а сам критерий изменится на .

2. Рассмотрим случай со свободной переменной.

а) , тогда

Условие оптимальности оценки: => => .

В данном случае , .

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

б) Будем руководствоваться аналогичными рассуждениями при вычислении интервалов устойчивости для четвёртого и пятого ресурсов.

, или ,.

, или ,

Оптимальные решения при конкретных изменениях коэффициентов.

а)стоимость второго сырья увеличилась до 4,5 у.е

Интервал устойчивости коэффициента целевой функции . Цена 4,5 у.е. входит в этот интервал, значит оптимальное решение не изменится, а критерий станет у.е.

б) стоимость третьего сырья уменьшилась до 3 у.е

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

– при : ;

– при : ;

– при : ;

– при : ;

– при : ;

.

Скорректируем симплекс-таблицу:


4 4,5 3 6 7,5 0 0 0 0 0

Св

Б.П.

X1

X2

X3

X4

X5

X6

X7

X8

X9

X10

В
4,5

X2

1,4 1 0 0 0 2 0 0 -0,2 0 0,4
0

X8

0,12 0 0 0,2 0,3 0,6 0 1 -0,46 0 0,12
3

X3

-0,4 0 1 1 1 -2 0 0 1,2 0 0,6
0

X7

0,12 0 0 0,2 0,3 -0,4 1 0 0,54 -1 0,32

F 1,1 0 0 -3 -4,5 3 0 0 -9,42 0 3,6

Через две итерации получаем оптимальную симплекс-таблицу:


4 4,5 3 6 7,5 0 0 0 0 0

Св

Б.П.

X1

X2

X3

X4

X5

X6

X7

X8

X9

X10

В
4

X1

1 1 0 -0,666 -1 0 0 -3,33 1,333 0 0
0

X6

0 -0,2 0 0,466 0,7 1 0 2,333 -1,03 0 0,2
3

X3

0 0 1 1,666 2 0 0 3,333 -0,333 0 0,1
0

X7

0 -0,2 0 0,466 0,7 0 1 1,333 -0,033 -1 0,4

F 0 -0,5 0 -3,66 -5,5 0 0 -3,33 4,333 0 3

Получим оптимальное решение . Стоимость сплава понизилась до 3 у.е. за единицу.

в) издержки на первое сырьё возросли до 6 у.е

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

г) издержки на четвёртый ресурс упали до 4 у.е.

При падении издержек до 4 у.е. за тонну оптимальное решение должно измениться, т.к. нижняя граница интервала устойчивости – 5,8 у.е. Оценка .


4 4,5 5,8 4 7,5 0 0 0 0 0

Св

Б.П.

X1

X2

X3

X4

X5

X6

X7

X8

X9

X10

В
4,5

X2

1,4 1 0 0 0 2 0 0 -0,2 0 0,4
0

X8

0,12 0 0 0,2 0,3 0,6 0 1 -0,46 0 0,12
5,8

X3

-0,4 0 1 1 1 -2 0 0 1,2 0 0,6
0

X7

0,12 0 0 0,2 0,3 -0,4 1 0 0,54 -1 0,32

F -0,02 0 0 1,8 -1,7 -2,6 0 0 -6,06 0 5,28

Оптимальная симплекс-таблица:


4 4,5 5,8 4 7,5 0 0 0 0 0

Св

Б.П.

X1

X2

X3

X4

X5

X6

X7

X8

X9

X10

В
4,5

X2

1,4 1 0 0 0 2 0 0 -0,2 0 0,4
4

X4

0,6 0 0 1 1,5 3 0 5 -2,3 0 0,6
5,8

X3

-1 0 1 0 -0,5 -5 0 -5 3,5 0 0
0

X7

0 0 0 0 0 -1 1 -1 1 -1 0,2

F -1,1 0 0 0 -4,4 -8 0 -9 10,2 0 4,2

С помощью симплекс-метода получаем оптимальное решение и оптимальное значение критерия у.е.

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

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

Возьмем, например, как изменяющийся коэффициент . Его изменение влечёт за собой изменение оценки только свободной переменной :

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

Возьмём также для наглядности изменение ещё одного коэффициента, т.к. полученный выше результат означает, что содержание сплава (т.е всех компонентов) в первом сырье может меняться от 0% до 100% (формально от 0% до 100,3%).

, , , , т.е. содержание свинца в первом сырье варьируется в пределах от 0% до 100% ( и экономического смысла не имеют).

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

а) 100,2%

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

б) 110%

, (не входит в интервал устойчивости).

– оценка не оптимальная.

Симплекс-методом получим оптимальное решение:

, .

4. Введение новой переменной.

Предположим, что появилась возможность использовать новый вид сырья, в котором содержится 40% олова, 60% цинка и 30% свинца, и который обладает стоимостью 3,5 у.е. за единицу. Определим новый план производства.

Пусть – доля шестого (нового) сырья в сплаве. Тогда:

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

Доход на тонну нового сырья будет равен , а затраты – 3,5 у.е. (Новое ограничение в двойственной задаче ) Тонна сырья приносит больше дохода, чем издержек на 1 у.е., поэтому будем увеличивать использование этого сырья.

Запишем новую симплекс-таблицу с учётом новой переменной:


4 4,5 5,8 6 7,5 3,5 0 0 0 0 0

Св

Б.П.

X1

X2

X3

X4

X5

X6’

X6

X7

X8

X9

X10

В

4,5

X2

1,4 1 0 0 0 0,6’ 2 0 0 -0,2 0 0,4
0

X8

0,12 0 0 0,2 0,3 1 0,6 0 1 -0,46 0 0,12
5,8

X3

-0,4 0 1 1 1 -2 -2 0 0 1,2 0 0,6
0

X7

0,12 0 0 0,2 0,3 -0,1 -0,4 1 0 0,54 -1 0,32

F -0,02 0 0 -0,2 -1,7 1 -2,6 0 0 -6,06 0 5,28

Оптимальная симплекс-таблица:


4 4,5 5,8 6 7,5 3,5 0 0 0 0 0

Св

Б.П.

X1

X2

X3

X4

X5

X6’

X6

X7

X8

X9

X10

В

3,5

X6’

2,333 1,666 0 0 0 1 3,333 0 0 -0,333 0 0,666
0

X8

-0,066 -0,133 0 0,2 0,3 0 0,333 0 1 -0,433 0 0,066
5,8

X3

-1,33 -0,666 1 1 1 0 -3,33 0 0 1,333 0 0,333
0

X7

0,633 0,366 0 0,2 0,3 0 0,333 1 0 0,466 -1 0,466

F -3,56 -2,53 0 -0,2 -1,7 0 -7,66 0 0 -6,566 0 4,266

Оптимальное решение будет , . Это означает, что для производства нового сплава будет использоваться 33,3% третьего сырья и 66,6% нового шестого сырья. Минимальная стоимость сплава будет 4,266 у.е. Видим, что использование нового вида сырья действительно выгодно, т.к. издержки на производство сплава снизились с 5,28 у.е. за единицу до 4,266 у.е.

5. Введение нового ограничения

Пусть для производства сплава нужно использовать ещё один компонент – медь, содержащуюся в сырье в количествах 40%, 10%, 20%, 20% и 30% соответственно. Содержание её в новом сплаве не должно быть меньше 20%.

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

Оптимальное решение первоначальной задачи: . Проверим, удовлетворяет ли оно новому ограничению:

.

Ограничение не выполняется, поэтому для решения задачи приведём новое ограничение к канонической форме:

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

После несложных вычислений получим: .

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


4 4,5 5,8 6 7,5 0 0 0 0 0 0

Св

Б.П.

X1

X2

X3

X4

X5

X6

X7

X8

X9

X10

X11

В
4,5

X2

1,4 1 0 0 0 2 0 0 -0,2 0 0 0,4
0

X8

0,12 0 0 0,2 0,3 0,6 0 1 -0,46 0 0 0,12
5,8

X3

-0,4 0 1 1 1 -2 0 0 1,2 0 0 0,6
0

X7

0,12 0 0 0,2 0,3 -0,4 1 0 0,54 -1 0 0,32
0

X11

0,34 0 0 0 0,1 0,2 0 0 -0,22 0 1 0,04

F -0,02 0 0 -0,2 -1,7 -2,6 0 0 -6,06 0 0 5,28

Оптимальное решение получим с помощью двойственного симплекс-метода.


4 4,5 5,8 6 7,5 0 0 0 0 0 0

Св

Б.П.

X1

X2

X3

X4

X5

X6

X7

X8

X9

X10

X11

В
4,5

X2

0 1 0 0 -0,411 1,176 0 0 4,117 0,705 0 0,235
0

X8

0 0 0 0,2 0,264 0,529 0 1 0,353 -0,382 0 0,106
5,8

X3

0 0 1 1 1,117 -1,76 0 0 -1,17 0,941 0 0,647
0

X7

0 0 0 0,2 0,264 -0,47 1 0 0,353 0,617 -1 0,305
4

X1

1 0 0 0 0,294 0,588 0 0 -2,94 -0,647 0 0,117

F 0 0 0 -0,2 -1,69 -2,58 0 0 -0,058 -6,047 0 5,282

Оптимальное решение: . Это значит, что для производства сплава с учётом примеси меди необходимо взять 11,7% первого сырья, 23,5% второго сырья и 64,7% третьего сырья. Минимальная стоимость единицы такого сплава будет 5,282 у.е.


13



Лабораторная работа № 5

Телешовой Елизаветы, гр. 726,

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

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

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

В амбаре было 4 мышиных норы: в первой проживало 15 мышей, во второй – 20, в третьей – 10 мышей, а в четвертой – 25 мышей, а также 5 источников пищи, от которых и кормилась вся эта орава мышей: у окорока – 5 мышей, у мешка крупы – 18 мышей, у мешка муки – 17 мышей, у мешка картошки – 22 мыши и у стопки старых газет и журналов эротического содержания – 8 мышей.

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

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

1);

2);

ну и конечно

Исходя из этих условий они составили математическую модель процесса своего питания:

; ;

Ну, и для наглядности нарисовали ее в виде таблицы:

Пища

Норы

окорок мешок крупы мешок муки мешок картошки журналы
5 18 17 22 8
нора 1 15

нора 2 20

нора 3 10

нора 4 25

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

.

Безусловно, цель мышей – добраться до еды с минимальными потерями по дороге, то есть:

.

Таким образом:

2. Двойственая задача.

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

(1).

Система (1) и будет служить в дальнейшем критерием оптимальности плана.

Запишем подробно двойственную задачу на основе этого ограничения:

; ; ; ;

Критерием двойственной задачи будет максимизация выгодности:

3. Метод последовательной максимальной загрузки выбранных коммуникаций.

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

(2).

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

Поскольку хотят есть все мыши во всех норах, то модель закрытая, т.е.

.

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

1) Выбираем коммуникацию, которую можно больше всего загрузить.

2) Максимально ее загружаем в соответствии с (2).

3) Корректируем объемы производства и потребления на величину выбранной перевозки, вычисляя остатки производства и потребления:

; ;

4) Вычеркиваем в транспортной таблице строку или столбец с нулевым объемом производства или потребления:

если – вычеркиваем -тую строку;

если – вычеркиваем -тый столбец;

5) Повторяем этот процесс с пункта 1 по 4, пока не будут перечеркнуты все строки или столбцы

В нашем случае это выглядит следующим образом:

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

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

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

Похожие рефераты: