Применение методов линейного программирования
Автор: ksuuu212 • Октябрь 5, 2022 • Лабораторная работа • 611 Слов (3 Страниц) • 315 Просмотры
ВВЕДЕНИЕ
Целью практической работы является нахождение оптимального решения задачи линейного программирования. Для выполнения работы использовалась программа GNU Octave.
1. Задача о покрытии
Условие задачи
В районе города, схема которого изображена на рисунке 1, рассматривается возможность размещения пожарных участков (возможные точки размещения обозначены номерами, линии соответствуют дорогам, а закрашенные эллипсы - природным объектам). Стоимость размещения участка в каждой из точек указана в табл. 1).
Требуется найти такое размещение участков, при котором стоимость была бы минимальна, но (манхеттенское) расстояние от каждого перекрестка до ближайшего участка было не более 3.
[pic 1]
Рисунок 1 - Схема города
Таблица 1 - Стоимость размещения участка
Расположение | Стоимость, д.е. |
1 | 150 |
2 | 150 |
3 | 350 |
4 | 200 |
5 | 100 |
Формализация задачи
Нам дана задача, которая относится к линейному программированию, а если быть точнее, то это «Задача о покрытии».
Функция цели должна стремиться к минимуму, так как необходимо свести затраты к наименьшему значению:
F = 150 x1 + 150 x2 + 350 x3 + 200 x4 + 100 x5 min
Где xi - переменные, принимающие значение только либо 0, либо 1, другими словами булевы переменные. Соответсвенно, если участок размещен, то значение 1, в противном случае 0.
Для того, чтобы обозначить ограничения на схеме города пронумеруем перекрестки (см. рисунок 2).
[pic 2]
Рисунок 2 - Пронумерованные перекрестки
Теперь рассмотрим все ограничения, всего их будет 15, так как мы имеем
15 перекрёстков:
1) 1x1 + 1x2 + 1x3 + 0 x4 + 0 x5 >= 1
2) 1x1 + 1x2 + 1x3 + 1 x4 + 0 x5 >= 1
3) 0x1 + 1x2 + 1x3 + 1 x4 + 0 x5 >= 1
4) 0x1 + 1x2 + 1x3 + 1 x4 + 1 x5 >= 1
5) 1x1 + 1x2 + 1x3 + 1 x4 + 0 x5 >= 1
6) 1x1 + 1x2 + 1x3 + 1 x4 + 0 x5 >= 1
...