Главная страница
Навигация по странице:

  • Поиск решения, Ограничения

  • Поиск решения

  • «Жадный» алгоритм. Шаг 1.

  • Шаг 3.

  • РГР Логистика. РГР_М_1_. Решение задач линейного программирования в пакетах Mathcad и ms excel


    Скачать 1.5 Mb.
    НазваниеРешение задач линейного программирования в пакетах Mathcad и ms excel
    АнкорРГР Логистика
    Дата01.05.2021
    Размер1.5 Mb.
    Формат файлаdoc
    Имя файлаРГР_М_1_.doc
    ТипРешение
    #200627
    страница5 из 7
    1   2   3   4   5   6   7

    Лабораторная работа 3. Решение задачи о рюкзаке приближенными и точными алгоритмами.



    Задача о рюкзаке и ее варианты широко используются для моделирования большого числа практических задач управления, таких как выбор проектов, распределение капитала, комбинаторные аукционы, расположение предметов в системах сборки по заказу и др. [3, 6, 7].

    Одним из частных случаев задачи о рюкзаке является одномерная булева задача о рюкзаке, которая может быть сформулирована следующим образом. Рассмотрим рюкзак с объемом равным b. Пусть существует n различных предметов. Предмет j занимает объем aj, при этом его ценность равна cj. Цель задачи состоит в максимизации выгоды от помещенных в рюкзак предметов. Таким образом, задача может быть сформулирована как задача булева линейного программирования в следующем виде:

    Если условие заменить условием , то получим задачу об одномерном целочисленном рюкзаке. В этом случае имеется nтипов предметов и требуется определить, сколько предметов каждого типа нужно поместить в рюкзак, чтобы они имели максимальную суммарную ценность.

    Для решения задачи о рюкзаке разработан целый ряд алгоритмов и методов: динамическое программирование [6], метод ветвей и границ [3], метод перебора L-классов [2] и другие.

    В случае небольших n одномерная задача о рюкзаке может быть также решена в табличном процессоре MS Excel. При этом исходные данные задачи записываются также, как и для задачи ЛП, но в окне Поиск решения, Ограничения необходимо указать, что переменные являются целыми, либо булевыми (рис. 10).


    Рис. 10. Диалоговое окно Поиск решения для задачи о рюкзаке.
    При больших n точное решение задачи может потребовать значительных затрат машинного времени. Поэтому актуальной является разработка приближенных алгоритмов. Самый известный приближенный алгоритм – это так называемый “жадный” алгоритм. Опишем этот алгоритм по шагам для булевого случая.

    «Жадный» алгоритм.
    Шаг 1. Упорядочить предметы по не возрастанию удельной полезности cj/ aj,

    т.е. так, чтобы выполнялось соотношение

    ,

    положить k:=1 и перейти на шаг 2.

    Шаг 2. Если akb, то положить xk:=1, b:=bak, иначе xk:= 0.

    Увеличить k на единицу и перейти на шаг 3.

    Шаг 3. Если k > n, то алгоритм завершает работу, иначе перейти на шаг 2.

    Варианты заданий. Решить задачу о рюкзаке в пакете MS Excel. Разработать алгоритм полного перебора и «жадный» алгоритм для задачи о рюкзаке [8]. Найти точное и приближенное решение задачи о рюкзаке, используя реализованные алгоритмы.


    1) 6x1+ 2x2+ 3x3+ 7x4 → max

    5x1+ 2x2+ 4x3+ 5x4 ≤ 14

    xi ≥ 0, xiє Z, i = 1,..,4.


    2) 2x1+ 4x2+ 4x3+ 3x4 → max

    2x1+5x2+ 3x3+4x4 ≤ 12

    xi ≥ 0, xiє Z, i = 1,..,4.



    3) 3x1+ 6x2+ 5x3+ x4 → max

    2x1+ 5x2+4x3+ x4 ≤ 15

    xi ≥ 0, xiє Z, i = 1,..,4.



    4) 2x1+ 2x2+ x3+3x4 → max

    2x1+ 3x2+ 2x3+ 3x4 ≤ 13

    xi ≥ 0, xiє Z, i = 1,..,4.


    5) 5x1+ x2+ x3+ 3x4 → max

    4x1+ 3x2+ x3 + 3x4 ≤ 13

    xi ≥ 0, xiє Z, i = 1,..,4.


    6) x1+ 5x2+ 2x3+ 3x4 → max

    2x1+ 4x2+ 5x3+ 3x4 ≤ 14

    xi ≥ 0, xiє Z, i = 1,..,4.



    7) 5x1+ 7x2+ 6x3+ 3x4 → max

    4x1+ 5x2+ 8x3+ 3x4 ≤ 14

    xi ≥ 0, xiє Z, i = 1,..,4.



    8) x1+ 7x2+ 3x3+ 4x4 → max

    x1+ 5x2+ 2x3+ 3x4 ≤ 13

    xi ≥ 0, xiє Z, i = 1,..,4.


    9) x1+ 7x2+ 7x3+ 4x4 → max

    2x1+ 6x2+ 4x3+ 3x4 ≤ 15

    xi ≥ 0, xiє Z, i = 1,..,4.



    10) 3x1+ 5x2+ 2x3+ 8x4 → max

    2x1+ 4x2+ x3+ 6x4 ≤ 15

    xi ≥ 0, xiє Z, i = 1,..,4.


    11) x1+ 5x2+ 6x3+ 3x4 → max

    2x1+ 4x2+ 5x3 + 3x4 ≤ 15

    xi ≥ 0, xiє Z, i = 1,..,4.



    12) 4x1+ 5x2+ 2x3+4x4 → max

    2x1+2x2+ x3+ 3x4 ≤ 13

    xi ≥ 0, xiє Z, i = 1,..,4.


    13) 3x1+ 7x2+ 7x3+ 5x4 → max

    4x1+ 7x2+ 5x3+ 6x4 ≤ 13

    xi ≥ 0, xiє Z, i = 1,..,4.



    14) 2x1+ 4x2+ 5x3+ 6x4 → max

    2x1+ 3x2+ 4x3+ 5x4 ≤ 14

    xi ≥ 0, xiє Z, i = 1,..,4.



    15) 5x1+ 6x2+ 3x3+ 4x4 → max

    4x1+ 7x2+ 3x3+ 5x4 ≤ 18

    xi ≥ 0, xiє Z, i = 1,..,4.


    16) 5x1+ 6x2+ 9x3+ 4x4 → max
    4x1+ 5x2+ 8x3+ 3x4 ≤ 14

    xi ≥ 0, xiє Z, i = 1,..,4.


    17) x1+ 7x2+ 3x3+ 8x4 → max

    x1+ 4x2+ 2x3+ 5x4 ≤ 14

    xi ≥ 0, xiє Z, i = 1,..,4.


    18) 9x1+ x2+ 2x3+5x4 → max

    8x1+ x2+3x3+4x4 ≤ 15

    xi ≥ 0, xiє Z, i = 1,..,4.


    19) 2x1+ 3x2+ 6 x3+9x4 → max

    4x1+ 7x2+ 8x3+10x4 ≤ 20

    xi ≥ 0, xiє Z, i = 1,..,4.



    20) x1+ 8x2+ 9x3+7x4 → max

    x1+ 5x2+ 8x3+ 6x4 ≤ 14

    xi ≥ 0, xiє Z, i = 1,..,4.



    21) 2x1+ 3x2+ 3x3+ 4x4 → max

    4x1+ 4x2+ 5x3+ 5x4 ≤ 19

    xi ≥ 0, xiє Z, i = 1,..,4.


    22) 4x1+ 3x2+ 7x3+ x4 → max
    4x1+ 5x2+ 8x3+ 2x4 ≤ 14

    xi ≥ 0, xiє Z, i = 1,..,4.


    23) x1+ 4x2+ 3x3+ 9x4 → max

    x1+ 3x2+ 2x3+ 5x4 ≤ 17

    xi ≥ 0, xiє Z, i = 1,..,4.


    24) 7x1+ x2+ 3x3+2x4 → max

    6x1+ x2+2x3+3x4 ≤ 20

    xi ≥ 0, xiє Z, i = 1,..,4.


    25) 2x1+ 3x2+ 6 x3+9x4 → max

    4x1+ 7x2+ 8x3+10x4 ≤ 20

    xi ≥ 0, xiє Z, i = 1,..,4.



    26) x1+ 6x2+ 7x3+4x4 → max

    x1+ 5x2+ 4x3+ 3x4 ≤ 19

    xi ≥ 0, xiє Z, i = 1,..,4.



    27) 2x1+ 5x2+ 3x3+ 7x4 → max

    x1+ 3x2+ 2x3+ 5x4 ≤ 27

    xi ≥ 0, xiє Z, i = 1,..,4.


    28) 5x1+ x2+ 3x3+7x4 → max

    4x1+ x2+2x3+3x4 ≤ 26

    xi ≥ 0, xiє Z, i = 1,..,4.


    29) 2x1+ 3x2+ 6 x3+7x4 → max

    3x1+ 7x2+ 8x3+ 9x4 ≤ 25

    xi ≥ 0, xiє Z, i = 1,..,4.



    30) x1+ 6x2+ 4x3+4x4 → max

    x1+ 5x2+ 4x3+ 3x4 ≤ 29

    xi ≥ 0, xiє Z, i = 1,..,4.





    1   2   3   4   5   6   7


    написать администратору сайта