Задачи по "Математике"

 

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

    Находим разрешающий элемент по минимальному неотрицательному симплексному отношению (по второму столбцу):

min {42/4; 74/6} = 42/4

    Следовательно, разрешающим элементом будет  значение, стоящее на пересечении  столбца х₂ и строки у₁, т.е. 4:

 

    Делаем  пересчет симплекс-таблицы, меняя местами  переменные х₂ и у₁. разрешающий столбец делим на разрешающий элемент и меняем при этом знак. На месте разрешающего элемента ставим величину, обратную ему. Разрешающую строку делим на разрешающий элемент. Остальные элементы находим по правилу прямоугольника. Результаты расчетов представлены в таблице 2.

 

    Выбираем  первый столбец.

    Находим разрешающий элемент по минимальному неотрицательному симплексному отношению (по первому столбцу):

min {10,5/1,5; 11/3} = 11/3

    Следовательно, разрешающим элементом будет  значение, стоящее на пересечении  столбца x₁ и строки у₂, т.е. 3: 

 

    Делаем  пересчет симплекс-таблицы, меняя местами  переменные х₂ и у₁. разрешающий столбец делим на разрешающий элемент и меняем при этом знак. На месте разрешающего элемента ставим величину, обратную ему. Разрешающую строку делим на разрешающий элемент. Остальные элементы находим по правилу прямоугольника. Результаты расчетов представлены в таблице 3.

 

    В единичном столбце и в F-строке нет отрицательных элементов, следовательно, получено оптимальное решение. Выпишем оптимальное решение.

    Для прямой задачи переменные, стоящие  в первой строке таблицы, являются небазисными  и их значения равны нулю. Значения переменных, стоящих в первом левом  столбце, равны соответствующим  значениям единичного столбца (табл. 4). 

     

    х₁ =3,667, х₂ = 5.

    Значение  целевой функции: F = 456, 667.

    Для двойственной задачи переменные, стоящие  в левом столбце таблицы, являются небазисными и их значения равны  нулю. Значения переменных, стоящих  в первой строке таблицы, равны соответствующим  значениям F-строки.

    U₁= 5, U₂ = 3,333.

    Значение  целевой функции: W = 456,667.

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

    

    

    

    Оптимальные двойственные оценки показывают предельную полезность (эффективность) каждого  ресурса. Величина двойственной оценки показывает насколько увеличится значение целевой функции при увеличении соответствующего ресурса на 1 ед. В данном случае имеем:

    U₁* =5, следовательно, при увеличении суммы на приобретение станков на 1 ед. производство деталей увеличится на 5 ед.

    U₂* =3,333, следовательно, при увеличении площади на 1 кв. м. производство деталей возрастет на 3,333 ед.

    Задание 4. Решить транспортную задачу по критерию стоимости методом потенциалов. Найти оптимальный план, при котором суммарные затраты на перевозку груза будут минимальными. Если оптимальным будет начальный опорный план, то решить задачу на максимум. Решить задачу Поиском решения в Excel.

    

                

    Решение:

    Пусть х_ij – объем перевозки от  i-го поставщика к j-му потребителю.

     , следовательно, транспортная  задача открытого типа. Вводим  фиктивного поставщика: А₄=64-58=6. Составляем математическую модель задачи:

    х₁₁+х₁₂+х₁₃+х₁₄ =10

    х₂₁+х₂₂+х₂₃+х₂₄ =14

    х₃₁+х₃₂+х₃₃+х₃₄ =16

    х₄₁+х₄₂+х₄₃+х₄₄ =18

    х₅₁+х₅₂+х₅₃+х₅₄ =6

    х₁₁+х₂₁+х₃₁+х₄₁+х₅₁ =12

    х₁₂+х₂₂+х₃₂+х₄₂+х₅₂ =18

    х₁₃+х₂₃+х₃₃+х₄₃+х₅₃ =14

    х₁₄+х₂₄+х₃₄+х₄₄+х₅₄ =20

    х_ij =>0  х_ij : целые

    Z=5х₁₁+7х₁₂+6х₁₃+4х₁₄+2х₂₁+х₂₂+3х₂₃+8х₂₄+6х₃₁+8х₃₂+6х₃₃+4х₃₄+11х₄₁+

    +2х₄ +3х₄₃+8х₄₄ -> min

    Целевая функция выражает общие затраты  на перевозку, поэтому ее минимизируем.

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

 

    Число заполненных клеток=m+n-1=5+4-1=8, следовательно, полученный план невырожденный. Затраты  на транспортировку составят:

    

    Найдем  оптимальный план задачи методом  потенциалов. Полагая U₁=10, находим значения V_ij и U_ij по заполненным клеткам.

    По  пустым клеткам определяем из соотношения  Δ_ij=V_ij-U_ij-c_ij.

    Выписываем  положительные значения  Δ_ij:

    Δ₁₄=17-4-10=3

    Δ₃₁=15-6-3=3

    Δ₃₄=17-4-7=7

    Δ₄₂=14-2-9=3

    Выбираем  наибольшее значение: Δ₃₄=17-4-7=7

    Строим  из ячейки 34 замкнутый цикл: