работа № 2
Телешовой
Елизаветы, гр.
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 | |
;
Пересчитав
все оценки,
видим, что
,
значит критерий
можно улучшить.
Будем увеличивать
.
Пусть
,
тогда:
откуда получаем:
;
Все оценки
опорного плана
должны быть
неотрицательны,
а значит должны
выполняться
условия:
=>
Выведем из
базиса
.
Теперь базисными
переменными
являются
,
а свободными
.
Выразим функцию
цели через
новые переменные:
,
а из ограничений
(2)
и (3):
.
Тогда:
;
| 16 | 10 | 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 |
| 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 | |
Пересчитав
все оценки,
видим, что
,
значит критерий
можно улучшить.
Будем увеличивать
.
Пусть
,
тогда:
откуда получаем:
;
Все оценки
опорного плана
должны быть
неотрицательны,
а значит должны
выполняться
условия:
=>
Выведем из
базиса
.
Теперь базисными
переменными
являются
,
а свободными
.
Выразим функцию
цели через
новые переменные:
,
а из ограничений
(1)
и (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 | 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 | |
Критерий
можно улучшить,
т.к.
,
,
но нельзя найти
такое
,
при котором
базисные переменные
обращаются
в 0. Значит задача
неразрешима
из-за неограниченности
критерия.
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 | |
Видим, что
оценки свободных
переменных
меньше нуля,
значит решение
оптимальное.
;
F = 3,648.
Делаем
вывод: оптимальное
решение может
существовать
и при неограниченности
области.
Область не
ограничена,
но существует
оптимальное
решение
,
причем единственное,
которое достигается
в угловой точке.
11
Лабораторная
работа № 3
Телешовой
Елизаветы, гр.
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-го
вида в единице
полученного
сплава. Тогда
функция цели
(себестоимость
единицы сплава
в у.е.) запишется
следующим
образом:
.
Система
ограничений
будет иметь
вид:
(1).
Запишем
систему в
каноническом
виде:
(2).
Решим
поставленную
задачу методом
искусственного
базиса. Для
этого составим
расширенную
задачу:
(3).
Составим
вспомогательную
целевую функцию:
.
Выразим ее
через переменные,
не входящие
в начальный
базис
.
Выражая
из первого
ограничения,
а
из третьего
получаем:
;
;
Тогда:
.
Запишем начальную
симплекс-таблицу:
| 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) Т.к. все переменные
исходной задачи
неотрицательны,
то все ограничения
двойственной
задачи будут
неравенствами
типа «»
(поскольку
двойственная
задача на максимум).
Поскольку
первое условие
исходной задачи
представляет
собой равенство,
а остальные
три – неравенства,
то
может принимать
любые значения,
а
,и
– только положительные.
Таким образом,
математическая
модель двойственной
задачи следующая:
.
(4).
Проанализируем
теперь экономический
смысл двойственной
задачи. Для
этого сначала
рассмотрим
экономический
смысл переменных
,,
и
.
Из ограничений
видно, что величина
имеет размерность
[у.е./ед. сплава],
величина
–
[у.е./ед. олова],
–
[у.е./ед. цинка
], а
–
[у.е./ед. свинца].
Указать экономический
смысл переменной
не представляется
возможным в
силу условия
задачи. Что
касается
экономического
смысла переменных
и
,
то в системе
(1) они соответствует
второму и четвёртому
ограничениям,
отражающим
относительную
избыточность
ресурсов "олово"
и "свинец", т.е.
они могут быть
рассмотрены
как условный
убыток для
держателя этого
ресурса, или
цену, выплачиваемую
его приобретателю.
Таким образом,
олово и свинец
выступают в
данной задаче
в качестве
антиблага, что
экономически
также достаточно
абсурдно.
Экономический
смысл переменной
,
отражающей
ограниченность
ресурса "цинк",
виден явно: она
представляет
собой двойственную
оценку, или
условную цену
этого ресурса.
Таким образом,
экономический
смысл ограничений
заключается
в следующем.
Пусть, рассматриваемая
фирма вместо
того, чтобы
производить
сплав из указанных
пяти видов
сырья, решила,
приобретя у
некой другой
фирмы цинк по
цене
и взяв у нее
некоторое
количество
олова с доплатой
и свинца с
доплатой
,
производить
свой сплав из
этих компонентов
с учетом некоего
параметра
.
Стоимость
получаемых
компонент по
каждому виду
сырья в этом
случае не должна
превосходить
стоимость
единицы сырья.
Целевая
функция данной
двойственной
задачи экономически
интерпретируется
как максимальная
прибыль фирмы-поставщика
ресурсов.
Решение двойственной
задачи.
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 | |
.
Значение целевой
функции при
этом равно
5,28.
2. Решение
по второй теореме
двойственности.
Согласно
второй теореме
двойственности,
планы
и
начальной
и двойственной
задачи соответственно
являются оптимальными
тогда и только
тогда, когда
выполняются
соотношения:
(5)
(6)
Покомпонентно
для наших задач
эти соотношения
записываются
следующим
образом:
(5).
(6)
Из системы
(5) видно, что во
втором и третьем
уравнениях
в скобках получается
ноль, поскольку
и
положительны,
.
Из системы (6)
получаем, что
,
поскольку в
третьем и четвёртом
уравнениях
в скобках получаются
положительные
числа.
Из первого
и третьего
уравнений
системы (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 | |
Из теории
известно, что
справедливы
следующие
формулы:
(7);
(8).
В системе
ограничений
(2) исходной задачи
переменной
соответствует
первое ограничение,
содержащее
базисную переменную
,
переменной
– второе, содержащее
базисную переменную
,
переменной
– третье, содержащее
базисную переменную
и
– четвёртое
с переменной
.
Запишем условие
(7) для оценок
,,
и
приведенной
симплекс-таблицы:
;
;
;
;
Теперь запишем
условие (8) для
нашего случая:
,
что покомпонентно
записывается
как:
,
,
,
,
откуда
,
,
,
С учетом того,
что мы решали
симплекс-методом
не исходную
задачу (1), а задачу
в канонической
форме (2), т.е. по
оптимальной
симплекс-таблице
мы можем найти
решение двойственной
задачи к канонической
форме исходной
задачи. Очевидно,
задача в симметричной
и канонической
форме – две
разные задачи,
отличающиеся
знаком и количеством
ограничений
в двойственных
задачах. Более
того, так как
все ограничения
в канонической
задаче – равенства,
то в двойственной
задаче все
могут быть
любого знака,
поэтому наши
не являются
ошибкой. Но нам
необходимо
решить не
двойственную
к канонической
задаче, а двойственную
к симметричной.
Если сделать
замену
,
то двойственная
задача к симметричной
задаче примет
форму двойственной
к канонической
задаче. Следовательно,
или
.
4. Решение
через матрицу,
обратную к
базисной.
Оптимальное
решение двойственной
задачи можно
найти по формуле
.
Как видно из
оптимальной
симплекс-таблицы,
.
Тогда
.
Соответственно,
.
Получим:
,
Откуда
.
Таким
образом, мы
видим, что всеми
четырьмя способами
было получено
одно и то же
решение:
;.
Экономическая
интерпретация
трех теорем
двойственности.
Согласно
первой теореме
двойственности,
если одна из
пары двойственных
задач имеет
оптимальный
план, то и другая
имеет оптимальный
план, причем
значения функций
цели при оптимальных
планах равны
между собой;
если же целевая
функция одной
из задач неограниченна,
то другая совсем
не имеет планов,
и наоборот.
В нашем случае
пара задач
имеет оптимальные
планы, значения
целевых функций
при которых
равны 5,28.
Экономический
смысл этого
состоит в том,
что в оптимальном
плане минимальные
затраты фирмы
на производство
тонны сплава
равны максимальной
прибыли некой
другой фирмы
от продажи
первой фирме
необходимых
для производства
ресурсов по
условным ценам,
равным двойственным
оценкам этих
ресурсов.
Как было
указано выше,
вторая теорема
двойственности
заключается
в выполнении
соотношений
дополняющей
нежесткости
в случае оптимальности
планов пары
задач (соотношения
(5) и (6)). Приведем
сначала экономическую
интерпретацию
условия (6). Каждому
из четырёх
"ресурсов"
исходной задачи
соответствует
его двойственная
оценка, или
условная цена
(,,
и
соответственно).
В случае положительности
двойственной
оценки (в нашем
случае
и
)
справедливы
равенства
,
т.е.
первый и второй
"ресурсы"
используются
полностью и
являются дефицитными.
Следует оговориться,
что первое
равенство
выполняется
всегда, в противном
случае задача
не имеет решения.
Это логически
понятно, поскольку
сумма частей
всегда равна
целому. Что
касается третьего
и четвёртого
ресурсов, то
они имеют нулевую
двойственную
оценку, т.е. эти
ресурсы не
является дефицитным.
Рассмотрим
теперь условие
(5). Поскольку
,
то справедливы
неравенства:
.
Экономически
это значит, что
затраты на
сырье №1, 4 и 5 превосходят
возможные
затраты в случае
закупки отдельных
ресурсов, поэтому
эти виды сырья
использоваться
не будут. С другой
стороны,
,,
следовательно,
т.е.
затраты на
сырье первого
и второго вида
равны альтернативным
затратам на
производство,
значит эти виды
сырья будут
использоваться.
Третья теорема
двойственности
позволяет
определить
зависимость
изменения
целевой функции
начальной
задачи от изменения
запасов "ресурсов":
,
т.е. в нашем случае
как изменяются
минимальные
издержки на
производство
единицы сплава
в зависимости
от изменения
"ресурсов".
Так, пусть, например,
максимальная
доля олова
увеличится
на 0,1, т.е. до 40 %. Тогда,
по третьей
теореме двойственности,
минимальные
издержки на
производство
единицы сплава
уменьшатся
на
[у.е.].
С другой стороны,
изменение
минимальной
доли цинка или
свинца не приведет
к изменению
минимальных
издержек, поскольку
их двойственные
оценки равны
нулю. Но двойственные
оценки позволяют
о влиянии на
целевую функцию
не любых изменений
ресурсов, а
лишь таких,
какие не приводят
к недопустимости
оптимального
решения.
7
Лабораторная
работа № 4
Телешовой
Елизаветы, гр.
726,
Послеоптимизационный
анализ задач
линейного
программирования.
1.Анализ чувствительности
оптимального
решения задачи
к изменению
свободных
членов ограничений.
Для изготовления
определенного
сплава из свинца,
цинка и олова
используется
сырье из тех
же металлов,
отличающееся
составом и
стоимостью.
Сырье | Содержание в процентах | ||||
Компоненты | 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%,
цинка – от нуля
(
не имеет экономической
интерпретации)
до 42%
и свинца – от
28%
до 100% (аналогично
случаю с цинком
не может быть
объяснена
экономически).
Возможны также
различные
комбинации
изменений,
которые описывает
область устойчивости
(интервалы
устойчивости
являются
своеобразными
частными случаями
области устойчивости).
При данных
изменениях
ресурсов двойственные
оценки не изменятся,
а значит
и номера
базисных переменных
также не изменятся.
Изобразим
область устойчивости
двойственных
оценок к изменению
свободных
членов ограничений
графически.
Для этого, исходя
из экономических
соображений
и наглядности
графика, построим
его в координатах
и
,
т.е.
.
Получим:
Пример
практического
применения
интервалов
устойчивости.
Изменим
условие задачи
следующим
образом:
а) содержание
олова в новом
сплаве не должно
превосходить
15%;
Интервал
устойчивости
для олова – это
.
15% или 0,15 входят
в этот интервал,
следовательно
двойственные
оценки не изменятся
и оптимальное
решение будет
(при
).
.
По третьей
теореме двойственности
найдём значение
критерия при
этом решении:
=>
.
б) содержание
цинка должно
быть не менее
45%;
Интервал
устойчивости
для цинка -
.
Т.к. содержание
цинка в сплаве
должно быть
не более 42%, а т.к.
0,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 | |
Как видим,
оценки по-прежнему
удовлетворяют
критерию
оптимальности
и все базисные
переменные
неотрицательны,
значит, решение
допустимое
и оптимальное.
Новое решение
задачи
.
Оптимальное
значение критерия
.
Это означает,
что для производства
единицы сплава
необходимо
взять 25% второго
сырья и 75% третьего
сырья. При этом
доля цинка в
новом сплаве
будет ровно
45%, олова 22,5% и свинца
32,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 | |
Получим
следующее
решение:
,
.
Таким образом,
для изготовления
нового сплава
необходимо
взять 50%
сырья №2
и 50% сырья
№3.
Задача анализа
дополнительно
закупаемых
объёмов ресурсов
с целью обеспечения
наибольшей
эффективности
планирования.
Предположим,
что появилась
возможность
покупать сырьё
у других поставщиков
по более низкой
цене: цинк по
2 у.е., а за олово
и свинец, т.к.
согласно
экономическому
смыслу задачи
они являются
"антиблагами",
мы получаем
большую доплату
от их поставщика:
1,5 у.е. и 0,5 у.е. соответственно.
Руководитель
предприятия
выделил на
закупку ресурсов
3 у.е.
Решение:
По ранее
полученным
результатам
мы знаем, что
предприятие
тратит минимум
средств (5,28 у.е.)
когда в полученном
сплаве ровно
30% олова, 42% цинка
и 28% свинца (будем
считать для
удобства, что
для производства
10 тонн сплава
необходимо
3 тонны олова,
4,2 тонны цинка
и 2,8 тонн свинца).
Т.к. олово и свинец
мы получаем
с доплатой, то
возьмём их в
полном объёме,
необходимом
для производства
сплава. От "покупки"
олова мы получим
,
а от свинца –
,
т.е. всего 5,9 у.е.
(в связи с их
доходностью,
а не убыточностью
временно исключим
их из рассмотрения).
Будем вести
анализ закупок
цинка. На первой
итерации мы
не закупаем
цинк, т.к. в этом
случае он бы
приносил больше
убытка (двойственная
оценка равна
нулю по сравнению
с предлагаемой
ценой в 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 | |||
| Б.П. |
|
|
|
|
|
|
|
|
|
| В |
| 4,5 |
| 1,4 | 1 | 0 | 0 | 0 | 2 | 0 | 0 | -0,2 | 0 | 0,4 |
| 0 |
| 0,12 | 0 | 0 | 0,2 | 0,3 | 0,6 | 0 | 1 | -0,46 | 0 | 0,12 |
| 5,8 |
| -0,4 | 0 | 1 | 1 | 1 | -2 | 0 | 0 | 1,2 | 0 | 0,6 |
| 0 |
| 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 | |||
| Б.П. |
|
|
|
|
|
|
|
|
|
| В |
| 4,5 |
| 1,4 | 1 | 0 | 0 | 0 | 2 | 0 | 0 | -0,2 | 0 | 0,4 |
| 0 |
| 0,12 | 0 | 0 | 0,2 | 0,3 | 0,6 | 0 | 1 | -0,46 | 0 | 0,12 |
| 5,8 |
| -0,4 | 0 | 1 | 1 | 1 | -2 | 0 | 0 | 1,2 | 0 | 0,6 |
| 0 |
| 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 | |||
| Б.П. |
|
|
|
|
|
|
|
|
|
|
| В |
| 4,5 |
| 1,4 | 1 | 0 | 0 | 0 | 0,6’ | 2 | 0 | 0 | -0,2 | 0 | 0,4 |
| 0 |
| 0,12 | 0 | 0 | 0,2 | 0,3 | 1 | 0,6 | 0 | 1 | -0,46 | 0 | 0,12 |
| 5,8 |
| -0,4 | 0 | 1 | 1 | 1 | -2 | -2 | 0 | 0 | 1,2 | 0 | 0,6 |
| 0 |
| 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 | |||
| Б.П. |
|
|
|
|
|
|
|
|
|
|
| В |
| 3,5 |
| 2,333 | 1,666 | 0 | 0 | 0 | 1 | 3,333 | 0 | 0 | -0,333 | 0 | 0,666 |
| 0 |
| -0,066 | -0,133 | 0 | 0,2 | 0,3 | 0 | 0,333 | 0 | 1 | -0,433 | 0 | 0,066 |
| 5,8 |
| -1,33 | -0,666 | 1 | 1 | 1 | 0 | -3,33 | 0 | 0 | 1,333 | 0 | 0,333 |
| 0 |
| 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, пока не будут
перечеркнуты
все строки или
столбцы
В нашем случае
это выглядит
следующим
образом:
Пища Норы | окорок | мешок крупы | мешок муки | мешок картошки | журналы | |
| 5 2 0 | 18 0 | 17 2 0 | 22 0 | 8 0 | ||
| нора 1 | 15 0 | 15 | ||||
| нора 2 | 20 2 0 | 18 | 2 | |||
| нора 3 | 10 2 0 | 2 | 8 | |||
| нора 4 | 25 3 0 | 3 | 22 | |||
Римскими
цифрами пронумерован
порядок итераций.
I.
;
;
;
– 4 столбец
исключен.
II.
;
;
;
– 2 столбец
исключен.
III.
;
;
;
– 1 строка
исключена.
IV.
;
;
;
– 5 столбец
исключен.
V.
;
;
;
– 4 строка
исключена.
VI.
;
;
;
– 3 строка
и 1 столбец
исключены.
VII.
;
;
;
– 2 строка
и 3
столбец исключены.
Порассуждав
таким образом,
мыши получили
следующий
начальный
опорный план:
;
.
По этому
опорному плану
коту достанется
аж 13 мышей (0,18 часть
мыши отдельно
вряд ли выживет).
“Жирно
ему будет”-,
подумали
мыши и стали
составлять
другой опорный
план
методом
северо-западного
угла.
4. Метод северо-западного
угла.
Данный метод
очень прост,
пункты 1 и 2 в методе
максимальной
загрузки заменяются
на следующий:
очередная
загружаемая
коммуникация
выбирается
в левой верхней
клетке сохраненной
части таблицы,
т.е. в северо-западном
углу таблицы.
Математически
это выражается
следующим
образом:
,
I – множество
номеров пунктов
производства;
,
J – множество
номеров пунктов
потребления;
Последовательно
по итерациям
метода получаем:
I.
;
;
;
– 1 столбец
исключен.
II.
;
;
;
– 1 строка
исключена.
III.
;
;
;
– 2 столбец
исключен.
IV.
;
;
;
– 2 строка
исключена.
V.
;
;
;
– 3 столбец
исключен.
VI.
;
;
;
– 3 строка
исключена.
VII.
;
;
;
– 4 столбец
исключен.
VIII.
;
;
;
– 4 строка
и 5 столбец
исключены.
Пища Норы | окорок | мешок крупы | мешок муки | мешок картошки | журналы | |
| 5 0 | 18 8 0 | 17 5 0 | 22 17 0 | 8 0 | ||
| нора 1 | 15 10 0 | 5 | 10 | |||
| нора 2 | 20 12 0 | 8 | 12 | |||
| нора 3 | 10 5 0 | 5 | 5 | |||
| нора 4 | 25 8 0 | 17 | 8 | |||
Получили
следующий
опорный план:
.
.
Те же самые
13 мышей, и даже
хуже предыдущего
опорного плана
(если учитывать
сотые). Пришлось
мышам использовать
метод минимальных
затрат.
5. Метод
минимальных
затрат.
В этом методе
в первую очередь
загружаются
те коммуникации,
в которых затраты
на перевозку
минимальные.
В нашем случае,
это те пути,
мышиные потери
на которых
минимальны.
Пища Норы | окорок | мешок крупы | мешок муки | мешок картошки | журналы | |
| 5 0 | 18 0 | 17 0 | 22 20 18 15 0 | 8 0 | ||
| нора 1 | 15 0 | 15 | ||||
| нора 2 | 20 3 0 | 17 | 3 | |||
| нора 3 | 10 2 0 | 2 | 8 | |||
| нора 4 | 25 7 2 0 | 5 | 18 | 2 | ||
I.
;
;
;
– 2 столбец
исключен.
II.
;
;
;
– 1 столбец
исключен.
III.
;
;
;
– 4 строка
исключена.
IV.
;
;
;
– 5 столбец
исключен.
V.
;
;
;
– 3 строка
исключена.
VI.
;
;
;
– 3 столбец
исключен.
VII.
;
;
;
– 2 строка
исключена.
VIII.
;
;
;
– 1 строка
и 4 столбец
исключены.
Опорный план:
Целевая
функция:
Этот опорный
план понравился
мышам значительно
больше, но все
равно потери
достаточно
велики (7 мышей).
Теперь требовалось
решить эту
задачу и найти
оптимальный
план. И сделать
они это собрались
самым точным
методом – методом
потенциалов.
6. Решение задачи
методом потенциалов.
Если план
действительно
оптимален, то
система (1) будет
выполняться,
т.е.:
1) для каждой
занятой клетки
транспортной
таблицы сумма
потенциалов
должна быть
равна
для этой клетки;
2) для каждой
незанятой
клетки сумма
потенциалов
не больше (меньше
или равно)
.
Построим
для каждой
свободной
переменной
плана числа
и они должны
быть положительны.
Так как число
потенциалов
равно 9, а система
состоит из 8
уравнений, то
для нахождения
какого-либо
решения этой
системы необходимо
первому из
потенциалов
придать произвольное
значение (например:
).
Далее последовательно
находим значения
всех потенциалов.
Распишем подробно
эту процедуру.
Пища Норы | окорок | мешок крупы | мешок муки | мешок картошки | журналы | ||
| 5 | 18 | 17 | 22 | 8 | |||
| нора 1 | 15 | 15 | |||||
| нора 2 | 20 | 17 | 3 | ||||
| нора 3 | 10 | 2 | 8 | ||||
| нора 4 | 25 | 5 | 18 | 2 | |||
Таким образом,
после того, как
все потенциалы
найдены, можно
искать
:
Видно, что
и
меньше
нуля, значит
существующий
опорный план
можно улучшить.
Поскольку
,
нужно ввести
в базис вектор,
соответствующий
клетке (2; 1), для
чего загрузить
ее некоторым
количеством
единиц груза
(мышей). Но, так
как мы, увеличивая
загрузку (2; 1),
нарушаем баланс
строк и столбцов
распределительной
таблицы, то
следует изменить
объемы поставок
в ряде других
занятых клеток.
А чтобы число
базисных переменных
осталось прежним,
необходимо
вывести из
базиса одну
переменную.
Выводится
обычно та переменная,
у которой загрузка
в цикле минимальна.
Строим цикл:
(2; 1) – начальная
точка цикла;
Что характерно,
для этой точки
(впрочем как
и для других)
мы можем построить
только один
цикл. Каждой
клетке цикла
приписываем
определенный
знак:
(2; 1) – “+”, (4;
1) – “-”, (4; 4) – “+” (2; 4) –
“-”.
Пища Норы | окорок | мешок крупы | мешок муки | мешок картошки | журналы | |
| 5 | 18 | 17 | 22 | 8 | ||
| нора 1 | 15 | 15 | ||||
| нора 2 | 20 | 17 | 3 | |||
| нора 3 | 10 | 2 | 8 | |||
| нора 4 | 25 | 5 | 18 | 2 | ||
В клетках
с “+” – увеличиваем
загрузку, а в
клетках с “-”
– уменьшаем.
Величина, на
которую увеличиваем
или уменьшаем
всегда одна
и она определяется
из условия:
,
где
–
содержимое
клеток с “-”.
Таким образом
получаем:
,
а значит из
базиса будет
выведена (2;
4), где в процессе
реализации
цикла загрузка
уменьшится
до 0.
Перейдем
к новому опорному
плану
Пища Норы | окорок | мешок крупы | мешок муки | мешок картошки | журналы | ||
| 5 | 18 | 17 | 22 | 8 | |||
| нора 1 | 15 | 15 | |||||
| нора 2 | 20 | 3 | 17 | ||||
| нора 3 | 10 | 2 | 8 | ||||
| нора 4 | 25 | 2 | 18 | 5 | |||
Определяем
Все
больше 0, следовательно
план оптимальный.
.
Целевая
функция при
этом плане:
М-да, незначительное
улучшение для
мышей. Целых
6 мышей и еще
один мышиный
хвостик – такова
ежедневная
дань коту Василию.
Но делать нечего,
и стали мыши
действовать
по этому плану.
7. Открытая модель.
И все было
бы хорошо, но
в 3 норе появился
дополнительный
приплод – 10 мышей,
следовательно
в ней стало
проживать 20
мышей, а количество
мышей, питающихся
у источников
пищи, осталось
тем же. Получилась
так называемая
открытая модель,
где:
(3)
и
ее необходимо
сбалансировать.
Для этого нужно
ввести фиктивный
пункт потребления
с объемом
потребления:
;
и
дополнительные
переменные
приводящие
ограничение-неравенство
(3) к виду равенств
и понимание
как фиктивные
перевозки из
пунктов производства
в фиктивный
пункт потребления.
Новая математическая
модель:
;
;
При этом во
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 | 20 12 0 |
|
|
|
|
|
|
|
| нора 4 | 25 10 5 0 |
|
|
|
|
|
|
|
|
|
|
|
|
| |||
Определяем
.
меньше 0, поэтому
существующий
опорный план
можно улучшить.
Поскольку
–
наибольший,
то мы будем
вводить в базис
вектор, соответствующий
клетке (4; 4). Строим
цикл и
переходим к
новому опорному
плану.
Пища Норы | окорок | мешок крупы | мешок муки | мешок картошки | журналы | R | ||
| 5 | 18 | 17 | 22 | 8 | 10 | |||
| нора 1 | 15 |
|
|
|
|
|
|
|
| нора 2 | 20 |
|
|
|
|
|
|
|
| нора 3 | 20 |
|
|
|
|
|
|
|
| нора 4 | 25 |
|
|
|
|
|
|
|
|
|
|
|
|
| |||
Определяем
меньше 0, поэтому
существующий
опорный план
можно также
улучшить. Теперь
мы будем вводить
в базис вектор,
соответствующий
клетке (2; 1). Строим
цикл и
переходим к
новому опорному
плану.
Пища Норы | окорок | мешок крупы | мешок муки | мешок картошки | журналы | R | ||
| 5 | 18 | 17 | 22 | 8 | 10 | |||
| нора 1 | 15 |
|
|
|
|
|
|
|
| нора 2 | 20 |
|
|
|
|
|
|
|
| нора 3 | 20 |
|
|
|
|
|
|
|
| нора 4 | 25 |
|
|
|
|
|
|
|
|
|
|
|
|
| |||
Определяем
Все
больше 0, следовательно
план оптимальный.
.
Целевая
функция при
этом плане:
Этот план
чуть хуже
предыдущего,
к тому же 10 мышей
из первой норы
остаются голодными.
Во всяком случае
питаются раз
в три дня.
8. Запрещенные
перевозки.
Но кот Василий
тоже не дремал,
и, произведя
те же операции,
что и мыши в
свое время,
определил
оптимальный
план их передвижений
(см. пункт 6). Посмотрев
на него, он сразу
решил взять
под особый
контроль путь
от второй норы
к мешку муки
и от четвертой
норы к мешку
крупы.
Вскоре мыши
это на себе
почувствовали,
а почувствовав,
кинулись составлять
новый оптимальный
план, пометив
эти два маршрута
как чрезвычайно
опасные буквой
М
Пища Норы | окорок | мешок крупы | мешок муки | мешок картошки | журналы | ||
| 5 | 18 | 17 | 22 | 8 | |||
| Нора 1 | 15 | 15 | |||||
| Нора 2 | 20 | 2 | 18 | ||||
| Нора 3 | 10 | 2 | 8 | ||||
| Нора 4 | 25 | 3 | 17 | 5 | |||
Видно, что
этот план уже
является оптимальным.
Целевая
функция:
.
Как зыбко
мышиное счастье.
Стоило коту
взяться за дело
всерьез, и потери
возросли чуть
ли не в два раза.
10
Лабораторная
работа № 6
Телешовой
Елизаветы, гр.
726,
Решение
задачи о ранце
методом ветвей
и границ.
1. Постановка
задачи.
1929 год. В США
великая депрессия,
введен сухой
закон. Страна
просто задыхается
без спиртного.
В этот сложный
момент группа
инициативных
граждан под
руководством
Аль Капоне
решает помочь
родной стране.
Ими планируется
поставка алкогольной
продукции из
Ливерпуля в
Штаты. Благодарные
сограждане
из 5 крупных
городов США
готовы платить
большие деньги
за тонну спиртного:
2000 долл. в Бостоне,
3000 в Детройте,
2500 в Вашингтоне,
3200 в Нью-Йорке
и 1800 долл в Чикаго.
Все 5 городов
находятся на
разном расстоянии
от порта, куда
прибывает груз:
Бостон – 250 миль,
Детройт – 300 миль,
Вашингтон –
500 миль, Нью-Йорк
–100 миль и Чикаго
– 600 миль. Требуется
выбрать города,
в которых можно
получить максимальную
прибыль от
продажи спиртного.
При этом суммарное
расстояние
от этих портов
до порта с грузом
не должно превышать
1000 миль.
2. Решение задачи.
Данная задача
является задачей
о ранце вида:
, (1)
где критерием
является функция
,
(2)
которая может
быть устремлена
и к максимуму,
и к минимуму.
Для начала
составим следующую
математическую
модель:
Пусть
– j-тый город,
откуда соответственно
.
При этом, если
в j-тый город
будет разгружаться
алкогольная
продукция, то
,
иначе
.
Другим ограничением
будет являться
суммарное
расстояние
до порта с грузом.
Таким образом:
;
Целевой
функцией или
критерием будет
являться максимальная
благодарность
сограждан:
.
Далее
отбираем порты
по приоритетности,
т.е. в порядке
убывания отношения
:
(3);
(2);
(4);
(1);
(5).
После
этого определяем
начальный план
следующим
образом: пусть
,
поскольку
отношение
наибольшее,
и следовательно
продажа спиртного
в Нью-Йорке
даст наибольшую
прибыль при
наименьших
затратах, которые
зависят от
расстояния.
Вычитая из
суммарного
расстояния
расстояние
до порта мы
получим расстояние,
которое разделяется
между остальными
городами, т.е.:
,
;
Аналогично
рассуждая,
далее получаем:
,
;
,
;
В последнем
случае оставшееся
после других
городов расстояние
меньше 500 миль,
поэтому
будет дробным:
,
=>
.
Таким образом,
начальный
опорный план:
.
Значение
целевой функции:
.
Но
обязательно
целое. Поэтому
чтобы определить,
чему все же
равен
:
0 или 1 вычислим
следующие
значения:
;–
целая часть
критерия при
существующем
опорном плане.
;–
значение
критерия при
целочисленном
опорном плане,
т.е.
.
Множество
D, которому
принадлежит
имеет
,
.
Разделим его
на 2 подмножества,
такие что:
;
- здесь
.
-
здесь
.
1) Анализ
множества D1.
Поскольку
целевая функция
и ограничения
будут иметь
вид:
Строим новый
опорный план:
,
;
,
;
,
;
Т.к.
,
поэтому
будет дробным:
,
=>
.
Таким образом,
новый опорный
план:
.
;
,
при
.
2) Анализ
множества D2.
Поскольку
целевая функция
и ограничения
будут иметь
вид:
=>
.
Строим новый
опорный план:
,
;
,
;
Т.к.
,
поэтому
будет дробным:
,
=>
.
Таким образом,
новый опорный
план:
.
;
,
при
.
3) Отсев
неперспективного
подмножества.
.
Так как
и
больше Rec,
то оба подмножества
можно считать
перспективными,
но поскольку
,
то далее мы
будем исследовать
подмножество
D2.
Разделим его
на 2 подмножества,
такие что:
;
- здесь
.
-
здесь
.
4) Анализ
множества D3.
Поскольку
,
целевая функция
и ограничения
будут иметь
вид:
.
Строим новый
опорный план:
,
;
,
;
Т.к.
,
поэтому
будет дробным:
,
=>
.
Таким образом,
новый опорный
план:
.
;
,
при
.
5) Анализ
множества D4.
Поскольку
,
целевая функция
и ограничения
будут иметь
вид:
=>
.
Строим новый
опорный план:
,
;
Т.к.
,
поэтому
будет дробным:
,
=>
.
Таким образом,
новый опорный
план:
.
;
,
при
.
6) Отсев
неперспективного
подмножества.
.
Так как
и
больше Rec,
то оба подмножества
можно считать
перспективными,
но поскольку
,
то далее мы
будем исследовать
подмножество
D3.
Разделим его
на 2 подмножества,
такие что:
;
- здесь
.
-
здесь
.
7) Анализ
множества D5.
Поскольку
,
,
целевая функция
и ограничения
будут иметь
вид:
.
Строим новый
опорный план,
очевидно:
.
При
,
ограничение
выполняется
всегда.
;
,
при
.
8) Анализ
множества D6.
Поскольку
,
,
целевая функция
и ограничения
будут иметь
вид:
.
Ограничение
несовместное,
поскольку даже
при
оно не выполняется.
Следовательно
множество D6
не существует.
Таким образом,
оптимальным
планом данной
задачи будет:
,
то есть алкоголь
выгоднее всего
поставлять
в 3 города: Детройт,
Вашингтон и
Нью-Йорк. При
этом прибыль
составит 8700 долл.
3. Постановка
задачи о многомерном
ранце.
В
связи с тем,
что спиртное
стало хорошо
раскупаться,
Аль Капоне
решил увеличить
поставки. Но
чтобы мирно
спящее ФБР не
дай бог не
проснулось,
было решено
осуществлять
поставки через
три разных
порта на восточном
побережье. Цены
на спиртное
в пяти вышеуказанных
городах не
изменились,
расстояние
же от них (в милях)
до портов указано
в следующей
таблице:
| Бостон | Детройт | Вашингтон | Нью-Йорк | Чикаго | |
| Порт 1 | 250 | 300 | 500 | 100 | 600 |
| Порт 2 | 100 | 200 | 700 | 400 | 300 |
| Порт 3 | 500 | 400 | 300 | 550 | 150 |
Во всех трех
случаях суммарное
расстояние
от порта до
городов не
должно превышать
1000 миль. Требуется
решить тот же
самый вопрос:
в какие города
выгоднее поставлять
продукцию?
4. Решение задачи
о многомерном
ранце (вручную).
Задача
о многомерном
ранце имеет
следующую
математическую
модель:
, (3)
где критерием
является функция
,
(4)
От
задачи об одномерном
ранце она отличается
наличием нескольких
ограничений.
Таким образом,
математическая
модель:
Пусть
– j-тый город,
откуда соответственно
.
При этом, если
в j-тый город
будет разгружаться
алкогольная
продукция, то
,
иначе
.
;
Целевой
функцией или
критерием будет
являться максимальная
благодарность
сограждан:
.
Решим
задачу оценки
критерия для
каждого ограничения
в отдельности.
Пусть множество
относится
к первому
ограничению,
–
ко второму, а
–
к третьему.
1) Анализ
множества
.
(3);
(2);
(4);
(1);
(5).
Определяем
начальный план:
,
;
,
;
,
;
В последнем
случае оставшееся
после других
городов расстояние
меньше 500 миль,
поэтому
будет дробным:
,
=>
.
Таким образом,
начальный
опорный план:
.
;
2) Анализ
множества
.
(1);
(2);
(5);
(3);
(4).
Определяем
начальный план:
,
;
,
;
,
;
В последнем
случае оставшееся
после других
городов расстояние
также равно
300 миль, поэтому
будет целым:
,
=>
.
Таким образом,
опорный план:
.
;
3) Анализ
множества
.
(5);
(2);
(3);
(4);
(1).
Определяем
начальный план:
,
;
,
;
,
;
В последнем
случае оставшееся
после других
городов расстояние
меньше 550 миль,
поэтому
будет дробным:
,
=>
.
Таким образом,
опорный план:
.
;
4) Вычисление
верхней и нижней
границ.
Вычисляем
верхнюю границу:
;
– третье
ограничение
более жесткое,
далее будем
исследовать
опорный план
.
Определяем
опорные планы
для третьего
ограничения:
a)
,
;
,
;
В последнем
случае оставшееся
после других
городов расстояние
равно 50 миль,
поэтому
.
Таким образом
:
.
б)
,
;
,
;
В последнем
случае оставшееся
после других
городов расстояние
равно 100 миль,
поэтому
.
Таким образом
:
.
в)
В этом случае
.
Вычисляем
нижнюю границу:
;
;
;
.
5) Ветвление
множества D.
;
- здесь
.
-
здесь
.
6) Анализ
множества D1.
a)
Определяем
начальный план
для
:
,
;
,
;
В последнем
случае оставшееся
после других
городов расстояние
меньше 500 миль,
поэтому
будет дробным:
,
=>
.
Таким образом,
новый опорный
план:
.
;
б)
Определяем
начальный план
для
:
,
;
,
;
,
;
В последнем
случае оставшееся
после других
городов расстояние
меньше 700 миль,
поэтому
будет дробным:
,
=>
.
Таким образом,
новый опорный
план:
.
;
в)
Определяем
начальный план
для
:
,
;
,
;
,
;
В последнем
случае оставшееся
после других
городов расстояние
меньше 100
миль, поэтому
будет дробным:
,
=>
.
Таким образом,
новый опорный
план:
.
;
г)
Вычисление
верхней и нижней
границ.
Вычисляем
верхнюю границу:
;
– первое
ограничение
более жесткое.
Определяем
опорные планы
для первого
ограничения:
–
В этом случае
.
–
,
;
,
;
В последнем
случае оставшееся
после других
городов расстояние
равно 450 миль,
поэтому
.
Таким образом
:
.
–
,
;
,
;
В последнем
случае оставшееся
после других
городов расстояние
равно 100
миль, поэтому
.
Таким образом
:
.
Вычисляем
нижнюю границу:
Т.к.
,
то
;
;
.
7) Анализ
множества D2.
Поскольку
,
то:
.
=>
;
a)
Определяем
начальный план
для
:
,
;
,
;
В последнем
случае оставшееся
после других
городов расстояние
меньше 500 миль,
поэтому
будет дробным:
,
=>
.
Таким образом,
новый опорный
план:
.
;
б)
Определяем
начальный план
для
:
,
;
,
;
,
;
Таким образом,
новый опорный
план:
.
;
в)
Определяем
начальный план
для
:
,
;
В последнем
случае оставшееся
после других
городов расстояние
меньше 400
миль, поэтому
будет дробным:
,
=>
.
Таким образом,
новый опорный
план:
.
;
г)
Вычисление
верхней и нижней
границ.
Вычисляем
верхнюю границу:
;
– третье
ограничение
более жесткое.
Определяем
опорные планы
для третьего
ограничения:
–
,
;
В
последнем
случае оставшееся
после других
городов расстояние
равно 50 миль,
поэтому
.
Таким образом:
.
–
,
;
,
;
В последнем
случае оставшееся
после других
городов расстояние
равно 50 миль,
поэтому
.
Таким образом
:
.
– В этом случае
.
Вычисляем
нижнюю границу:
Т.к.
,
то
;
;
.
8) Отсев
неперспективного
подмножества.
.
Так как
и
больше Rec,
то оба подмножества
перспективные,
но поскольку
,
то далее мы
будем исследовать
,
как более
перспективное.
;
- здесь
.
-
здесь
.
9) Анализ
множества D3.
Поскольку
,
то:
a)
Определяем
начальный план
для
:
,
;
,
;
В последнем
случае оставшееся
после других
городов расстояние
меньше 600 миль,
поэтому
будет дробным:
,
=>
.
Таким образом,
новый опорный
план:
.
;
б)
Определяем
начальный план
для
:
,
;
,
;
В последнем
случае оставшееся
после других
городов расстояние
меньше 700 миль,
поэтому
будет дробным:
,
=>
.
Таким образом,
новый опорный
план:
.
;
в)
Определяем
начальный план
для
:
,
;
В последнем
случае оставшееся
после других
городов расстояние
меньше 350
миль, поэтому
будет дробным:
,
=>
.
Таким образом,
новый опорный
план:
.
;
г)
Вычисление
верхней и нижней
границ.
Вычисляем
верхнюю границу:
;
– третье
ограничение
более жесткое.
Определяем
опорные планы
для третьего
ограничения:
–
,
;
,
;
В последнем
случае оставшееся
после других
городов расстояние
равно 100 миль,
поэтому
.
Таким образом
:
.
–
,
;
,
;
В последнем
случае оставшееся
после других
городов расстояние
равно 300
миль, поэтому
.
Таким образом
:
.
–
В этом случае
.
Вычисляем
нижнюю границу:
;
Т.к.
,
то
;
.
10) Анализ
множества D4.
Поскольку
,
то:
.
=>
;
a)
Определяем
начальный план
для
:
,
;
В последнем
случае оставшееся
после других
городов расстояние
меньше 500 миль,
поэтому
будет дробным:
,
=>
.
Таким образом,
новый опорный
план:
.
;
б)
Определяем
начальный план
для
:
,
;
,
;
Таким образом,
новый опорный
план:
.
;
в)
Определяем
начальный план
для
:
В этом случае
оставшееся
после других
городов расстояние
меньше 150 миль,
поэтому
будет дробным:
,
=>
.
Таким образом,
новый опорный
план:
.
;
г)
Вычисление
верхней и нижней
границ.
Вычисляем
верхнюю границу:
;
– третье
ограничение
более жесткое.
Определяем
опорные планы
для третьего
ограничения:
Очевидно,
что поскольку
,
то
.
Вычисляем
нижнюю границу:
Т.к.
,
то
;
.
Так
как
и
больше Rec,
то оба подмножества
перспективные,
но поскольку
,
то подмножество
более перспективное,
следовательно
оптимальным
планом будет
.
То есть города,
удовлетворяющие
всем 3 условиям
и при этом дающие
максимальную
прибыль – Детройт
и Нью-Йорк.
11
Лабораторная
работа № 7
Телешовой
Елизаветы, гр.
726,
Решение
задачи коммивояжера
методом
ветвей
и границ.
1. Постановка
задачи.
Испекла бабка
колобок и поставила
его остывать
на окошко. И
решил колобок,
что пока он
остывает, он
вполне может
обежать лес,
посмотреть
на лесных жителей
и снова вернуться
к деду и бабке.
Сказано – сделано.
Спрыгнул колобок
из окошка и
покатился в
лес. Помогите
колобку найти
кратчайший
маршрут его
движения по
лесу, если расстояния
между норами
лесных жителей,
а также домом
деда и бабки
даны в таблице.
| Дед и бабка | Заяц | Волк | Медведь | Лиса | |
| Дед и бабка | 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 |
2. Математическая
модель задачи.
Для решения
задачи присвоим
каждому пункту
маршрута определенный
номер: дед и
бабка – 1, заяц
– 2, волк – 3, медведь
– 4 и лиса – 5.
Соответственно
общее количество
пунктов
.
Далее введем
альтернативных
переменных
,
принимающих
значение 0, если
переход из
i-того
пункта в j-тый
не входит
в маршрут и 1 в
противном
случае. Условия
прибытия в
каждый пункт
и выхода из
каждого пункта
только по одному
разу выражаются
равенствами
(1) и (2).
(1)
(2)
Для обеспечения
непрерывности
маршрута вводятся
дополнительно
n
переменных
и
дополнительных
ограничений
(3).
(3)
Суммарная
протяженность
маршрута F,
которую необходимо
минимизировать,
запишется в
следующем виде:
(4)
В нашем случае
эти условия
запишутся в
следующем виде:
(1);
(2);
(3)
(4)
3. Решение задачи
методом ветвей
и границ.
1) Анализ
множества D.
Найдем оценку
снизу Н.
Для этого определяем
матрицу минимальных
расстояний
по строкам (1
где расстояние
минимально
в строке).
=>
;
Аналогично
определяем
матрицу минимальных
расстояний
по столбцам.
=>
;
;
Выберем
начальный план:
.
Тогда верхняя
оценка:
.
Очевидно,
что
,
где
означает переход
из первого
пункта в j-тый.
Рассмотрим
эти подмножества
по порядку.
2
) Анализ подмножества
D12.
;
;
;
;
;
3
) Анализ
подмножества
D13.
;
;
;
;
4
) Анализ
подмножества
D14.
;
;
;
;
;
5
) Анализ
подмножества
D15.
;
;
;
;
;
6)
Отсев неперспективных
подмножеств.
;
Подмножества
D13 и D15
неперспективные.
Т.к.
,
но
,
то далее будем
рассматривать
подмножество
D14.
.
7
) Анализ
подмножества
D142.
;
;
;
;
;
8)
Анализ подмножества
D143.
;
;
;
;
9)
Анализ подмножества
D145.
;
;
;
;
;
10)
Отсев неперспективных
подмножеств.
;
Подмножество
D143
неперспективное.
Т.к.
,
но
,
то далее будем
рассматривать
подмножество
D145.
.
9
) Анализ
подмножества
D1452.
;
;
;
;
;
9
) Анализ
подмножества
D1453.
;
;
;
;
;
;
Оптимальное
решение:
.
.
Таким
образом, маршрут
колобка: дед
и бабка – медведь
– лиса – заяц
– волк – дед и
бабка.
4