Рефераты по теме Теория систем управления

Реферат Лабораторная работа №6 по "Основам теории систем" (Решение задачи о ранце методом ветвей и границ) скачать бесплатно

Текст реферата Лабораторная работа №6 по "Основам теории систем" (Решение задачи о ранце методом ветвей и границ)

Лабораторная работа № 6

Телешовой Елизаветы, гр. 726,

Решение задачи о ранце методом ветвей и границ.

1. Постановка задачи.

1929 год. В США великая депрессия, введен сухой закон. Страна просто задыхается без спиртного. В этот сложный момент группа инициативных граждан под руководством Аль Капоне решает помочь родной стране. Ими планируется поставка алкогольной продукции из Ливерпуля в Штаты. Благодарные сограждане из 5 крупных городов США готовы платить большие деньги за тонну спиртного: 2000 долл. в Бостоне, 3000 в Детройте, 2500 в Вашингтоне, 3200 в Нью-Йорке и 1800 долл в Чикаго. Все 5 городов находятся на разном расстоянии от порта, куда прибывает груз: Бостон – 250 миль, Детройт – 300 миль, Вашингтон – 500 миль, Нью-Йорк –100 миль и Чикаго – 600 миль. Требуется выбрать города, в которых можно получить максимальную прибыль от продажи спиртного. При этом суммарное расстояние от этих портов до порта с грузом не должно превышать 1000 миль.

2. Решение задачи.

Данная задача является задачей о ранце вида: , (1) где критерием является функция (2) которая может быть устремлена и к максимуму, и к минимуму. Для начала составим следующую математическую модель: Пусть – j-тый город, откуда соответственно j-тый город будет разгружаться алкогольная продукция, то
;
Целевой функцией или критерием будет являться максимальная благодарность сограждан:
Далее отбираем порты по приоритетности, т.е. в порядке убывания отношения
(3); (2); ; (1); (5).
После этого определяем начальный план следующим образом: пусть наибольшее, и следовательно продажа спиртного в Нью-Йорке даст наибольшую прибыль при наименьших затратах, которые зависят от расстояния. Вычитая из суммарного расстояния расстояние до порта мы получим расстояние, которое разделяется между остальными городами, т.е.: ,
Аналогично рассуждая, далее получаем: ,
,
В последнем случае оставшееся после других городов расстояние меньше 500 миль, поэтому будет дробным:
Таким образом, начальный опорный план:
Значение целевой функции:
Но обязательно целое. Поэтому чтобы определить, чему все же равен
;– целая часть критерия при существующем опорном плане. ;– значение критерия при целочисленном опорном плане, т.е.
Множество D, которому принадлежит имеет Разделим его на 2 подмножества, такие что:
;
- здесь
здесь
1) Анализ множества D1.
Поскольку целевая функция и ограничения будут иметь вид:

Строим новый опорный план: ,
,
,
Т.к. будет дробным:
Таким образом, новый опорный план:
;
, при
2) Анализ множества D2.
Поскольку целевая функция и ограничения будут иметь вид:
=> .
Строим новый опорный план: ,
,
Т.к. будет дробным:
Таким

Страницы: 0 1 2 3 4 5