Главная | Обратная связь | Поможем написать вашу работу!
МегаЛекции

Многокритериальная многомерная задача о ранце




D – мерная задача о ранце с n предметами и m аддитивными критериями:

(9)

(10)

(11)

0≤aij≤bi Задачу (9)-(11) обозначим символом Z.

Для получения полной совокупности эффективных в рассматриваемой задаче оценок E(Z) рассмотрим совокупность задач Z(K,p):

(12)

(13)

(14)

, где k ∈{1,2,...,n}, p ∈P; здесь и далее P - множество всех целочисленных векторов

(p 1 ,p2 ,…, pd)- с координатами, удовлетворяющими условиям 0 ≤ pi ≤ bi, .

Полную совокупность эффективных оценок в задаче Z(k, p) обозначим

E(k, p). При этом E(Z) =E(n, b), здесь b= (b1,b2,…,bd).

(0,0,…,0) если ∃ i: 0≤pi<ail;

Е(1, р)=.

(c11,c21,…,cm1) при ail≤pi для всех

Условимся далее обозначать через Сj и aj векторы (с1j2j,…, сmj) и (a1j,a2j,…, adj).

Пусть уже найдены значения E(k, p) для некоторого k и всех возможных p

из P. Тогда значения E(k +1, p) вычисляются по формуле

Е(k, р), если ∃ i: 0≤pi<aik+1;

Е(k+1, р)= eff (Е(k, р)∪{Ck+1)⊕E(k, p -ak+1)})

. при аik+1≤pi для всех

 

здесь k = 1,2,...,n −1; p ∈ P.

Действительно, задача Z(k+1, p) отличается от Z(k, p) дополнительным

наличием булевозначной переменной хk+1. В случае ∃ i: 0≤pi<aik+1 имеем

E(k+1, p) =E(k, p), так как допустимым оказывается только нулевое значение данной переменной.

Если же для всех имеет место аik+1≤pi, то для переменной хk+1 следует

рассмотреть две возможности: хk+1= 0 и хk+1= 1.

Решение задачи Z сводится к последовательному заполнению строк таблицы. Заголовками строк являются допустимые значения первого аргумента функции E(k, p) r, т.е. натуральные числа от 1 до n. Заголовками столбцов являются допустимые значения второго аргумента. Указанные векторы перечисляются как заголовки столбцов в лексикографическом порядке. В каждую клетку (k, p) таблицы вносится множество векторов E(k, p). Процесс решения задачи Z заканчивается нахождением множества E(Z) =E(n, b)

 

Постановка многокритериальной задачи

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

Найдя оптимальное решение для поставленной задачи, определим, какие товары выгоднее погрузить, с целью максимальной выгоды от пордажи товара в минимальные сроки..

12+2х3+5х4+4х5àmax - прибыль от товара

х1+3х2+3х34+5х5àmax - степень спроса у потребителя

123+4х4+3х5 10 - вес товара и максимальная грузоподъемность

xi {0.1}, i= судна

                     
    (3,1)1 (3,1)1 (3,1)1 (3,1)1 (3,1)1 (3,1)1 (3,1)1 (3,1)1 (3,1)1
  (1,3)2 (3,1)1 (1,3)2 (4,4)1,2 (4,4)1,2 (4,4)1,2 (4,4)1,2 (4,4)1,2 (4,4)1,2 (4,4)1,2 (4,4)1,2
  (2,3)3 (3,6)2,3 (5,4)1,3 (3,6)2,3 (6,7)1,2,3 (6,7)1,2,3 (6,7)1,2,3 (6,7)1,2,3 (6,7)1,2,3 (6,7)1,2,3 (6,7)1,2,3
  (2,3)3 (3,6)2,3 (5,4)1,3 (3,6)2,3 (6,7)1,2,3 (6,7)1,2,3 (7,4) 3,4 (8,7)2,3,4 (10,5)1,3,4 (8,7)2,3,4 (11,8)1,2,3,4 (11,8)1,2,3,4 (11,8)1,2,3,4
  (2,3)3 (3,6)2,3 (5,4)1,3 (3,6)2,3 (4,5)5 (6,8)3,5 (7,11)1,3,5 (9,9)1,3,5 (7,11)1,3,5 (10,12)1,2,3,5 (10,12)1,2,3,5 (11,9)3,4,5 (12,12)2,3,4,5 (14,10)1,3,4,5 (12,12)2,3,4,5

 

Построена таблица включающая в себя полную совокупность эффективных оценок Е. В итоге мы получили две самых эффективных оценки (14,10) и (12,12). ЛПР необходимо выбрать одну из них. Руководствуясь соображениями, что все – таки прибыль нам несколько важнее, чем быстрый сбыт товара, ЛПР выбирает оценку (14,10).

Поскольку Кopt=(14,10), то Парето- оптимальное решение выглядит: х1345=1 , х2=0;

Следовательно погружены все предметы кроме второго с учетом их стоимости и приоритету у потребителей. И от их продажи товаров мы получим прибыль 14тыс.у.е.

 

Заключение

Мы ознакомились с принципами постановки и методами решения задач дискретной оптимизации, возникающих в процессах управления и принятия решений в системах управления.

В курсовой работе в качестве основной задачи дискретной оптимизации рассмотрены задачи о ранце на примере задачи о водных грузоперевозках.

Приведены в качестве иллюстрированного примера алгоритмы решения однокритериальной и многокритериальной задачи о ранце.

Дополнительно описываются различные методы решения многокритериальных задач, базирующихся на концепции эффективной оценки и Парето-оптимального решения, и так же рассмотрен подход, использующий схемы компромисса.

 

Список литературы

1. Д.И.Коган Методы оптимизации. Типовые алгоритмы решения задач дискретной оптимизации. Учебное пособие. Москва, МГУПИ, 2009

2. Д.И.Коган Многокритериальные задачи принятия решений в системах управления. Москва, МГУПИ, 2008

3. Д.И. Коган Лекции по предмету “теория систем”

4. http://xreferat.ru/33/6244-1-metody-resheniya-zadachi-o-ryukzake.html

5. http://www.dissercat.com/content/mnogokriterialnye-zadachi-rantsevogo-tipa-matematicheskie-modeli-i-algoritmy-resheniya

6. http://andreyusoft.narod.ru/uchebnik1/part2p3.html

 

 

Поделиться:





Воспользуйтесь поиском по сайту:



©2015 - 2024 megalektsii.ru Все авторские права принадлежат авторам лекционных материалов. Обратная связь с нами...