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

  • 2. Распределить план перевозок однотипного груза от трёх поставщиков к четырём потребителям, обеспечив минимальные затраты на перевозку. Исходные данные представлены в таблице 2.

    		•

    Мод. Практические занятия Составить план производства продукции, обеспечив максимум прибыли, учитывая ограничения, заданные в таблице1


    Скачать 26.98 Kb.
    НазваниеПрактические занятия Составить план производства продукции, обеспечив максимум прибыли, учитывая ограничения, заданные в таблице1
    Дата21.01.2023
    Размер26.98 Kb.
    Формат файлаdocx
    Имя файлаМод.docx
    ТипДокументы
    #897547

    ПРАКТИЧЕСКИЕ ЗАНЯТИЯ
    № 1. реализации единицы продукции, руб">Составить план производства продукции, обеспечив максимум прибыли, учитывая ограничения, заданные в таблице1.

    Таблица 1. Линейная оптимизация
    Расход сырья (доли)
    Прибыль от реализации единицы продукции, руб.

    Сырье 1
    Сырье 2
    Сырье 3
    Сырье 4

    Продукт 1
    0,2
    0,3
    0,1
    0,4
    120

    Продукт 2
    0,4
    0,1
    0,3
    0,2
    150

    Продукт 3
    0,6
    0,1
    0,1
    0,2
    110

    Наличие сырья на складе, кг
    850
    640
    730
    1000





    Решение:
    F(X) = 850x1+640x2+730x3+1000x4 → max при ограничениях:
    1/5x1+3/10x2+1/10x3+2/5x4≤120
    2/5x1+1/10x2+3/10x3+1/5x4≤150
    3/5x1+1/10x2+1/10x3+1/5x4≤110
    x1 ≥ 0, x2 ≥ 0, x3 ≥ 0, x4 ≥ 0


    F(X) = 850x1+640x2+730x3+1000x4


    В 1-м неравенстве смысла (≤) вводим базисную переменную x5.

    В 2-м неравенстве смысла (≤) вводим базисную переменную x6.

    В 3-м неравенстве смысла (≤) вводим базисную переменную x7.


    1/5x1+3/10x2+1/10x3+2/5x4+x5 = 120
    2/5x1+1/10x2+3/10x3+1/5x4+x6 = 150
    3/5x1+1/10x2+1/10x3+1/5x4+x7 = 110

    Переход к СЗЛП.

    Расширенная матрица системы ограничений-равенств данной задачи:

    1/5
    3/10
    1/10
    2/5
    1
    0
    0
    120

    2/5
    1/10
    3/10
    1/5
    0
    1
    0
    150

    3/5
    1/10
    1/10
    1/5
    0
    0
    1
    110


    1. В качестве базовой переменной можно выбрать x5.
    2. В качестве базовой переменной можно выбрать x6.
    3. В качестве базовой переменной можно выбрать x7.

    Поскольку в системе имеется единичная матрица, то в качестве базисных переменных принимаем X = (5,6,7).
    Соответствующие уравнения имеют вид:
    1/5x1+3/10x2+1/10x3+2/5x4+x5 = 120
    2/5x1+1/10x2+3/10x3+1/5x4+x6 = 150
    3/5x1+1/10x2+1/10x3+1/5x4+x7 = 110
    Выразим базисные переменные через остальные:
    x5 = -1/5x1-3/10x2-1/10x3-2/5x4+120
    x6 = -2/5x1-1/10x2-3/10x3-1/5x4+150
    x7 = -3/5x1-1/10x2-1/10x3-1/5x4+110
    Подставим их в целевую функцию:
    F(X) = 850x1+640x2+730x3+1000x4
    или
    F(X) = 850x1+640x2+730x3+1000x4 → max

    Система неравенств:
    -1/5x1-3/10x2-1/10x3-2/5x4+120 ≥ 0
    -2/5x1-1/10x2-3/10x3-1/5x4+150 ≥ 0
    -3/5x1-1/10x2-1/10x3-1/5x4+110 ≥ 0
    Приводим систему неравенств к следующему виду:
    1/5x1+3/10x2+1/10x3+2/5x4 ≤ 120
    2/5x1+1/10x2+3/10x3+1/5x4 ≤ 150
    3/5x1+1/10x2+1/10x3+1/5x4 ≤ 110

    F(X) = 850x1+640x2+730x3+1000x4 → max

    Упростим систему.
    2x1+3x2+x3+4x4 ≤ 1200
    4x1+x2+3x3+2x4 ≤ 1500
    6x1+x2+x3+2x4 ≤ 1100
    F(X) = 850x1+640x2+730x3+1000x4 → max
    Если задача ЛП решается на поиск min-го значения, то стандартная форма будет иметь следующий вид:
    -2x1-3x2-x3-4x4 ≤ -1200
    -4x1-x2-3x3-2x4 ≤ -1500
    -6x1-x2-x3-2x4 ≤ -1100
    F(X) = -850x1-640x2-730x3-1000x4 → min
    Решим прямую задачу линейного программирования симплекс-методом.
    Определим максимальное значение целевой функции F(X) = 850x1+640x2+730x3+1000x4 при следующих условиях-ограничений.
    1/5x1+3/10x2+1/10x3+2/5x4+x5+120=120
    2/5x1+1/10x2+3/10x3+1/5x4+x6+150=150
    3/5x1+1/10x2+1/10x3+1/5x4+x7+110=110


    Расширенная матрица системы ограничений-равенств данной задачи:

    1/5
    3/10
    1/10
    2/5
    1
    0
    0
    120

    2/5
    1/10
    3/10
    1/5
    0
    1
    0
    150

    3/5
    1/10
    1/10
    1/5
    0
    0
    1
    110


    1. В качестве базовой переменной можно выбрать x5.
    2. В качестве базовой переменной можно выбрать x6.
    3. В качестве базовой переменной можно выбрать x7.
    Поскольку в системе имеется единичная матрица, то в качестве базисных переменных принимаем X = (5,6,7).
    Выразим базисные переменные через остальные:
    x5 = -1/5x1-3/10x2-1/10x3-2/5x4+120
    x6 = -2/5x1-1/10x2-3/10x3-1/5x4+150
    x7 = -3/5x1-1/10x2-1/10x3-1/5x4+110
    Подставим их в целевую функцию:
    F(X) = 850x1+640x2+730x3+1000x4
    1/5x1+3/10x2+1/10x3+2/5x4+x5=120
    2/5x1+1/10x2+3/10x3+1/5x4+x6=150
    3/5x1+1/10x2+1/10x3+1/5x4+x7=110
    Введем новую переменную x0 = 850x1+640x2+730x3+1000x4.
    Выразим базисные переменные <5, 6, 7> через небазисные (свободные).
    x0 = 0+850x1+640x2+730x3+1000x4
    x5 = 120-1/5x1-3/10x2-1/10x3-2/5x4
    x6 = 150-2/5x1-1/10x2-3/10x3-1/5x4
    x7 = 110-3/5x1-1/10x2-1/10x3-1/5x4
    Переходим к основному алгоритму симплекс-метода.
    Поскольку задача решается на максимум, то переменную для включения в текущий план выбирают по максимальному положительному числу в уравнении для x0.
    1. Проверка критерия оптимальности.
    В выражении для x0 присутствуют положительные элементы. Следовательно, текущий план неоптимален.
    2. Определение новой базисной переменной.
    Поскольку коэффициент при переменной x4 больше, чем при остальных переменных, то при увеличении x4 целевая функция будет увеличиваться быстрее.
    max(850,640,730,1000,0,0,0) = 1000
    x0 = 0+850x1+640x2+730x3+1000x4
    x5 = 120-1/5x1-3/10x2-1/10x3-2/5x4
    x6 = 150-2/5x1-1/10x2-3/10x3-1/5x4-
    x7 = 110-3/5x1-1/10x2-1/10x3-1/5x4
    В качестве новой переменной выбираем x4.
    Вычислим значения Di по всем уравнениям для этой переменной: bi / ai4 и из них выберем наименьшее:
    min (120 : 2/5 , 150 : 1/5 , 110 : 1/5 ) = 300
    Вместо переменной x5 в план войдет переменная x4.
    Выразим переменную x4 через x5
    x4 = 300-1/2x1-3/4x2-1/4x3-5/2x5
    и подставим во все выражения.
    x0 = 0+850x1+640x2+730x3+1000(300-1/2x1-3/4x2-1/4x3-5/2x5)
    x6 = 150-2/5x1-1/10x2-3/10x3-1/5(300-1/2x1-3/4x2-1/4x3-5/2x5)
    x7 = 110-3/5x1-1/10x2-1/10x3-1/5(300-1/2x1-3/4x2-1/4x3-5/2x5)
    После приведения всех подобных, получаем новую систему, эквивалентную прежней:
    x0 = 300000+350x1-110x2+480x3-2500x5
    x4 = 300-1/2x1-3/4x2-1/4x3-5/2x5
    x6 = 90-3/10x1+1/20x2-1/4x3+1/2x5
    x7 = 50-1/2x1+1/20x2-1/20x3+1/2x5
    Полагая небазисные переменные x = (4, 6, 7) равными нулю, получим новый допустимый вектор и значение целевой функции:
    x = (-350, 110, -480, 0, 2500, 0, 0), x0 = 300000
    1. Проверка критерия оптимальности.
    В выражении для x0 присутствуют положительные элементы. Следовательно, текущий план неоптимален.
    2. Определение новой базисной переменной.
    Поскольку коэффициент при переменной x3 больше, чем при остальных переменных, то при увеличении x3 целевая функция будет увеличиваться быстрее.
    max(350,-110,480,0,-2500,0,0) = 480
    x0 = 300000+350x1-110x2+480x3-2500x5
    x4 = 300-1/2x1-3/4x2-1/4x3-5/2x5
    x6 = 90-3/10x1+1/20x2-1/4x3+1/2x5
    x7 = 50-1/2x1+1/20x2-1/20x3+1/2x5
    В качестве новой переменной выбираем x3.
    Вычислим значения Di по всем уравнениям для этой переменной: bi / ai3 и из них выберем наименьшее:
    min (300 : 1/4 , 90 : 1/4 , 50 : 1/20 ) = 360
    Вместо переменной x6 в план войдет переменная x3.
    Выразим переменную x3 через x6
    x3 = 360-6/5x1+1/5x2+2x5-4x6
    и подставим во все выражения.
    x0 = 300000+350x1-110x2+480(360-6/5x1+1/5x2+2x5-4x6)-2500x5
    x4 = 300-1/2x1-3/4x2-1/4(360-6/5x1+1/5x2+2x5-4x6)-21/2x5
    x7 = 50-1/2x1+1/20x2-1/20(360-6/5x1+1/5x2+2x5-4x6)+1/2x5
    После приведения всех подобных, получаем новую систему, эквивалентную прежней:
    x0 = 472800-226x1-14x2-1540x5-1920x6
    x4 = 210-1/5x1-4/5x2-3x5+x6
    x3 = 360-6/5x1+1/5x2+2x5-4x6
    x7 = 32-11/25x1+1/25x2+2/5x5+1/5x6
    Полагая небазисные переменные x = (4, 3, 7) равными нулю, получим новый допустимый вектор и значение целевой функции:
    x = (226, 14, 0, 0, 1540, 1920, 0), x0 = 472800
    Выражение для x0 не содержит положительных элементов. Найден оптимальный план.
    Окончательный вариант системы уравнений:
    x0 = 472800-226x1-14x2-1540x5-1920x6
    x4 = 210-1/5x1-4/5x2-3x5+x6
    x3 = 360-6/5x1+1/5x2+2x5-4x6
    x7 = 32-11/25x1+1/25x2+2/5x5+1/5x6
    Оптимальный план можно записать так:
    x1 = 0, x2 = 0, x3 = 360, x4 = 210, x5 = 0, x6 = 0, x7 = 32
    F(X) = 850*0 + 640*0 + 730*360 + 1000*210 = 472800
    № 2. Распределить план перевозок однотипного груза от трёх поставщиков к четырём потребителям, обеспечив минимальные затраты на перевозку.

    Исходные данные представлены в таблице 2.

    Таблица 2. Транспортная задача.
    Тарифы по перемещению единицы груза, тыс.руб.






    Потребитель1
    Потребитель2
    Потребитель3
    Потребитель4
    Возможности поставщика

    Поставщик1

    7
    250

    4

    9
    150

    3
    400
    U1=0

    Поставщик2
    406

    2

    11

    8
    144

    4
    550
    U2=1

    Поставщик 3
    44

    3

    8
    200

    6
    56

    5
    300
    U3=2

    Потребности потребителя
    450
    250
    200
    350












    V1=1
    V2=4
    V3=4
    V4=3






    S1=406*2+44*3+250*4+200*6+150*3+144*4+56*5=4450

    U1+V2=4 U1=0 V1=1

    U1+V4=3 U2=1 V2=4

    U2+V1=2 U3=2 V3=4

    U2+V4=4 V4=3

    U3+V3=6

    U3+V4=5

    Привышений нет S1=4450

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