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

  • Просмотров 4691
  • Скачиваний 570
  • Размер файла 994
    Кб

Лабораторная работа № 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,