Essays.club - Получите бесплатные рефераты, курсовые работы и научные статьи
Поиск

Применение методов линейного программирования

Автор:   •  Октябрь 5, 2022  •  Лабораторная работа  •  611 Слов (3 Страниц)  •  301 Просмотры

Страница 1 из 3

ВВЕДЕНИЕ

Целью практической работы является нахождение оптимального решения задачи линейного программирования. Для выполнения работы использовалась программа GNU Octave.

1. Задача о покрытии

  1. Условие задачи

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

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

[pic 1]

Рисунок 1 - Схема города

Таблица 1 - Стоимость размещения участка

Расположение

Стоимость, д.е.

1

150

2

150

3

350

4

200

5

100

  1. Формализация задачи

Нам дана задача, которая относится к линейному программированию, а если быть точнее, то это «Задача о покрытии».

Функция цели должна стремиться к минимуму, так как необходимо свести затраты к наименьшему значению:

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

...

Скачать:   txt (5.5 Kb)   pdf (123 Kb)   docx (52.3 Kb)  
Продолжить читать еще 2 страниц(ы) »
Доступно только на Essays.club