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

  • Решение

  • Рис. 8.9.

  • Рис. 8.10.

  • Пункт отправления

  • Таблица 8.8

  • Город отправления

  • Решение. Построим область допустимых решений Построим целевую функцию


    Скачать 271.12 Kb.
    НазваниеРешение. Построим область допустимых решений Построим целевую функцию
    Дата11.10.2021
    Размер271.12 Kb.
    Формат файлаdocx
    Имя файла9090.docx
    ТипРешение
    #245308

    Задания

    1. Изобразите на плоскости ограничения задачи линейного программирования и решите (графически) эту задачу:

    400W1 + 450W2 min

    5W1 + 10W2 45

    20W1 + 15W2 80

    W1 0, W2 0
    Решение.
    Построим область допустимых решений



    Построим целевую функцию



    Точка минимума:

    5W1 + 10W2 = 45

    20W1 + 15W2 = 80

    Отсюда

    W1 + 2W2 = 9

    4W1 + 3W2 = 16


    W1 =1;W2 = 4

    Минимальное значение функции

    400W1 + 450W2 = 400*1+450*4=2200



    2. Решите задачу линейного программирования:

    W1 + 5W2 max

    0,1W1 + W2 3,8

    0,25W1 + 0,25W2 4,2

    W1 0, W2 0
    Решение.
    Данную задачу можно решать различными методами, так как переменных две, то наиболее простой вариант –используя графический метод.



    Нанесем целевую функцию



    Максимальное значение в точке пересечения

    0,1W1 + W2 = 3,8

    0,25W1 + 0,25W2 = 4,2


    W1 =14,44;W2 = 2,36

    Максимальное значение функции

    W1 + 5W2 =14,44+5*2,36=26,24


    3. Решите задачу целочисленного программирования:

    10X + 5Y max

    8X + 3Y 40

    3X +10Y 30

    X 0, Y 0

    X и Y - целые числа
    Решение.

    Решим задачу графически.



    Нанесем целевую функцию



    Получим решение

    8X + 3Y = 40

    3X +10Y = 30

    Решение получили не целочисленное, параллельным переносом найдем целочисленное решение.



    Получим целочисленное решение

    4. Решите задачу о ранце:

    X1 + X2 + 2X3 + 2X4 + X5 + X6 max

    0,5X1 + X2 + 1,5X3 + 2X4 + 2,5X5 + 3X6 3

    Управляющие параметры Xk, k=1,2,3,4,5,6, принимают значения из множества, содержащего два элемента - 0 и 1.
    Решение.
    Условная оптимизация.

    f6(L) = max(1x6); 0 < x6 < 1; x6 = 0,1.

    f6(0) = max[0*1] = 0

    f6(1) = max[0*1] = 0

    f6(2) = max[0*1] = 0

    f6(3) = max[0*1, 1*1] = 1

    Таблица 1 – Расчет значения функции f1(L)

    L

    0

    1

    2

    3

    f6(L)

    0

    0

    0

    1

    x6

    0

    0

    0

    1


    f
    5(L) = max[1x5 + f6(L - 2.5x5)]; 0 < x5 < 1; x5 = 0,1.

    f5(0) = max[0*1+0] = 0

    f5(1) = max[0*1+0] = 0

    f5(2) = max[0*1+0] = 0

    f5(3) = max[0*1+1, 1*1+0] = 1

    Таблица 2 – Расчет значения функции f2(L)

    L

    0

    1

    2

    3

    f5(L)

    0

    0

    0

    1

    x5

    0

    0

    0

    0


    f
    4(L) = max[2x4 + f5(L - 2x4)]; 0 < x4 < 1; x4 = 0,1.

    f4(0) = max[0*2+0] = 0

    f4(1) = max[0*2+0] = 0

    f4(2) = max[0*2+0, 1*2+0] = 2

    f4(3) = max[0*2+1, 1*2+0] = 2

    Таблица 3 – Расчет значения функции f3(L)

    L

    0

    1

    2

    3

    f4(L)

    0

    0

    2

    2

    x4

    0

    0

    1

    1


    f
    3(L) = max[2x3 + f4(L - 1.5x3)]; 0 < x3 < 1; x3 = 0,1.

    f3(0) = max[0*2+0] = 0

    f3(1) = max[0*2+0] = 0

    f3(2) = max[0*2+2, 1*2+0] = 2

    f3(3) = max[0*2+2, 1*2+0] = 2

    Таблица 4 – Расчет значения функции f4(L)

    L

    0

    1

    2

    3

    f3(L)

    0

    0

    2

    2

    x3

    0

    0

    0

    0


    f
    2(L) = max[1x2 + f3(L - 1x2)]; 0 < x2 < 1; x2 = 0,1.

    f2(0) = max[0*1+0] = 0

    f2(1) = max[0*1+0, 1*1+0] = 1

    f2(2) = max[0*1+2, 1*1+0] = 2

    f2(3) = max[0*1+2, 1*1+2] = 3

    Таблица 5 – Расчет значения функции f5(L)

    L

    0

    1

    2

    3

    f2(L)

    0

    1

    2

    3

    x2

    0

    1

    0

    1


    f
    1(L) = max[1x1 + f2(L - 0.5x1)]; 0 < x1 < 1; x1 = 0,1.

    f1(0) = max[0*1+0] = 0

    f1(1) = max[0*1+1, 1*1+0] = 1

    f1(2) = max[0*1+2, 1*1+1] = 2

    f1(3) = max[0*1+3, 1*1+2] = 3

    Таблица 6 – Расчет значения функции f6(L)

    L

    0

    1

    2

    3

    f1(L)

    0

    1

    2

    3

    x1

    0

    0

    0

    0


    Безусловная оптимизация.


    Таким образом, максимальный вес рюкзака f1(3) равна 3 кг.

    При этом x1 = 0, так как f1(3) = 3 достигается при х1=0 (см. таблицу 6).

    Предметы остальных типов распределяются следующим образом:

    L = 3 - 0.5 * 0 = 3

    f2(3) = 3 достигается при х2 = 1 (см. таблицу 5).

    L = 3 - 1 * 1 = 2

    f3(2) = 2 достигается при х3 = 0 (см. таблицу 4).

    L = 2 - 1.5 * 0 = 2

    f4(2) = 2 достигается при х4 = 1 (см. таблицу 3).

    L = 2 - 2 * 1 = 0

    f5(0) = 0 достигается при х5 = 0 (см. таблицу 2).

    L = 0 - 2.5 * 0 = 0

    f6(0) = 0 достигается при х6 = 0 (см. таблицу 1).

    L = 0 - 3 * 0 = 0

    В итоге наилучший вариант загрузки рюкзака достигается при значениях: x1 = 0, x2 = 1, x3 = 0, x4 = 1, x5 = 0, x6 = 0



    5. Транспортная сеть (с указанием расстояний) приведена на рис. 8.9. Найдите кратчайший путь из пункта 1 в пункт 4.




    Рис. 8.9. Исходные данные к задаче о кратчайшем пути
    Решение.

    Проанализируем возможные варианты

    (1 – 2) = 5

    (1 – 3) = 0

    (1 – 3) + (1 – 4) = 0

    Кратчайший путь – 0.

    6. Как послать максимальное количество грузов из начального пункта 1 в конечный пункт 8, если пропускная способность путей между пунктами транспортной сети (рис. 8.10) ограничена (табл. 8.7)?




    Рис. 8.10. Транспортная сеть к задаче о максимальном потоке
    Таблица 8.7

    Исходные данные к задаче о максимальном потоке

    Пункт
    отправления


    Пункт
    назначения


    Пропускная
    способность


    1

    2

    1

    1

    3

    2

    1

    4

    3

    2

    5

    2

    3

    2

    2

    3

    4

    2

    3

    6

    1

    4

    7

    4

    5

    8

    3

    6

    5

    2

    6

    7

    1

    6

    8

    1

    7

    8

    3


    Решение.
    Максимальная пропускная способность составит 1+2+3 = 6 единиц, так как из первого пункта возможно отправить только 6 единиц.

    Далее из пункта 4 все грузы (3) могут быть отправлены в пункт 7. Из пункта 3 один груз отправляем в пункт 6 и далее в пункт 8.

    Один груз из пункта 3 в пункт 4, оттуда в пункт 7.

    И остается один груз – из пункта 2 в пункт 5 и далее в пункт 8.

    Грузы, собранные в пункте 7 – 4 штуки – отправляем в пункт 8.
    Итак, максимальная пропускная способность рассматриваемой транспортной системы - 6 единиц груза. При этом не используются внутренние участки (ветки) между пунктами 3 и 2, 6 и 7. Большая часть веток не догружена.


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

    Исходные данные к задаче коммивояжера

    Город отправления

    Город назначения

    Затраты на проезд

    А

    Б

    2

    А

    В

    1

    А

    Д

    5

    Б

    А

    3

    Б

    В

    2

    Б

    Д

    1

    В

    А

    4

    В

    Б

    1

    В

    Д

    2

    Д

    Ф

    5

    Д

    Б

    3

    Д

    В

    3

    Решение.

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

    В вершину Ф входит только один путь из вершины Д.

    То есть кратчайший пусть С(Д) + 5.

    Найдем кратчайший путь в вершину Д.

    Возможные варианты

    С(Д)=min (С(А) + 5; С(Б) + 1; С(В) + 2)

    Проанализируем пути

    С(А) = min (C(Б) + 3; С(В) + 4)

    С(Б) = min (С(А) + 2; С(В) + 1)

    С(В) = min (C(A) + 1; C(Б) + 2)

    Итак, путь

    А – В – Б – Д – Ф

    Длина пути составит 1+1+1+1+5=9


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