Лабораторные работы по Основам теории систем
.
Это значит, что
на производство
сплава мы не
только не тратим
средств, но и
получаем прибыль
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 у.е.
Лабораторная работа № 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, пока не будут перечеркнуты все строки или столбцы
В нашем случае это выглядит следующим образом:































