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


    		•

    вариант 2 07.04.21. Задание 1 2 Задание 2 9


    Скачать 195.66 Kb.
    НазваниеЗадание 1 2 Задание 2 9
    Дата25.11.2022
    Размер195.66 Kb.
    Формат файлаdocx
    Имя файлавариант 2 07.04.21.docx
    ТипДокументы
    #812538

    Содержание


    Задание № 1 2

    Задание № 2 9

    Задание № 3 12

    Задание № 4 17

    Список использованных источников 21


    Задание № 1



    Условие:

    Составить математическую модель задачи своего варианта и решить графическим методом и симплекс-методом (MS Excel)
    На четырех станках обрабатываются два вида деталей: А и В, причем каждая деталь проходит обработку на всех станках. Время обработки деталей на каждом станке, время работы станков в течение одного цикла производства и прибыль, получаемая от выпуска одной детали каждого вида приведены в таблице 1.
    Таблица 1 – Исходные данные

    Типы станков
    Время обработки, мин
    Время работы

    станка в течение

    одного цикла, мин

    Деталь А
    Деталь В

    № 1
    2
    3
    24

    № 2
    5
    4
    20

    № 3
    4
    8
    32

    № 4
    3
    3
    36

    Прибыль, у.е.
    3
    5
    –


    Определить программу, приносящую наибольшую прибыль.
    Решение:

    Составим математическую модель данной задачи. Поскольку необходимо определить максимальный доход от реализации всех деталей А и В, то переменные вводим следующим образом: х1 - деталь вида А; х2 - деталь вида В.

    Тогда прибыль составит 3х1+5х2

    При решении рассматриваемой задачи должны быть учтены ограничения по времени на производство деталей.

    Так как для производства детали вида А расходуется 2 мин, а для производство детали вида В расходуется 3 мин, то для изготовления первым станком деталей А и В не должно превышать 24 мин.

    Так как для производства детали вида А расходуется 5 мин, а для производство детали вида В расходуется 4 мин, то для изготовления вторым станком деталей А и В не должно превышать 20 мин.

    Так как для производства детали вида А расходуется 4 мин, а для производство детали вида В расходуется 8 мин, то для изготовления третьим станком деталей А и В не должно превышать 32 мин.

    Так как для производства детали вида А расходуется 3 мин, а для производство детали вида В расходуется 3 мин, то для изготовления четвертым станком деталей А и В не должно превышать 36 мин.

    Математическая модель поставленной задачи имеет следующий вид [2, c. 315]:



    Решим данную задачу графическим способом.

    Построим уравнение 2x1+3x2 = 24 по двум точкам. Для нахождения первой точки приравниваем x1 = 0. Находим x2 = 8. Для нахождения второй точки приравниваем x2 = 0. Находим x1 = 12. Соединяем точку (0;8) с (12;0) прямой линией.

    Построим уравнение 5x1+4x2 = 20 по двум точкам. Для нахождения первой точки приравниваем x1 = 0. Находим x2 = 5. Для нахождения второй точки приравниваем x2 = 0. Находим x1 = 4. Соединяем точку (0;5) с (4;0) прямой линией.

    Построим уравнение 4x1+8x2 = 32 по двум точкам. Для нахождения первой точки приравниваем x1 = 0. Находим x2 = 4. Для нахождения второй точки приравниваем x2 = 0. Находим x1 = 8. Соединяем точку (0;4) с (8;0) прямой линией.

    Построим уравнение 3x1+3x2 = 36 по двум точкам. Для нахождения первой точки приравниваем x1 = 0. Находим x2 = 12. Для нахождения второй точки приравниваем x2 = 0. Находим x1 = 12. Соединяем точку (0;12) с (12;0) прямой линией.

    На рисунке 1 представлены построенные прямые.


    Рисунок 1 - Прямые

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



    Рисунок 2 – Многоугольник
    Рассмотрим целевую функцию задачи F = 3x1+5x2 → max.
    Построим прямую, отвечающую значению функции F = 3x1+5x2 = 0. Вектор-градиент, составленный из коэффициентов целевой функции, указывает направление максимизации F(X). Начало вектора – точка (0; 0), конец – точка (3;5). Будем двигать эту прямую параллельным образом. Поскольку нас интересует максимальное решение, поэтому двигаем прямую до последнего касания обозначенной области. На рисунке 2 эта прямая обозначена пунктирной линией.

    Прямая F(x) = const пересекает область в точке C. Так как точка C получена в результате пересечения прямых , то ее координаты удовлетворяют уравнениям этих прямых:



    Откуда найдем максимальное значение целевой функции:

    F(x) = 3*1,33 + 5*3,33 = 20,67

    Решим данную задачу с помощью MS Excel.

    Введем исходные данные, рисунок 3.


    Рисунок 3 – Исходные данные
    Введем зависимости для целевой функции и ограничений, рисунок 4.


    Рисунок 4 – Зависимости

    Решим данную задачу с помощью Поиск решения, рисунок 5.


    Рисунок 5 – Поиск решения
    Таким образом, для максимизации прибыли необходимо производить деталей А – 1,33 шт, деталей В – 3,33 шт. Прибыль составит 20,67 д.ед.
    Ответ: F(x)max=20,67; x1=1,33; x2=3,33

    Задание № 2



    Условие:

    Составить задачу, двойственную задаче задания №1, дать содержательную интерпретацию
    Решение:

    Составим двойственную задачу.

    F(Z)=24y1+20y2+32y3+36y4

    Ограничения:



    При решении задачи в MS Excel выведем отчет об устойчивости, рисунок 6.


    Рисунок 6 – Отчет об устойчивости
    Оптимальный план двойственной задачи.
    y1=0, y2=0,17, y3=0,54, y4=0

    F(Z)=24*0+20*0,17+32*0,54+36*0=20,67

    Подставим оптимальный план прямой задачи в систему ограниченной математической модели:

    2*1,33+3*3,33 = 12,67< 24

    5*1,33+4*3,33=20=20

    4*1,33+8*3,33=32=32

    3*1,33+3*3,33=14<36

    1-ое ограничение выполняется как строгое неравенство, т.е. ресурс 1-го вида израсходован не полностью. Значит, этот ресурс не является дефицитным и его оценка в оптимальном плане y1 = 0.

    2-ое ограничение прямой задачи выполняется как равенство. Это означает, что 2-й ресурс полностью используется в оптимальном плане, является дефицитным и его оценка согласно второй теореме двойственности отлична от нуля (y2 ≠ 0).

    3-ое ограничение прямой задачи выполняется как равенство. Это означает, что 3-й ресурс полностью используется в оптимальном плане, является дефицитным и его оценка согласно второй теореме двойственности отлична от нуля (y3 ≠ 0).

    4-ое ограничение выполняется как строгое неравенство, т.е. ресурс 4-го вида израсходован не полностью. Значит, этот ресурс не является дефицитным и его оценка в оптимальном плане y4 = 0.
    Неиспользованный экономический резерв ресурса 4 составляет 22 (36-14).

    При подстановке оптимальных двойственных оценок в систему ограничений двойственной задачи получим:

    2*0+5*0,17+4*0,54+3*0=3=3

    3*0+4*0,17+8*0,54+3*0=5=5

    1-ое ограничение выполняется как строгое равенство, т.е. продукцию 1-го вида производить экономически выгодно, а его использование предусмотрено оптимальным планом прямой задачи (х1>0)

    2-ое ограничение двойственной задачи выполняется как равенство. Это означает, что 2-й продукт экономически выгодно производить (убытки от производства этого вида продукции отсутствуют), а его использование предусмотрено оптимальным планом прямой задачи (x2>0).

    Задание № 3



    Условие:

    На трех заводах производится однородная продукции в количестве единиц. Четырем потребителям требуется соответственно единиц продукции. Расходы по перевозке единицы продукции с i-го завода j-му потребителю известны (см. Транспортную таблицу 2). Требуется спланировать перевозку продукции так, чтобы затраты на транспортировку были минимальными.

    1) Записать математическую модель транспортной задачи.

    2) Найти опорное решение методом наименьшей стоимости и северо-западного угла.

    3) Опорное решение проверить методом потенциалов, получить оптимальное решение.
    Таблица 2 - Транспортная таблица

    Заводы
    Потребители
    Запас

    продукции, ед.

    В1
    В2
    В3
    В4

    А1
    4
    40
    6
    8
    600

    А2
    5
    7
    3
    9
    400

    А3
    4
    8
    6
    2
    700

    Потребность в продукции, ед.
    400
    300
    800
    200




    Решение:

    Проверим необходимое и достаточное условие разрешимости задачи.

    ∑a = 600+400+700 = 1700

    ∑b = 400+300+800+200=1700

    Условие баланса соблюдается. Запасы равны потребностям.

    Следовательно, модель транспортной задачи является закрытой.

    Используя метод северо-западного угла, построим первый опорный план транспортной задачи.

    План начинается заполняться с верхнего левого угла.

    Искомый элемент равен c11=4. Для этого элемента запасы равны 600, потребности 400. Поскольку минимальным является 400, то вычитаем его.
    x11 = min(600,400) = 400.

    Искомый элемент равен c12=40. Для этого элемента запасы равны 200, потребности 300. Поскольку минимальным является 200, то вычитаем его.
    x12 = min(200,300) = 200. Первая строка закрыта

    Искомый элемент равен c22=7. Для этого элемента запасы равны 400, потребности 100. Поскольку минимальным является 100, то вычитаем его.
    x22 = min(400,100) = 100.

    Искомый элемент равен c23=3. Для этого элемента запасы равны 300, потребности 800. Поскольку минимальным является 300, то вычитаем его.
    x23 = min(300,800) = 300. Вторая строка закрыта

    Искомый элемент равен c33=6. Для этого элемента запасы равны 700, потребности 500. Поскольку минимальным является 500, то вычитаем его.
    x33 = min(700,500) = 500.

    Искомый элемент равен c34=2. Для этого элемента запасы равны 200, потребности 200. Поскольку минимальным является 200, то вычитаем его.

    x34 = min(200,200) = 200. Третья строка закрыта

    Запишем полученный опорный план, таблица 3
    Таблица 3 – Опорный план
    B1
    B2
    B3
    B4
    Запасы

    A1
    4[400]
    40[200]
    6
    8
    600

    A2
    5
    7[100]
    3[300]
    9
    400

    A3
    4
    8
    6[500]
    2[200]
    700

    Потребности
    400
    300
    800
    200



    Подсчитаем число занятых клеток таблицы, их 6, а должно быть m + n - 1 = 6.

    Следовательно, опорный план является невырожденным.

    Значение целевой функции для этого опорного плана равно:

    F(x) = 4*400+40*200+7*100+3*300+6*500+2*200=14600

     Используя метод наименьшей стоимости, построим первый опорный план транспортной задачи.

    Искомый элемент равен c34=2. Для этого элемента запасы равны 700, потребности 200. Поскольку минимальным является 200, то вычитаем его.
    x34 = min(700,200) = 200.

    Искомый элемент равен c23=3. Для этого элемента запасы равны 400, потребности 800. Поскольку минимальным является 400, то вычитаем его.
    x23 = min(400,800) = 400.

    Искомый элемент равен c11=4. Для этого элемента запасы равны 600, потребности 400. Поскольку минимальным является 400, то вычитаем его.
    x11 = min(600,400) = 400.

    Искомый элемент равен c13=6. Для этого элемента запасы равны 200, потребности 400. Поскольку минимальным является 200, то вычитаем его.
    x13 = min(200,400) = 200.

    Искомый элемент равен c33=6. Для этого элемента запасы равны 500, потребности 200. Поскольку минимальным является 200, то вычитаем его.
    x33 = min(500,200) = 200.

    Искомый элемент равен c32=8. Для этого элемента запасы равны 300, потребности 300. Поскольку минимальным является 300, то вычитаем его.
    x32 = min(300,300) = 300.

    Получили опорный план задачи, таблица 4.

    Таблица 4 – Опорный план
    B1
    B2
    B3
    B4
    Запасы

    A1
    4[400]
    40
    6[200]
    8
    600

    A2
    5
    7
    3[400]
    9
    400

    A3
    4
    8[300]
    6[200]
    2[200]
    700

    Потребности
    400
    300
    800
    200




    Подсчитаем число занятых клеток таблицы, их 6, а должно быть m + n - 1 = 6. Следовательно, опорный план является невырожденным.

    Значение целевой функции для этого опорного плана равно:

    F(x) = 4*400+6*200+3*400+8*300+6*200+2*200=8000

    Так как значение целевой функции для опорного плана, найденного по минимальной стоимости, меньше чем значение целевой функции, найденной по северо-западному углу, то в качестве оптимального плана выбираем опорный план, найденный по наименьшей стоимости.

    Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0.

    u1 + v1 = 4; 0 + v1 = 4; v1 = 4

    u1 + v3 = 6; 0 + v3 = 6; v3 = 6

    u2 + v3 = 3; 6 + u2 = 3; u2 = -3

    u3 + v3 = 6; 6 + u3 = 6; u3 = 0

    u3 + v2 = 8; 0 + v2 = 8; v2 = 8

    u3 + v4 = 2; 0+ v4 = 2; v4 = 2
    v1=4
    v2=8
    v3=6
    v4=2

    u1=0
    4[400]
    40
    6[200]
    8

    u2=-3
    5
    7
    3[400]
    9

    u3=0
    4
    8[300]
    6[200]
    2[200]

    Опорный план является оптимальным, так все оценки свободных клеток удовлетворяют условию ui + vj ≤ cij.

    Минимальные затраты составят: F(x) = 4*400+6*200+3*400+8*300+6*200+2*200=8000

    Из 1-го склада необходимо груз направить в 1-й магазин (400 ед.), в 3-й магазин (200 ед.)

    Из 2-го склада необходимо весь груз направить в 3-й магазин.

    Из 3-го склада необходимо груз направить в 2-й магазин (300 ед.), в 3-й магазин (200 ед.), в 4-й магазин (200 ед.)

    Задание № 4



    Условие:

    Решение задачи о назначениях.

    На предприятии необходимо выполнить последовательно 12 видов работ (R1÷R12). 12 сотрудников предприятия (S1÷S12) затрачивают на выполнение каждого вида работ различное время в часах, таблица 5. Распределить работников по видам работ так, чтобы общее время на выполнение работ было минимально. Очередность выполнения работ не имеет значения. Составить экономико-математическую модель задачи и решить задачу, применив венгерский алгоритм.
    Таблица 5 - Исходные данные

    Сотруд-ник















    R1
    R2
    R3
    R4
    R5

    Вариант 2

    S1
    6
    5
    10
    11
    12

    S2
    6
    4,5
    8
    13
    15

    S3
    6,5
    5,5
    9
    12
    7

    S4
    5,5
    5
    11
    10
    10

    S5
    6
    5
    12
    9
    11


    Решение:

    Запишем экономико-математическую модель для нашей задачи.
    Переменные xij принимают значения 1, если i-й кандидат занимает j-ю вакансию. Если данное условие не выполняется, то xij=0.

    Ограничения по сотрудникам:

    x11 + x12 + x13 + x14 + x15 = 1

    x21 + x22 + x23 + x24 + x25 = 1

    x31 + x32 + x33 + x34 + x35 = 1

    x41 + x42 + x43 + x44 + x45 = 1

    x51 + x52 + x53 + x54 + x55 = 1

    Ограничения по времени:

    x11 + x21 + x31 + x41 + x51 = 1

    x12 + x22 + x32 + x42 + x52 = 1

    x13 + x23 + x33 + x43 + x53 = 1

    x14 + x24 + x34 + x44 + x54 = 1

    x15 + x25 + x35 + x45 + x55 = 1

    Целевая функция:

    6x11 + 5x12 + 10x13 + 11x14 + 12x15 + 6x21 + 4.5x22 + 8x23 + 13x24 + 15x25 + 6.5x31 + 5.5x32 + 9x33 + 12x34 + 7x35 + 5.5x41 + 5x42 + 11x43 + 10x44 + 10x45 + 6x51 + 5x52 + 12x53 + 9x54 + 11x55 → min

    В каждой строке ищем минимальный элемент и отнимаем от всех элементов строки.

    6
    5
    10
    11
    12

    6
    4,5
    8
    13
    15

    6,5
    5,5
    9
    12
    7

    5,5
    5
    11
    10
    10

    6
    5
    12
    9
    11


    Получаем:

    1
    0
    5
    6
    7

    1.5
    0
    3.5
    8.5
    10.5

    1
    0
    3.5
    6.5
    1.5

    0.5
    0
    6
    5
    5

    1
    0
    7
    4
    6


    Затем такую же операцию редукции проводим по столбцам, для чего в каждом столбце находим минимальный элемент.


    0.5
    0
    1.5
    2
    5.5

    1
    0
    0
    4.5
    9

    0.5
    0
    0
    2.5
    0

    0
    0
    2.5
    1
    3.5

    0.5
    0
    3.5
    0
    4.5


    После вычитания минимальных элементов получаем полностью редуцированную матрицу.

    Фиксируем нулевое значение в клетке (1, 2). Другие нули в строке 1 и столбце 2 вычеркиваем. Для данной клетки вычеркиваем нули в клетках (2; 2), (3; 2), (4; 2), (5; 2)

    Фиксируем нулевое значение в клетке (2, 3). Другие нули в строке 2 и столбце 3 вычеркиваем. Для данной клетки вычеркиваем нули в клетках (3; 3)
    Фиксируем нулевое значение в клетке (3, 5). Другие нули в строке 3 и столбце 5 вычеркиваем.

    Фиксируем нулевое значение в клетке (4, 1). Другие нули в строке 4 и столбце 1 вычеркиваем.

    Фиксируем нулевое значение в клетке (5, 4). Другие нули в строке 5 и столбце 4 вычеркиваем.

    В итоге получаем следующую матрицу:


    0
    [0]
    1.5
    2
    5.5

    1
    [-0-]
    [0]
    4.5
    9

    0.5
    [-0-]
    [-0-]
    2.5
    [0]

    [0]
    [-0-]
    2.5
    1
    3.5

    0.5
    [-0-]
    3.5
    [0]
    4.5


    Количество найденных нулей равно k = 5. В результате получаем оптимальную матрицу назначений:
    1















    1


















    1

    1





















    1




    Cmin = 5 + 8 + 7 + 5.5 + 9 = 34.5

    Путь: (1;2), (2;3), (3;5), (4;1), (5;4)

    Список использованных источников


    1. Продюсерство. Экономико-математические методы и модели: Учебное пособие / Под ред. Ю.В. Криволуцкого, Л.А. Фунберг. - М.: Юнити, 2015. - 319 c.

    2. Макаров, С.И. Методы оптимальных решений (экономико-математические методы и модели)(для бакалавров) / С.И. Макаров. - М.: КноРус, 2016. - 416 c

    3. Орлова, И.В. Экономико-математические методы и модели: компьютерное моделирование: Учебное пособие / И.В. Орлова, В.А. Половников. - М.: Вузовский учебник, 2017. - 344 c.

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