ТелешовойЕлизаветы, гр.726,
Цель работы:Решениезадач линейногопрограммированиясимплекс-методом.Варианты разрешимостизадач линейногопрограммирования.
1 вариант.
1. Четыре студента:Иванов, Петров,Сидоров и Васильевпошли на концертгруппы «Чайф»,захватив пиво2 сортов: «Русич»и «Премьер».Определитьплан распитиянапитков дляполучениямаксимальногосуммарногоопьянения (в
Студент | Нормавыпитого | Запасы (в литрах) | |
«Русич» | «Премьер» | ||
Иванов | 2 | 2 | 1.5 |
Петров | 3,5 | 1 | 1,5 |
Сидоров | 10 | 4 | 4,5 |
Васильев | – | 1 | 0,7 |
Крепостьнапитка | 16 % | 10 % |
2. Математическаямодель.
2.1 Управляемыепараметры
x1[л]– количествовыпитого пива«Русич».
x2[л]– количествовыпитого пива«Премьер».
2.2 Ограничения
Общее количествопива, выпитогоИвановым, непревосходитимеющихся унего запасовпива, поэтому:
Аналогичностроим другиеограничения:
3. Постановказадачи.
Найти
4. Решение.
Приведемзадачу к каноническомувиду:
Определимначальныйопорный план:
Это решениеявляется опорным,т.к. вектораусловий приположительныхкомпонентахрешения линейнонезависимы,также
Опорный планявляется оптимальным,если для задачимаксимизациивсе его оценкинеотрицательны.
Предположим,что
Запишем новыйопорный план:
При увеличении
Из ограничения(2)имеем:
Подставляяв функцию цели:
Оформим данныйэтап задачив виде симплекс-таблицы:
Начальнаясимплекс-таблица:
16 | 10 | 0 | 0 | 0 | 0 | |||
| Б.П. | X1 | X2 | X3 | X4 | X5 | X6 | в |
0 | X3 | 2 | 2 | 1 | 0 | 0 | 0 | 1,5 |
0 | X4 | 3,5 | 1 | 0 | 1 | 0 | 0 | 1,5 |
0 | X5 | 10 | 4 | 0 | 0 | 1 | 0 | 4,5 |
0 | X6 | 0 | 1 | 0 | 0 | 0 | 1 | 0,7 |
F | -16 | -10 | 0 | 0 | 0 | 0 | 0 |
Пересчитаемэлементы исходнойтаблицы поправилу четырехугольника:
16 | 10 | 0 | 0 | 0 | 0 | |||
| Б.П. | X1 | X2 | X3 | X4 | X5 | X6 | В |
0 | X3 | 0 | 1,428 | 1 | -0,572 | 0 | 0 | 0,642 |
16 | X1 | 1 | 0,286 | 0 | 0,286 | 0 | 0 | 0,428 |
0 | X5 | 0 | 1,14 | 0 | -2,86 | 1 | 0 | 0,214 |
0 | X6 | 0 | 1 | 0 | 0 | 0 | 1 | 0,7 |
F | 0 | -5,424 | 0 | 4,576 | 0 | 0 | 6,857 |
Пересчитаввсе оценки,видим, что
откуда получаем:
Все оценкиопорного планадолжны бытьнеотрицательны,а значит должнывыполнятьсяусловия:
Выведем избазиса
16 | 10 | 0 | 0 | 0 | 0 | |||
| Б.П. | X1 | X2 | X3 | X4 | X5 | X6 | В |
| X3 | 0 | 0 | 1 | 3 | -1,25 | 0 | 0,375 |
16 | X1 | 1 | 0 | 0 | 1 | -0,25 | 0 | 0,375 |
10 | X2 | 0 | 1 | 0 | -2,5 | 0,875 | 0 | 0,1875 |
0 | X6 | 0 | 0 | 0 | 2,5 | -0,875 | 1 | 0,5125 |
F | 0 | 0 | 0 | -9 | 4,75 | 0 | 7,875 |
Пересчитаввсе оценки,видим, что
откуда получаем:
Все оценкиопорного планадолжны бытьнеотрицательны,а значит должнывыполнятьсяусловия:
Выведем избазиса
16 | 10 | 0 | 0 | 0 | 0 | |||
Св | Б.П. | X1 | X2 | X3 | X4 | X5 | X6 | в |
0 | X4 | 0 | 0 | 0,333 | 1 | -0,416 | 0 | 0,125 |
16 | X1 | 1 | 0 | -0,333 | 0 | 0,166 | 0 | 0,25 |
10 | X2 | 0 | 1 | 1,833 | 0 | -0,166 | 0 | 0,5 |
0 | X6 | 0 | 0 | -0,833 | 0 | 0,166 | 1 | 0,2 |
F | 0 | 0 | 3 | 0 | 1 | 0 | 9 |
Видим, чтовсе оценкиположительны,значит любоеувеличениекакой-либосвободнойпеременнойуменьшит критерий.Данное решениеявляется оптимальным.Изобразим эторешение награфике:
Видим, что
2 вариант.
Отмечаяуспешно сданнуюсессию, вышеупомянутыестуденты взялистолько же пиваи в таких жепропорциях,за исключениемтого, что вместопива «Премьер»было купленопиво «Окское»,крепость которого6,4 % (дешевое иразбавленное).Определитьплан распитиянапитков дляполучениямаксимальногосуммарногоопьянения (в
Функция цели:
Приводимограниченияк каноническомувиду:
Решаемсимплекс-методом:
16 | 6,4 | 0 | 0 | 0 | 0 | |||
| Б.П. | X1 | X2 | X3 | X4 | X5 | X6 | В |
0 | X3 | 2 | 2 | 1 | 0 | 0 | 0 | 1,5 |
0 | X4 | 3,5 | 1 | 0 | 1 | 0 | 0 | 1,5 |
0 | X5 | 10 | 4 | 0 | 0 | 1 | 0 | 4,5 |
0 | X6 | 0 | 1 | 0 | 0 | 0 | 1 | 0,7 |
F | -16 | -10 | 0 | 0 | 0 | 0 | 0 |
16 | 6,4 | 0 | 0 | 0 | 0 | |||
| Б.П. | X1 | X2 | X3 | X4 | X5 | X6 | В |
0 | X3 | 0 | 1,428 | 1 | -0,571 | 0 | 0 | 0,642 |
16 | X1 | 1 | 1,286 | 0 | 0,286 | 0 | 0 | 0,428 |
0 | X5 | 0 | 1,142 | 0 | -2,85 | 1 | 0 | 0,214 |
0 | X6 | 0 | 1 | 0 | 0 | 0 | 1 | 0,7 |
F | 0 | -1,82 | 0 | 4,571 | 0 | 0 | 6,857 |
16 | 6,4 | 0 | 0 | 0 | 0 | |||
Св | Б.П. | X1 | X2 | X3 | X4 | X5 | X6 | В |
0 | X3 | 0 | 0 | 1 | 3 | -1,25 | 0 | 0,375 |
16 | X1 | 1 | 0 | 0 | 1 | -0,25 | 0 | 0,375 |
6,4 | X2 | 0 | 1 | 0 | -2,5 | 0,875 | 0 | 0,1875 |
0 | X6 | 0 | 0 | 0 | 2,5 | -0,875 | 1 | 0,5125 |
F | 0 | 0 | 0 | 0 | 1,6 | 0 | 7,2 |
Видим, чтовсе оценкиположительны,значит оптимальноерешение достигнуто.Но одна из свободныхпеременных(
16 | 10 | 0 | 0 | 0 | 0 | |||
Св | Б.П. | X1 | X2 | X3 | X4 | X5 | X6 | в |
0 | X4 | 0 | 0 | 0,333 | 1 | -0,416 | 0 | 0,125 |
16 | X1 | 1 | 0 | -0,333 | 0 | 0,166 | 0 | 0,25 |
10 | X2 | 0 | 1 | 1,833 | 0 | -0,166 | 0 | 0,5 |
0 | X6 | 0 | 0 | -0,833 | 0 | 0,166 | 1 | 0,2 |
F | 0 | 0 | 0 | 0 | 1 | 0 | 7,2 |
Если оптимальноерешение достигнутов 2-х точках, тооно достигаетсяи на отрезкемежду ними.Можно составитьуравнениеданного отрезкапо формуле:
На графикевидно, чтооптимальноерешение достигаетсяна отрезке,значит являетсяальтернативным.Вектор градиентацелевой функции(F) параллеленрадиус-векторуограничения(3). Это ограничениеобразует всемножествооптимальныхрешений.
Можно сделатьвывод, чтоальтернативныерешения имеются,когда все оценкисвободныхпеременныхбольше 0, а средикоэффициентовцелевой функцииоценка однойиз свободныхпеременныхравна 0.
3 вариант.
СтудентПетров, решивдогнать поколичествувыпитого студентаСидорова, выпил4 доли пива «Русич»вместо запланированных3,5. Решим задачус учетом изменившихсяданных.
Функцияцели:
Приводимограниченияк каноническомувиду:
Решим задачусимплекс-методом.
16 | 10 | 0 | 0 | 0 | 0 | |||
| Б.П. | X1 | X2 | X3 | X4 | X5 | X6 | в |
0 | X3 | 2 | 2 | 1 | 0 | 0 | 0 | 1,5 |
0 | X4 | 4 | 1 | 0 | 1 | 0 | 0 | 1,5 |
0 | X5 | 10 | 4 | 0 | 0 | 1 | 0 | 4,5 |
0 | X6 | 0 | 1 | 0 | 0 | 0 | 1 | 0,7 |
F | -16 | -10 | 0 | 0 | 0 | 0 | 0 |
16 | 10 | 0 | 0 | 0 | 0 | |||
| Б.П. | X1 | X2 | X3 | X4 | X5 | X6 | В |
0 | X3 | 0 | 1,5 | 1 | -0,5 | 0 | 0 | 0,75 |
16 | X1 | 1 | 0,25 | 0 | 0,25 | 0 | 0 | 0,375 |
0 | X5 | 0 | 1,5 | 0 | -2,5 | 1 | 0 | 0,75 |
0 | X6 | 0 | 1 | 0 | 0 | 0 | 1 | 0,7 |
F | 0 | -6 | 0 | 4 | 0 | 0 | 6 |
16 | 10 | 0 | 0 | 0 | 0 | |||
Св | Б.П. | X1 | X2 | X3 | X4 | X5 | X6 | в |
10 | X2 | 0 | 1 | 1,666 | -0,333 | 0 | 0 | 0,5 |
16 | X1 | 1 | 0 | -0,166 | 0,333 | 0 | 0 | 0,25 |
0 | X5 | 0 | 0 | -1 | -2 | 1 | 0 | 0 |
0 | X6 | 0 | 0 | -0,666 | 0,333 | 0 | 1 | 0,2 |
F | 0 | 0 | 4 | 2 | 0 | 0 | 9 |
Данное оптимальноерешение являетсявырожденным,т.к. положительныхкомпонентовменьше числаограничений.На существованиевырожденногооптимальногорешения указываетналичие всимплекс-таблиценулевого свободногочлена при найденномоптимальномрешении.
В случаевырожденногорешения симплекс-таблицаможет зацикливаться.Существует2 способа предупреждениязацикливания:
а)
б) Если минимальноеотношениесвободныхкоэффициентовк положительнымчленам разрешающегостолбца определяетсянеоднозначно,то выбираетсяотношениелюбого другогостолбца кположительнымкоэффициентамданного столбца,пока строкане определитсяоднозначно.
4вариант.
В связи снеожиданнополученнойстипендией,запасы пиварезко увеличились.
Функция цели:
Приводимограниченияк каноническомувиду:
В матрицеусловий нетединичнойподматрицы,поэтому используемметод искусственногобазиса. Построимвспомогательнуюзадачу.
Решаемвспомогательнуюзадачу симплекс-методом:
0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | |||
| Б.П. | X1 | X2 | X3 | X4 | X5 | X6 | X7 | X8 | X9 | X10 | в |
1 | X7 | 2 | 2 | -1 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 1,5 |
1 | X8 | 3.5 | 1 | 0 | -1 | 0 | 0 | 0 | 1 | 0 | 0 | 1,5 |
1 | X9 | 10 | 4 | 0 | 0 | -1 | 0 | 0 | 0 | 1 | 0 | 4,5 |
1 | X10 | 0 | 1 | 0 | 0 | 0 | -1 | 0 | 0 | 0 | 1 | 0,7 |
F | 15,5 | 8 | -1 | -1 | -1 | -1 | 0 | 0 | 0 | 0 | 0 |
0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | |||
| Б.П. | X1 | X2 | X3 | X4 | X5 | X6 | X7 | X8 | X9 | X10 | в |
1 | X7 | 0 | 1,428 | -1 | 0,571 | 0 | 0 | 1 | -0,571 | 0 | 0 | 0,642 |
0 | X1 | 1 | 0,285 | 0 | -0,285 | 0 | 0 | 0 | 0,285 | 0 | 0 | 0,428 |
1 | X9 | 0 | 1,142 | 0 | 2,857 | -1 | 0 | 0 | -2,85 | 1 | 0 | 0,214 |
1 | X10 | 0 | 1 | 0 | 0 | 0 | -1 | 0 | 0 | 0 | 1 | 0,7 |
F | 0 | 3.571 | -1 | 3,428 | -1 | -1 | 0 | -4,42 | 0 | 0 | 1,557 |
0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | |||
| Б.П. | X1 | X2 | X3 | X4 | X5 | X6 | X7 | X8 | X9 | X10 | в |
1 | X7 | 0 | 0 | -1 | -3 | 1,25 | 0 | 1 | 3 | -1,25 | 0 | 0,375 |
0 | X1 | 1 | 0 | 0 | -1 | 0,25 | 0 | 0 | 1 | -0,25 | 0 | 0,375 |
0 | X2 | 0 | 1 | 0 | 2,5 | -0,875 | 0 | 0 | -2,5 | 0,875 | 0 | 0,187 |
1 | X10 | 0 | 0 | 0 | -2,5 | 0,875 | -1 | 0 | 2,5 | -0,875 | 1 | 0,512 |
F | 0 | 0 | -1 | -5,5 | 2,125 | -1 | 0 | 4,5 | -3,12 | 0 | 0,887 |
0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | |||
| Б.П. | X1 | X2 | X3 | X4 | X5 | X6 | X7 | X8 | X9 | X10 | в |
1 | X8 | 0 | 0 | -0,333 | -1 | 0,416 | 0 | 0,333 | 1 | -0,416 | 0 | 0,125 |
0 | X1 | 1 | 0 | 0,333 | 0 | -0,166 | 0 | -,333 | 0 | 0,166 | 0 | 0,25 |
0 | X2 | 0 | 1 | -0,833 | 0 | 0,166 | 0 | 0,833 | 0 | -0,166 | 0 | 0,5 |
1 | X10 | 0 | 0 | 0,833 | 0 | -0,166 | -1 | -0,833 | 0 | 0,166 | 1 | 0,2 |
F | 0 | 0 | 0,5 | -1 | 0,25 | -1 | -1,5 | 0 | -1,25 | 0 | 0,325 |
0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | |||
| Б.П. | X1 | X2 | X3 | X4 | X5 | X6 | X7 | X8 | X9 | X10 | в |
1 | X8 | 0 | 0 | 0 | -1 | 0,35 | -0,4 | 0 | 1 | -0,35 | 0,4 | 0,205 |
0 | X1 | 1 | 0 | 0 | 0 | -0,1 | 0,4 | 0 | 0 | 0,1 | -0,4 | 0,17 |
0 | X2 | 0 | 1 | 0 | 0 | 0 | -1 | 0 | 0 | 0 | 1 | 0,7 |
0 | X3 | 0 | 0 | 1 | 0 | -0,2 | -1,2 | -1 | 0 | 0,2 | 1,2 | 0,24 |
F | 0 | 0 | 0 | -1 | 0,35 | -0,4 | -1 | 0 | -1,35 | -0,6 | 0,205 |
0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | |||
Св | Б.П. | X1 | X2 | X3 | X4 | X5 | X6 | X7 | X8 | X9 | X10 | в |
0 | X5 | 0 | 0 | 0 | -2,85 | 1 | -1,14 | 0 | 2,857 | -1 | -1,142 | 0,585 |
0 | X1 | 1 | 0 | 0 | -0,285 | 0 | 0,285 | 0 | 0,285 | 0 | -0,285 | 0,228 |
0 | X2 | 0 | 1 | 0 | 0 | 0 | -1 | 0 | 0 | 0 | 1 | 0,7 |
0 | X3 | 0 | 0 | 1 | -0,571 | 0 | -1,42 | -1 | -1,571 | 0 | 1,428 | 0,357 |
F | 0 | 0 | 0 | 0 | 0 | 0 | -1 | -1 | -1 | -1 | 0 |
Решим исходнуюзадачу:
16 | 10 | 0 | 0 | 0 | 0 | |||
Св | Б.П. | X1 | X2 | X3 | X4 | X5 | X6 | в |
0 | X5 | 0 | 0 | 0 | -2,85 | 1 | -1,14 | 0,585 |
16 | X1 | 1 | 0 | 0 | -0,285 | 0 | 0,285 | 0,228 |
10 | X2 | 0 | 1 | 0 | 0 | 0 | -1 | 0,7 |
0 | X3 | 0 | 0 | 1 | -0,571 | 0 | -1,42 | 0,357 |
F | 0 | 0 | 0 | -4,576 | 0 | -5,424 | 3,648 |
К
5вариант.
После отмеченноготаким образомпраздникаобязательнонаступаетпохмелье. Решимзадачу из предыдущеговарианта, минимизируяэтот неприятныйфактор, т.е. функцияцели:
Приводимограниченияк каноническомувиду:
Эта задачарешается методомискусственногобазиса, т.к. вней нет единичнойподматрицы.Вспомогательнаязадача получаетсяточно такойже, как и в предыдущемварианте, поэтомупросто возьмемопорный планиз предыдущейзадачи.
16 | 10 | 0 | 0 | 0 | 0 | |||
Св | Б.П. | X1 | X2 | X3 | X4 | X5 | X6 | в |
0 | X5 | 0 | 0 | 0 | -2,85 | 1 | -1,14 | 0,585 |
16 | X1 | 1 | 0 | 0 | -0,285 | 0 | 0,285 | 0,228 |
10 | X2 | 0 | 1 | 0 | 0 | 0 | -1 | 0,7 |
0 | X3 | 0 | 0 | 1 | -0,571 | 0 | -1,42 | 0,357 |
F | 0 | 0 | 0 | -4,576 | 0 | -5,424 | 3,648 |
Видим, чтооценки свободныхпеременныхменьше нуля,значит решениеоптимальное.
Д
Область неограничена,но существуетоптимальноерешение
ТелешовойЕлизаветы, гр.726,
Для изготовленияопределенногосплава из свинца,цинка и оловаиспользуетсясырье из техже металлов,отличающеесясоставом истоимостью.
Сырье | Содержаниев процентах | ||||
Компоненты | 1 | 2 | 3 | 4 | 5 |
Свинец | 10 | 10 | 40 | 60 | 70 |
Цинк | 10 | 30 | 50 | 30 | 20 |
Олово | 80 | 60 | 10 | 10 | 10 |
Стоимость,у. е. | 4 | 4,5 | 5,8 | 6 | 7,5 |
Определить,сколько нужновзять сырьякаждого вида,чтобы изготовитьс минимальнойсебестоимостьюсплав, содержащийолова не более30%,цинка не менее10%,свинца не более40%.
Пусть хi – доля сырьяi-говида в единицеполученногосплава. Тогдафункция цели(себестоимостьединицы сплавав у.е.) запишетсяследующимобразом:
Системаограниченийбудет иметьвид:
Запишемсистему вканоническомвиде:
Решимпоставленнуюзадачу методомискусственного базиса. Дляэтого составимрасширеннуюзадачу:
Составимвспомогательнуюцелевую функцию:
Тогда:
Запишем начальнуюсимплекс-таблицу:
4 | 4,5 | 5,8 | 6 | 7,5 | 0 | 0 | 0 | M | M | |||
Св | Б.П. | X1 | X2 | X3 | X4 | X5 | X6 | X7 | X8 | X9 | X10 | В |
M | X9 | 1 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 1 | 0 | 1 |
0 | X6 | 0,8 | 0,6 | 0,1 | 0,1 | 0,1 | 1 | 0 | 0 | 0 | 0 | 0,3 |
M | X10 | 0,1 | 0,3 | 0,5 | 0,3 | 0,2 | 0 | -1 | 0 | 0 | 1 | 0,1 |
0 | X8 | 0,1 | 0,1 | 0,4 | 0,6 | 0,7 | 0 | 0 | 1 | 0 | 0 | 0,4 |
F | -4 | -4,5 | -5,8 | -6 | -7,5 | 0 | 0 | 0 | 0 | 0 | 0 | |
FM | 1,1 | 1,3 | 1,5 | 1,3 | 1,2 | 0 | -1 | 0 | 0 | 0 | 1,1 |
Оптимальнаясимплекс-таблицабудет иметьвид:
4 | 4,5 | 5,8 | 6 | 7,5 | 0 | 0 | 0 | M | M | |||
Св | Б.П. | 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 | -0,2 | -1,7 | -2,6 | 0 | 0 | -6,06 | 0 | 5,28 | |
FM | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | -1 | -1 | 0 |
Полученноерешение будетоптимальным,поскольку всеоценки неположительные.Запишем оптимальноерешение:
Экономическиполученноерешение интерпретируетсяследующимобразом: дляполученияединицы сплаваминимальнойсебестоимостинеобходимовзять 40% сырья№2 и 60% сырья №3.При этом сплавсодержит ровно30% олова, более20% (точнее, 42%) цинкаи менее 40% (28%) свинца.Минимальнаясебестоимостьединицы сплавасоставляет5,28 у.е.
Задача, двойственнаяк исходной,строитсяследующимобразом:
1) Исходнаязадача – наминимум, следовательно,двойственнаязадача – намаксимум.
2) Матрицакоэффициентовсистемы ограниченийбудет представлятьсобой транспонированнуюматрицу соответствующихкоэффициентовисходной задачи.При этом всеограничениядолжны бытьодного типа,например "большеили равно".Поэтому преобразуемвторое и четвертоеограниченияк типу "большеили равно",умножив их на–1, затем транспонируемполученнуюматрицу:
3) Числопеременныхв двойственнойзадаче равночислу ограниченийв исходной,т.е. 4, и наоборот,число ограниченийв двойственнойзадаче равночислу переменныхв исходной,т.е. 5. Переменная
4) Коэффициентамипри переменных
а правымичастями ограниченийдвойственнойзадачи являютсякоэффициентыцелевой функцииисходной задачи,т.е. вектор
5) Т.к. все переменныеисходной задачинеотрицательны,то все ограничениядвойственнойзадачи будутнеравенствамитипа «
Таким образом,математическаямодель двойственнойзадачи следующая:
Проанализируемтеперь экономическийсмысл двойственнойзадачи. Дляэтого сначаларассмотримэкономическийсмысл переменных
Таким образом,экономическийсмысл ограниченийзаключаетсяв следующем.Пусть, рассматриваемаяфирма вместотого, чтобыпроизводитьсплав из указанныхпяти видовсырья, решила,приобретя унекой другойфирмы цинк поцене
Целеваяфункция даннойдвойственнойзадачи экономическиинтерпретируетсякак максимальнаяприбыль фирмы-поставщикаресурсов.
1. Решениес помощью IBLP.
Введязадачу в программу,получаем следующееоптимальноерешение:
1 | -0,3 | 0,1 | -0,4 | 0 | 0 | 0 | 0 | 0 | |||
Св | Б.П. | Y1 | Y2 | Y3 | Y4 | Y5 | Y6 | Y7 | Y8 | Y9 | В |
1 | Y1 | 1 | 0 | 0,54 | -0,46 | 0 | -0,2 | 1,2 | 0 | 0 | 6,06 |
-0,3 | Y2 | 0 | 1 | 0,4 | -0,6 | 0 | -2 | 2 | 0 | 0 | 2,6 |
0 | Y5 | 0 | 0 | -0,12 | -0,12 | 1 | -1,4 | 0,4 | 0 | 0 | 0,02 |
0 | Y8 | 0 | 0 | -0,2 | -0,2 | 0 | 0 | -1 | 1 | 0 | 0,2 |
0 | Y9 | 0 | 0 | -0,3 | -0,3 | 0 | 0 | -1 | 0 | 1 | 1,7 |
T | 0 | 0 | 0,32 | 0,12 | 0 | 0,4 | 0,6 | 0 | 0 | 5,28 |
2. Решениепо второй теоремедвойственности.
Согласновторой теоремедвойственности,планы
Покомпонентнодля наших задачэти соотношениязаписываютсяследующимобразом:
Из системы(5) видно, что вовтором и третьемуравненияхв скобках получаетсяноль, поскольку
Из первогои третьегоуравненийсистемы (5) имеем:
откуда
Таким образом,
3. Решениес помощьюсимплекс-таблицыисходной задачи.
Запишем ещераз оптимальнуюсимплекс-таблицуисходной задачи:
4 | 4,5 | 5,8 | 6 | 7,5 | 0 | 0 | 0 | M | M | |||
Св | Б.П. | 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 | -0,2 | -1,7 | -2,6 | 0 | 0 | -6,06 | 0 | 5,28 | |
FM | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | -1 | -1 | 0 |
Из теорииизвестно, чтосправедливыследующиеформулы:
В системеограничений(2) исходной задачипеременной
Теперь запишемусловие (8) длянашего случая:
С учетом того,что мы решалисимплекс-методомне исходнуюзадачу (1), а задачув каноническойформе (2), т.е. пооптимальнойсимплекс-таблицемы можем найтирешение двойственнойзадачи к каноническойформе исходнойзадачи. Очевидно,задача в симметричнойи каноническойформе – дверазные задачи,отличающиесязнаком и количествомограниченийв двойственныхзадачах. Болеетого, так каквсе ограниченияв каноническойзадаче – равенства,то в двойственнойзадаче все
4. Решениечерез матрицу,обратную кбазисной.
Оптимальноерешение двойственнойзадачи можнонайти по формуле
Получим:
Откуда
Такимобразом, мывидим, что всемичетырьмя способамибыло полученоодно и то жерешение:
Согласнопервой теоремедвойственности,если одна изпары двойственныхзадач имеетоптимальныйплан, то и другаяимеет оптимальныйплан, причемзначения функцийцели при оптимальныхпланах равнымежду собой;если же целеваяфункция однойиз задач неограниченна,то другая совсемне имеет планов,и наоборот.
В нашем случаепара задачимеет оптимальныепланы, значенияцелевых функцийпри которыхравны 5,28.Экономическийсмысл этогосостоит в том,что в оптимальномплане минимальныезатраты фирмына производствотонны сплаваравны максимальнойприбыли некойдругой фирмыот продажипервой фирменеобходимыхдля производстваресурсов поусловным ценам,равным двойственнымоценкам этихресурсов.
Как былоуказано выше,вторая теоремадвойственностизаключаетсяв выполнениисоотношенийдополняющейнежесткостив случае оптимальностипланов парызадач (соотношения(5) и (6)). Приведемсначала экономическуюинтерпретациюусловия (6). Каждомуиз четырёх"ресурсов"исходной задачисоответствуетего двойственнаяоценка, илиусловная цена(
т.е.первый и второй"ресурсы"используютсяполностью иявляются дефицитными.Следует оговориться,что первоеравенствовыполняетсявсегда, в противномслучае задачане имеет решения.Это логическипонятно, посколькусумма частейвсегда равнацелому. Чтокасается третьегои четвёртогоресурсов, тоони имеют нулевуюдвойственнуюоценку, т.е. этиресурсы неявляется дефицитным.Рассмотримтеперь условие(5). Поскольку
Экономическиэто значит, чтозатраты насырье №1, 4 и 5 превосходятвозможныезатраты в случаезакупки отдельныхресурсов, поэтомуэти виды сырьяиспользоватьсяне будут. С другойстороны,
т.е.затраты насырье первогои второго видаравны альтернативнымзатратам напроизводство,значит эти видысырья будутиспользоваться.
Третья теоремадвойственностипозволяетопределитьзависимостьизмененияцелевой функцииначальнойзадачи от изменениязапасов "ресурсов":
ТелешовойЕлизаветы, гр.726,
Для изготовленияопределенногосплава из свинца,цинка и оловаиспользуетсясырье из техже металлов,отличающеесясоставом истоимостью.
Сырье | Содержаниев процентах | ||||
Компоненты | 1 | 2 | 3 | 4 | 5 |
Свинец | 10 | 10 | 40 | 60 | 70 |
Цинк | 10 | 30 | 50 | 30 | 20 |
Олово | 80 | 60 | 10 | 10 | 10 |
Стоимость,у. Е. | 4 | 4,5 | 5,8 | 6 | 7,5 |
Определить,сколько нужновзять сырьякаждого вида,чтобы изготовитьс минимальнойсебестоимостьюсплав, содержащийолова не более30%,цинка не менее10%,свинца не более40%.
Математическаямодель:
Пусть хi – доля сырьяi-говида в единицеполученногосплава. Тогдафункция цели(себестоимостьединицы сплавав у.е.) запишетсяследующимобразом:
Системаограниченийбудет иметьвид:
Запишемсистему вканоническомвиде:
Оптимальнаясимплекс-таблица:
4 | 4,5 | 5,8 | 6 | 7,5 | 0 | 0 | 0 | M | M | |||
Св | Б.П. | 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 | -0,2 | -1,7 | -2,6 | 0 | 0 | -6,06 | 0 | 5,28 |
Оптимальноерешение:
Экономическиполученноерешение интерпретируетсяследующимобразом: дляполученияединицы сплаваминимальнойсебестоимостинеобходимовзять 40% сырья№2 и 60% сырья №3.При этом сплавсодержит ровно30% олова, более20% (точнее, 42%) цинкаи менее 40% (28%) свинца.Минимальнаясебестоимостьединицы сплавасоставляет5,28 у.е. Оптимальныедвойственныеоценки
Теперь найдёмобласть устойчивостидвойственныхоценок к изменениюсвободныхчленов ограничений.Как известно,область устойчивостидвойственныхоценок – этообласть изменениясвободныхчленов ограничений,при которойдвойственныеоценки не меняются.Неизменностьдвойственныхоценок говорито том, что неменяют своихномеров базисныеи свободныепеременныев решении.
В связи свычислениеминтерваловустойчивостинеобходимосделать замечаниео знаках неравенств.Мы помним, чтоизначальноих изменениемы учитывали(), но знакисамих неравенствне меняли. Сейчасмы также небудем менятьзнаки второгои четвёртогонеравенств,но примем вовнимание обратныйзнак
Пусть свободныечлены изменилисьна
Базисноерешение вычисляетсячерез матрицу,обратную кбазисной, исвободные членыограничений.Из оптимальнойсимплекс-таблицыполучим матрицу,обратную кбазисной, иоптимальноерешение (базисныекомпоненты):
Все элементырешения должныбыть неотрицательны,иначе решениебудет недопустимым,т.е. базисноерешение остаётсяоптимальнымдо тех пор, покаоно допустимое.Область устойчивостиследующая:
Теперь найдёминтервалыустойчивости(интервалустойчивостидвойственныхоценок к изменениюправой частиограниченияили i-горесурса – такоемножество i–горесурса, прикотором двойственныеоценки не меняются):
1)
2)
3)
4)
Полученныерезультатыэкономическиозначают, чтосвободный членв первом ограниченииможет менятьсяот 0,5 до 1,26,но экономическогосмысла это никакого не имеет,т.к. сумма составляющихдолей сплававсегда 100%. Содержаниеолова в новомсплаве варьируетсяот 10%до 60%,цинка – от нуля(
И
Примерпрактическогопримененияинтерваловустойчивости.
Изменимусловие задачиследующимобразом:
а) содержаниеолова в новомсплаве не должнопревосходить15%;
Интервалустойчивостидля олова – это
По третьейтеореме двойственностинайдём значениекритерия приэтом решении:
б) содержаниецинка должнобыть не менее45%;
Интервалустойчивостидля цинка -
Решениенедопустимое.Но если бы онобыло допустимым,то оно было быи оптимальным,а значит, оценкибы удовлетворяликритериюоптимальности.Полученноерешение являетсяпсевдопланоми можно использоватьдвойственныйсимплекс-метод.
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,03 |
F | -0,02 | 0 | 0 | -0,2 | -1,7 | -2,6 | 0 | 0 | -6,06 | 0 | 5,28 |
Определим,какую из переменныхвыведем избазиса. В данномслучае этобудет единственнаяотрицательнаяпеременная
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 | 2 | 1 | 0 | 1 | 1,5 | 0 | 5 | 0 | 2,5 | -5 | 0,25 |
0 | X8 | 0,3 | 0 | 0 | 0,5 | 0,75 | 0 | 1,5 | 1 | 0,35 | -1,5 | 0,075 |
5,8 | X3 | -1 | 0 | 1 | 0 | -0,5 | 0 | -5 | 0 | -1,5 | 5 | 0,75 |
0 | X6 | -0,3 | 0 | 0 | -0,5 | -0,75 | 1 | -2,5 | 0 | -1,35 | 2,5 | 0,075 |
F | -0,8 | 0 | 0 | -1,5 | -3,65 | 0 | -6,5 | 0 | 2,55 | 6,5 | 5,475 |
Как видим,оценки по-прежнемуудовлетворяюткритериюоптимальностии все базисныепеременныенеотрицательны,значит, решениедопустимоеи оптимальное.Новое решениезадачи
в) в новомсплаве должнобыть менее 40%олова и более30% цинка;
Запишемобласть устойчивостидвойственныхоценок, учитываяновые изменения(
Решениеявляется допустимым,а значит, иоптимальным.Значение критериянайдём по третьейтеореме двойственности:
г) менее 60%олова и более40% цинка;
В данномслучае изменениясоставляют:увеличениесодержанияолова на 30% и цинкана 30%, т.е
Решениенедопустимое,но являетсяпсевдопланом,поэтому, руководствуясьрассуждениями,аналогичнымипункту б), решимзадачу двойственнымсимплекс-методом.
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,1 |
F | -0,02 | 0 | 0 | -0,2 | -1,7 | -2,6 | 0 | 0 | -6,06 | 0 | 5,28 |
Оптимальнаясимплекс-таблица:
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 | 2 | 1 | 0 | 1 | 1,5 | 0 | 5 | 0 | 2,5 | -5 | 0.5 |
0 | X8 | 0,3 | 0 | 0 | 0,5 | 0,75 | 0 | 1,5 | 1 | 0,35 | -1,5 | 0,15 |
5,8 | X3 | -1 | 0 | 1 | 0 | -0,5 | 0 | -5 | 0 | -1,5 | 5 | 0,5 |
0 | X6 | -0,3 | 0 | 0 | -0,5 | -0.75 | 1 | -2.5 | 0 | -1.35 | 2,5 | 0,25 |
F | -0,8 | 0 | 0 | -1,5 | -3,65 | 0 | -6,5 | 0 | 2,55 | 6,5 | 5,15 |
Получимследующеерешение:
Задача анализадополнительнозакупаемыхобъёмов ресурсовс целью обеспечениянаибольшейэффективностипланирования.
Предположим,что появиласьвозможностьпокупать сырьёу других поставщиковпо более низкойцене: цинк по2 у.е., а за оловои свинец, т.к.согласноэкономическомусмыслу задачиони являются"антиблагами",мы получаембольшую доплатуот их поставщика:1,5 у.е. и 0,5 у.е. соответственно.Руководительпредприятиявыделил назакупку ресурсов3 у.е.
Решение:
По ранееполученнымрезультатаммы знаем, чтопредприятиетратит минимумсредств (5,28 у.е.)когда в полученномсплаве ровно30% олова, 42% цинкаи 28% свинца (будемсчитать дляудобства, чтодля производства10 тонн сплаванеобходимо3 тонны олова,4,2 тонны цинкаи 2,8 тонн свинца).Т.к. олово и свинецмы получаемс доплатой, товозьмём их вполном объёме,необходимомдля производствасплава. От "покупки"олова мы получим
Будем вестианализ закупокцинка. На первойитерации мыне закупаемцинк, т.к. в этомслучае он быприносил большеубытка (двойственнаяоценка равнанулю по сравнениюс предлагаемойценой в 2 у.е.).Решив новуюзадачу безпроизводстваолова и свинца,мы безусловновыйдем за границыобласти устойчивостидвойственныхоценок. Крометого, сменитсярешение: двойственнаяоценка цинкаувеличитсядо 3 и новое значениецелевой функциипонизится до4 у.е. Вычтем изэтих затратна производствосплава доходот полученияолова и цинка:
С увеличениемдвойственнойоценки цинкастановитсявыгодно покупатьего. Но мы располагаемсуммой денегтолько 3 у.е. иможем закупитьна них 1,5 тоннвместо 2 необходимых.Теперь намнужно производитьтолько 0,5 тонныцинка. На второйитерации мыполучаем такоеже решение:критерий равен4 у.е. и двойственнаяоценка цинка,которого мыпроизводим3 тонны, равна4.
Таким образом,мы получилиоптимальноерешение расходованиявыделенных3 у.е.: "закупать"с доплатой 4тонны оловаи 5 тонн свинцаи покупать поцене 2 у.е. 1,5 тонныцинка. При такомплане предприятиеполучит прибыльот производствасплава в размере1,9 у.е.
Определиминтервал устойчивостирешения к изменениюстоимостисырья, то есть,в каких пределахмогут менятьсяцены на сырьё,чтобы планвыпуска сплаване изменился.Для этого рассмотримдва случая:изменение цен(коэффициентовцелевой функции)происходитна сырьё, использующеесяпри производствесплава (базисныепеременные)и не использующееся(свободныепеременные).
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. Рассмотримслучай со свободнойпеременной.
а)
Условиеоптимальностиоценки:
В данномслучае
Таким образом,решение будетоставатьсяоптимальным,при уменьшениикоэффициентапри
б) Будемруководствоватьсяаналогичнымирассуждениямипри вычисленииинтерваловустойчивостидля четвёртогои пятого ресурсов.
Оптимальныерешения при конкретныхизмененияхкоэффициентов.
а)стоимостьвторого сырьяувеличиласьдо 4,5 у.е
Интервалустойчивостикоэффициентацелевой функции
б) стоимостьтретьего сырьяуменьшиласьдо 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 |
Получимоптимальноерешение
в) издержкина первое сырьёвозросли до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 |
С помощьюсимплекс-методаполучаем оптимальноерешение
В этом пункте,как и в предыдущем,можно рассматриватьдва случая:изменениезначенийкоэффициентов,соответствующихбазисным переменными свободнымпеременным.Изменениезначенийкоэффициентовпри базисныхпеременныхприводит кизменениюбазисной матрицы,поэтому проанализироватьэто довольносложно, ленчерешить задачузаново. Следовательно.Рассмотримслучай с изменениемкоэффициентапри свободнойпеременной.
Возьмем,например, какизменяющийсякоэффициент
Возьмём такжедля наглядностиизменение ещёодного коэффициента,т.к. полученныйвыше результатозначает, чтосодержаниесплава (т.е всехкомпонентов)в первом сырьеможет менятьсяот 0% до 100% (формальноот 0% до 100,3%).
В качествепримера толькоиз чистогоматематическоголюбопытстваприведем такуюфантастическуюситуацию: содержаниесплава в первомсырье возрослодо:
а) 100,2%
б) 110%
Симплекс-методомполучим оптимальноерешение:
Предположим,что появиласьвозможностьиспользоватьновый вид сырья,в котором содержится40% олова, 60% цинкаи 30% свинца, икоторый обладаетстоимостью3,5 у.е. за единицу.Определим новыйплан производства.
Пусть
Решим, выгодноли использоватьновое сырьё.Для этоговоспользуемсядвойственнымиоценками
Доход на тоннунового сырьябудет равен
Запишем новуюсимплекс-таблицус учётом новойпеременной:
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 |
Оптимальноерешение будет
Пусть дляпроизводствасплава нужноиспользоватьещё один компонент– медь, содержащуюсяв сырье в количествах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 |
Оптимальноерешение:
ТелешовойЕлизаветы, гр.726,
В некоторомцарстве, некоторомгосударствежил-был котВасилий, которыйочень любилмышей… на обед.А обедал онисключительнов амбаре своегохозяина, да такхорошо, чтобедные мышии носу не могливысунуть изсвоих нор. Новсю жизнь вноре не просидишь,есть то хочется,и стали мышидумать и гадать,как им провестикота Василияи до заветныхпищевых ресурсовамбара добраться.
В амбаре было4 мышиных норы:в первой проживало15 мышей, во второй– 20, в третьей– 10 мышей, а вчетвертой –25 мышей, а также5 источниковпищи, от которыхи кормиласьвся эта оравамышей: у окорока– 5 мышей, у мешкакрупы – 18 мышей,у мешка муки– 17 мышей, у мешкакартошки – 22мыши и у стопкистарых газети журналовэротическогосодержания– 8 мышей.
И тут мышивспомнили, чтокогда-то в стопкежурналов лежалакнижка поматематическомупрограммированию.Конечно мышидавным-давноуспели ее сгрызть,но кое-что изнее они, покагрызли, прочитатьуспели, в частности,как решатьтранспортныезадачи.
Считая что
1)
2)
ну и конечно
Исходя изэтих условийони составилиматематическуюмодель процессасвоего питания:
Ну, и длянаглядностинарисовалиее в виде таблицы:
| окорок | мешоккрупы | мешокмуки | мешоккартошки | журналы | |
5 | 18 | 17 | 22 | 8 | ||
нора1 | 15 | | | | | |
нора2 | 20 | | | | | |
нора3 | 10 | | | | | |
нора4 | 25 | | | | | |
В левом верхнемуглу каждойячейки таблицымыши указаличисло попавшихв лапы кота (впроцентах) поотношению кобщему числумышей из
Безусловно,цель мышей –добраться доеды с минимальнымипотерями подороге, то есть:
Таким образом:
Необходимо,конечно, оценитьи выгодностьпередвиженияиз каждой норык каждому пищевомуресурсу. Дляэтого мышиоценили такназываемыепотенциалынор (
Система (1) ибудет служитьв дальнейшемкритериемоптимальностиплана.
Запишемподробно двойственнуюзадачу на основеэтого ограничения:
Критериемдвойственнойзадачи будетмаксимизациявыгодности:
Первое, чтопришло на уммышам – использоватьте источникипищи, доступк которым легче,и они решилипостроитьначальныйопорный планпо методумаксимальнойзагрузки, исходяиз формулы:
т.е. выбираютсяте варианты,которые могутобеспечитьедой максимальноеколичествомышей, и этиварианты будутиспользоватьсяв соответствиис (2).
Посколькухотят есть всемыши во всехнорах, то модельзакрытая, т.е.
Общая схемапостроенияначальногоопорного планапо методумаксимальнойзагрузки такова:
1) Выбираемкоммуникацию,которую можнобольше всегозагрузить.
2) Максимальноее загружаемв соответствиис (2).
3) Корректируемобъемы производстваи потребленияна величинувыбраннойперевозки,вычисляя остаткипроизводстваи потребления:
4) Вычеркиваемв транспортнойтаблице строкуили столбецс нулевым объемомпроизводстваили потребления:
если
если
5) Повторяемэтот процессс пункта 1 по4, пока не будутперечеркнутывсе строки илистолбцы
В нашем случаеэто выглядитследующимобразом:
| окорок | мешоккрупы | мешокмуки | мешоккартошки | журналы | |
5 2 0 | 18 0 | 17 2 0 | 22 0 | 8 0 | ||
нора1 | 15 0 | | | | | |
нора2 | 20 2 0 | | | | | |
нора3 | 10 2 0 | | | | | |
нора4 | 25 3 0 | | | | | |
Римскимицифрами пронумерованпорядок итераций.
I.
II.
III.
IV.
V.
VI.
VII.
Порассуждавтаким образом,мыши получилиследующий начальныйопорный план:
По этомуопорному планукоту достанетсяаж 13 мышей (0,18 частьмыши отдельновряд ли выживет).“Жирноему будет”-,подумалимыши и сталисоставлятьдругой опорныйпланметодомсеверо-западногоугла.
Данный методочень прост,пункты 1 и 2 в методемаксимальнойзагрузки заменяютсяна следующий:очереднаязагружаемаякоммуникация
Последовательнопо итерациямметода получаем:
I.
II.
III.
IV.
V.
VI.
VII.
VIII.
| окорок | мешоккрупы | мешокмуки | мешоккартошки | журналы | |
5 0 | 18 8 0 | 17 5 0 | 22 17 0 | 8 0 | ||
нора1 | 15 10 0 | | | | | |
нора2 | 20 12 0 | | | | | |
нора3 | 10 5 0 | | | | | |
нора4 | 25 8 0 | | | | | |
Получилиследующийопорный план:
Те же самые13 мышей, и дажехуже предыдущегоопорного плана(если учитыватьсотые). Пришлосьмышам использоватьметод минимальныхзатрат.
В этом методев первую очередьзагружаютсяте коммуникации,в которых затратына перевозкуминимальные.В нашем случае,это те пути,мышиные потерина которыхминимальны.
| окорок | мешоккрупы | мешокмуки | мешоккартошки | журналы | |
5 0 | 18 0 | 17 0 | 22 20 18 15 0 | 8 0 | ||
нора1 | 15 0 | | | | | |
нора2 | 20 3 0 | | | | | |
нора3 | 10 2 0 | | | | | |
нора4 | 25 7 20 | | | | | |
I.
II.
III.
IV.
V.
VI.
VII.
VIII.
Опорный план:
Целеваяфункция:
Этот опорныйплан понравилсямышам значительнобольше, но всеравно потеридостаточновелики (7 мышей).Теперь требовалосьрешить этузадачу и найтиоптимальныйплан. И сделатьони это собралисьсамым точнымметодом – методомпотенциалов.
Если пландействительнооптимален, тосистема (1) будетвыполняться,т.е.:
1) для каждойзанятой клеткитранспортнойтаблицы суммапотенциаловдолжна бытьравна
2) для каждойнезанятойклетки суммапотенциаловне больше (меньшеили равно)
Построимдля каждойсвободнойпеременнойплана числа
| окорок | мешоккрупы | мешокмуки | мешоккартошки | журналы | ||
5 | 18 | 17 | 22 | 8 | |||
нора1 | 15 | | | | | | |
нора2 | 20 | | | | | | |
нора3 | 10 | | | | | | |
нора4 | 25 | | | | | | |
| | | | |
Таким образом,после того, каквсе потенциалынайдены, можноискать
Видно, что
Строим цикл:
(2; 1) – начальнаяточка цикла;
Что характерно,для этой точки(впрочем каки для других)мы можем построитьтолько одинцикл. Каждойклетке циклаприписываемопределенныйзнак:
(2; 1) – “+”, (4;1) – “-”, (4; 4) – “+” (2; 4) –“-”.
| окорок | мешоккрупы | мешокмуки | мешоккартошки | журналы | |
5 | 18 | 17 | 22 | 8 | ||
нора1 | 15 | | | | | |
нора2 | 20 | | | | | |
нора3 | 10 | | | | | |
нора4 | 25 | | | | | |
В клеткахс “+” – увеличиваемзагрузку, а вклетках с “-”– уменьшаем.Величина, накоторую увеличиваемили уменьшаемвсегда однаи она определяетсяиз условия:
Таким образомполучаем:
Перейдемк новому опорномуплану
| окорок | мешоккрупы | мешокмуки | мешоккартошки | журналы | ||
5 | 18 | 17 | 22 | 8 | |||
нора1 | 15 | | | | | | |
нора2 | 20 | | | | | | |
нора3 | 10 | | | | | | |
нора4 | 25 | | | | | | |
| | | | |
Определяем
Все
Целеваяфункция приэтом плане:
М-да, незначительноеулучшение длямышей. Целых6 мышей и ещеодин мышиныйхвостик – таковаежедневнаядань коту Василию.Но делать нечего,и стали мышидействоватьпо этому плану.
И все былобы хорошо, нов 3 норе появилсядополнительныйприплод – 10 мышей,следовательнов ней сталопроживать 20мышей, а количествомышей, питающихсяу источниковпищи, осталосьтем же. Получиласьтак называемаяоткрытая модель,где:
иее необходимосбалансировать.Для этого нужноввести фиктивныйпункт потребления
идополнительныепеременные
При этом во2 и 3 норах всемыши должныбыть накормлены(во второй –самые умныемыши, а в третьей– большой приплод),поэтому второеи третье ограничения– уравнения.В первое и четвертоеограничениядобавим новыепеременныеR1и R4для уравновешиваниясистемы. А таккак этих источниковпищи на самомделе нет, то изатраты (потерипо дороге) наних нулевые.
В транспортнойтаблице в последнемстолбце введемеще 2 переменныев (2; 5) и (3; 5) – R2и R3, чтобыстолбец былполностьюзаполнен, а таккак перевозкив этих коммуникацияхне должны быть,то наложим наних очень большиештрафы М и включимвсе новые переменныев целевую функцию:
Так как критерийстремится кминимуму, тов оптимальномплане перевозкис самыми большимизатратами недолжны осуществляться(т.е.
| окорок | мешок крупы | мешок муки | мешок картошки | журналы | R | ||
5 0 | 18 15 0 | 17 0 | 22 10 0 | 8 0 | 10 5 0 | |||
нора 1 | 15 5 | | | | | | | |
нора 2 | 20 3 0 | | | | | | | |
нора 3 | 2012 0 | | | | | | | |
нора 4 | 25 10 5 0 | | | | | | | |
| | | | | |
Определяем
| окорок | мешок крупы | мешок муки | мешок картошки | журналы | R | ||
5 | 18 | 17 | 22 | 8 | 10 | |||
нора 1 | 15 | | | | | | | |
нора 2 | 20 | | | | | | | |
нора 3 | 20 | | | | | | | |
нора 4 | 25 | | | | | | | |
| | | | | |
Определяем
| окорок | мешок крупы | мешок муки | мешок картошки | журналы | R | ||
5 | 18 | 17 | 22 | 8 | 10 | |||
нора 1 | 15 | | | | | | | |
нора 2 | 20 | | | | | | | |
нора 3 | 20 | | | | | | | |
нора 4 | 25 | | | | | | | |
| | | | | |
Определяем
Все
Целеваяфункция приэтом плане:
Этот планчуть хужепредыдущего,к тому же 10 мышейиз первой норыостаются голодными.Во всяком случаепитаются разв три дня.
Но кот Василийтоже не дремал,и, произведяте же операции,что и мыши всвое время,определилоптимальныйплан их передвижений(см. пункт 6). Посмотревна него, он сразурешил взятьпод особыйконтроль путьот второй норык мешку мукии от четвертойноры к мешкукрупы.
Вскоре мышиэто на себепочувствовали,а почувствовав,кинулись составлятьновый оптимальныйплан, пометивэти два маршрутакак чрезвычайноопасные буквойМ
| окорок | мешоккрупы | мешокмуки | мешоккартошки | журналы | ||
5 | 18 | 17 | 22 | 8 | |||
Нора1 | 15 | | | | | | |
Нора2 | 20 | | | | | | |
Нора3 | 10 | | | | | | |
Нора4 | 25 | | | | | | |
| | | | |
Видно, чтоэтот план ужеявляется оптимальным.
Целеваяфункция:
Как зыбкомышиное счастье.Стоило котувзяться за деловсерьез, и потеривозросли чутьли не в два раза.
ТелешовойЕлизаветы, гр.726,
1929 год. В СШАвеликая депрессия,введен сухойзакон. Странапросто задыхаетсябез спиртного.В этот сложныймомент группаинициативныхграждан подруководствомАль Капонерешает помочьродной стране.Ими планируетсяпоставка алкогольнойпродукции изЛиверпуля вШтаты. Благодарныесогражданеиз 5 крупныхгородов СШАготовы платитьбольшие деньгиза тонну спиртного:2000 долл. в Бостоне,3000 в Детройте,2500 в Вашингтоне,3200 в Нью-Йоркеи 1800 долл в Чикаго.Все 5 городовнаходятся наразном расстоянииот порта, кудаприбывает груз:Бостон – 250 миль,Детройт – 300 миль,Вашингтон –500 миль, Нью-Йорк–100 миль и Чикаго– 600 миль. Требуетсявыбрать города,в которых можнополучить максимальнуюприбыль отпродажи спиртного.При этом суммарноерасстояниеот этих портовдо порта с грузомне должно превышать1000 миль.
Данная задачаявляется задачейо ранце вида:
где критериемявляется функция
которая можетбыть устремленаи к максимуму,и к минимуму.
Для началасоставим следующуюматематическуюмодель:
Пусть
Целевойфункцией иликритерием будетявляться максимальнаяблагодарностьсограждан:
Далееотбираем портыпо приоритетности,т.е. в порядкеубывания отношения
Послеэтого определяемначальный планследующимобразом: пусть
Аналогичнорассуждая,далее получаем:
В последнемслучае оставшеесяпосле другихгородов расстояниеменьше 500 миль,поэтому
Таким образом,начальныйопорный план:
Значениецелевой функции:
Но
МножествоD, которомупринадлежит
1) Анализмножества D1.
Поскольку
Строим новыйопорный план:
Т.к.
Таким образом,новый опорныйплан:
2) Анализмножества D2.
Поскольку
Строим новыйопорный план:
Т.к.
Таким образом,новый опорныйплан:
3) Отсевнеперспективногоподмножества.
Так как
4) Анализмножества D3.
Поскольку
Строим новыйопорный план:
Т.к.
Таким образом,новый опорныйплан:
5) Анализмножества D4.
Поскольку
Строим новыйопорный план:
Т.к.
Таким образом,новый опорныйплан:
6) Отсевнеперспективногоподмножества.
Так как
7) Анализмножества D5.
Поскольку
Строим новыйопорный план,очевидно:
8) Анализмножества D6.
Поскольку
Ограничениенесовместное,поскольку дажепри
Таким образом,оптимальнымпланом даннойзадачи будет:
Всвязи с тем,что спиртноестало хорошораскупаться,Аль Капонерешил увеличитьпоставки. Ночтобы мирноспящее ФБР недай бог непроснулось,было решеноосуществлятьпоставки черезтри разныхпорта на восточномпобережье. Ценына спиртноев пяти вышеуказанныхгородах неизменились,расстояниеже от них (в милях)до портов указанов следующейтаблице:
Бостон | Детройт | Вашингтон | Нью-Йорк | Чикаго | |
Порт1 | 250 | 300 | 500 | 100 | 600 |
Порт2 | 100 | 200 | 700 | 400 | 300 |
Порт3 | 500 | 400 | 300 | 550 | 150 |
Во всех трехслучаях суммарноерасстояниеот порта догородов недолжно превышать1000 миль. Требуетсярешить тот жесамый вопрос:в какие городавыгоднее поставлятьпродукцию?
Задачао многомерномранце имеетследующуюматематическуюмодель:
где критериемявляется функция
Отзадачи об одномерномранце она отличаетсяналичием несколькихограничений.Таким образом,математическаямодель:
Пусть
Целевойфункцией иликритерием будетявляться максимальнаяблагодарностьсограждан:
Решимзадачу оценкикритерия длякаждого ограниченияв отдельности.Пусть множество
1) Анализмножества
Определяемначальный план:
В последнемслучае оставшеесяпосле другихгородов расстояниеменьше 500 миль,поэтому
Таким образом,начальныйопорный план:
2) Анализмножества
Определяемначальный план:
В последнемслучае оставшеесяпосле другихгородов расстояниетакже равно300 миль, поэтому
Таким образом,опорный план:
3) Анализмножества
Определяемначальный план:
В последнемслучае оставшеесяпосле другихгородов расстояниеменьше 550 миль,поэтому
Таким образом,опорный план:
4) Вычислениеверхней и нижнейграниц.
Вычисляемверхнюю границу:
Определяемопорные планыдля третьегоограничения:
a)
В последнемслучае оставшеесяпосле другихгородов расстояниеравно 50 миль,поэтому
б)
В последнемслучае оставшеесяпосле другихгородов расстояниеравно 100 миль,поэтому
в)В этом случае
Вычисляемнижнюю границу:
5) Ветвлениемножества D.
6) Анализмножества D1.
a)Определяемначальный пландля
В последнемслучае оставшеесяпосле другихгородов расстояниеменьше 500 миль,поэтому
Таким образом,новый опорныйплан:
б)Определяемначальный пландля
В последнемслучае оставшеесяпосле другихгородов расстояниеменьше 700 миль,поэтому
Таким образом,новый опорныйплан:
в)Определяемначальный пландля
В последнемслучае оставшеесяпосле другихгородов расстояниеменьше 100миль, поэтому
Таким образом,новый опорныйплан:
г)Вычислениеверхней и нижнейграниц.
Вычисляемверхнюю границу:
Определяемопорные планыдля первогоограничения:
–В этом случае
–
В последнемслучае оставшеесяпосле другихгородов расстояниеравно 450 миль,поэтому
–
В последнемслучае оставшеесяпосле другихгородов расстояниеравно 100миль, поэтому
Вычисляемнижнюю границу:
Т.к.
7) Анализмножества D2.
Поскольку
a)Определяемначальный пландля
В последнемслучае оставшеесяпосле другихгородов расстояниеменьше 500 миль,поэтому
Таким образом,новый опорныйплан:
б)Определяемначальный пландля
Таким образом,новый опорныйплан:
в)Определяемначальный пландля
В последнемслучае оставшеесяпосле другихгородов расстояниеменьше 400миль, поэтому
г)Вычислениеверхней и нижнейграниц.
Вычисляемверхнюю границу:
Определяемопорные планыдля третьегоограничения:
–
Впоследнемслучае оставшеесяпосле другихгородов расстояниеравно 50 миль,поэтому
–
В последнемслучае оставшеесяпосле другихгородов расстояниеравно 50 миль,поэтому
– В этом случае
Вычисляемнижнюю границу:
Т.к.
8) Отсевнеперспективногоподмножества.
Так как
9) Анализмножества D3.
Поскольку
a)Определяемначальный пландля
В последнемслучае оставшеесяпосле другихгородов расстояниеменьше 600 миль,поэтому
Таким образом,новый опорныйплан:
б)Определяемначальный пландля
В последнемслучае оставшеесяпосле другихгородов расстояниеменьше 700 миль,поэтому
Таким образом,новый опорныйплан:
в)Определяемначальный пландля
В последнемслучае оставшеесяпосле другихгородов расстояниеменьше 350миль, поэтому
Таким образом,новый опорныйплан:
г)Вычислениеверхней и нижнейграниц.
Вычисляемверхнюю границу:
Определяемопорные планыдля третьегоограничения:
–
В последнемслучае оставшеесяпосле другихгородов расстояниеравно 100 миль,поэтому
–
В последнемслучае оставшеесяпосле другихгородов расстояниеравно 300миль, поэтому
–В этом случае
Вычисляемнижнюю границу:
Т.к.
10) Анализмножества D4.
Поскольку
a)Определяемначальный пландля
В последнемслучае оставшеесяпосле другихгородов расстояниеменьше 500 миль,поэтому
Таким образом,новый опорныйплан:
б)Определяемначальный пландля
Таким образом,новый опорныйплан:
в)Определяемначальный пландля
В этом случаеоставшеесяпосле другихгородов расстояниеменьше 150 миль,поэтому
Таким образом,новый опорныйплан:
г)Вычислениеверхней и нижнейграниц.
Вычисляемверхнюю границу:
Определяемопорные планыдля третьегоограничения:
Очевидно,что поскольку
Вычисляемнижнюю границу:
Т.к.
Т
ТелешовойЕлизаветы, гр.726,
Испекла бабкаколобок и поставилаего остыватьна окошко. Ирешил колобок,что пока оностывает, онвполне можетобежать лес,посмотретьна лесных жителейи снова вернутьсяк деду и бабке.Сказано – сделано.Спрыгнул колобокиз окошка ипокатился влес. Помогитеколобку найтикратчайшиймаршрут егодвижения полесу, если расстояниямежду норамилесных жителей,а также домомдеда и бабкиданы в таблице.
Деди бабка | Заяц | Волк | Медведь | Лиса | |
Деди бабка | 0 | 6 | 4 | 5 | 2 |
Заяц | 6 | 0 | 3 | 3,5 | 4,5 |
Волк | 4 | 3 | 0 | 5,5 | 5 |
Медведь | 5 | 3,5 | 5,5 | 0 | 2 |
Лиса | 2 | 4,5 | 5 | 2 | 0 |
Для решениязадачи присвоимкаждому пунктумаршрута определенныйномер: дед ибабка – 1, заяц– 2, волк – 3, медведь– 4 и лиса – 5.Соответственнообщее количествопунктов
Для обеспечениянепрерывностимаршрута вводятсядополнительноnпеременных
Суммарнаяпротяженностьмаршрута F,которую необходимоминимизировать,запишется вследующем виде:
В нашем случаеэти условиязапишутся вследующем виде:
1) Анализмножества D.
Найдем оценкуснизу Н.Для этого определяемматрицу минимальныхрасстоянийпо строкам (1где расстояниеминимальнов строке).
Аналогичноопределяемматрицу минимальныхрасстоянийпо столбцам.
Выберемначальный план:
Очевидно,что
2
3
4
5
6)Отсев неперспективныхподмножеств.
ПодмножестваD13 и D15неперспективные.Т.к.
7
8)Анализ подмножестваD143.
9)Анализ подмножестваD145.
10)Отсев неперспективныхподмножеств.
ПодмножествоD143неперспективное.Т.к.
9
9
Оптимальноерешение:
Такимобразом, маршрутколобка: деди бабка – медведь– лиса – заяц– волк – дед ибабка.