Математическое програмирование

Математическое  программирование

Задача 1

  Для производства двух видов изделий А и В используется три типа технологического оборудования. Для производства единицы изделия А оборудование первого типа используется 2  часа, оборудование второго типа – 1 час, оборудование третьего типа – 3 часа. Для производства единицы изделия В оборудование первого типа используется 2 часа, оборудование второго типа – 2 часа, оборудование третьего типа – 1 час.

         На изготовление всех изделий  предприятие может использовать оборудование первого типа не более чем 48 часа, оборудование второго типа – 38 часов, оборудование третьего типа – 54 часов.

         Прибыль от реализации единицы готового изделия А составляет 2 денежные единицы, а изделия В – 3 денежные единицы.

         Составить план производства изделий А и В, обеспечивающий максимальную прибыль от их реализации.  Решить задачу симплекс-методом путем преобразования симплекс-таблиц. Дать геометрическое истолкование задачи, используя для этого ее формулировку с ограничениями – неравенствами.

      Решение.

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

         Прибыль рассчитывается по формуле:

          Запишем математическую модель задачи:

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

        Для этого построим на плоскости  области, описываемые ограничениями-неравенствами, и прямую , которая называется целевой функцией.

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

         График целевой функции передвигается в направлении, обозначенном стрелкой (в направлении своего градиента), до тех пор, пока не достигнет граничной точки многоугольника – в нашем случае это точка – (10 ; 14).  В этой точке целевая функция будет достигать максимума.

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

       Составляем симплекс-таблицу:

         В графе Базис записываются  вектора переменных, принимаемые  за базисные. На первом этапе  это – А₃, А₄, А₅. Базисными будут переменные, каждая из которых входит только в одно уравнение системы, и нет такого уравнения, в которое не входила бы хотя бы одна из базисных переменных.

         В следующий столбец  записываются коэффициенты целевой функции, соответствующие каждой переменной. Столбец В – столбец свободных членов. Далее идут столбцы коэффициентов А_i при i –й переменной.

         Под столбцом свободных членов  записывается начальная оценка 

         Остальные оценки записываются  под столбцами соответствующих  векторов  .

         Преобразуем симплекс-таблицу следующим образом:

      Шаг 1: Проверяется критерий оптимальности, суть которого состоит в том, что все оценки  должны быть неотрицательны. В нашем случае этот критерий не выполнен, поэтому переходим ко второму шагу.

         Шаг 2: Для отрицательных оценок  вычисляются величины:

          Из этих элементов выбирается  тот, для которого вычисленное  произведение минимально, в нашем случае -57 минимально, поэтому в качестве разрешающего элемента выбирается второй элемент второго столбца – 2 (выделен в таблице).

         Шаг 3: Вторая строка таблицы делится на 2

От элементов строки 1 отнимает соответствующие элементы строки 2, умноженные на 2.

От элементов строки 3 отнимает соответствующие элементы строки 2.

От элементов строки 4 отнимает соответствующие элементы строки 2, умноженные на -3.

        Таким образом, новыми базисными  переменными становятся А₃, А₅, А₂. 

        Возвращаемся к шагу 1 и повторяем  весь процесс.

Проверяется критерий оптимальности. Отрицательная оценка только одна – в столбце А₁.

         Вычисляем:

         Разрешающим элементом будет  первый элемент первого столбца – 1.

Новыми  базисными переменными становятся A₅, A₂, A₁

От элементов строки 2 отнимает соответствующие элементы строки 1, умноженные на 0,5.

От элементов строки 3 отнимает соответствующие элементы строки 1, умноженные на 2,5.

От элементов строки 4 отнимает соответствующие элементы строки 1, умноженные на -0,5.

      Отрицательных оценок нет, то есть критерий оптимальности выполнен.

      Таким образом, получается искомое значение целевой функции 

F(10; 14; 0; 0; 10) = 62, т.е. возвращаясь к системе неравенств, получаем:

        Ответы, полученные различными методами, совпадают.

Ответ: х_опт = ( 10 , 14) Значение функции : F = 62 
 

Задача 2

      Имеются три пункта отправления А₁,А₂,А₃ однородного груза и пять пунктов В₁, В₂, В₃, В₄, В₅   его назначения. На пунктах А₁,А₂,А₃ находится груз в количествах 50, 30, 70 тонн. В пункты В₁, В₂, В₃, В₄, В₅   требуется доставить соответственно 20, 30, 50, 30, 20 тонн груза. Расстояния в сотнях километрах между пунктами отправления и назначения приведены в матрице D:

          Найти такой план перевозок,  при котором общие затраты  на перевозку грузов будут минимальными.

      Указания: 1) считать стоимость перевозок пропорциональной количеству груза и расстоянию, на которое этот груз перевозится, т.е. для решения задачи достаточно минимизировать общий объем плана, выраженный в тонно-километрах;

2) для  решения задачи использовать  методы северо-западного угла и потенциалов.

      Решение.

        Составим математическую модель задачи:

Обозначим - количество груза, перевезенного из пункта отправления i в пункт назначения j.

Получим следующие ограничения (т.к. весь груз должен быть вывезен, и все потребности удовлетворены полностью):

     При этом должна быть минимизирована целевая функция

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

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

      Построим  систему потенциалов. U_i - потенциалы, соответствующие поставщикам,  V_i- потенциалы, соответствующие потребителям.

         Полагаем U₁ =0, а далее U_i + V_i = d_ij для занятых клеток таблицы.

         Проверим критерий оптимальности  : для свободных клеток.

         Из тех условий, где критерий не выполняется, выбираем то условие, где разница максимальна. Это – ячейка (1 , 4). Перебросим в ячейку (1 , 4) 20 единиц груза из ячейки (1 , 1). 
 
 
 

         Чтобы компенсировать недостаток  в третьей строке, перебросим те же 20 единиц груза из ячейки (3 , 4) в ячейку (3 , 1).

      Получили новую таблицу, для которой повторяем расчет потенциалов:

         Полагаем U₁ =0, а далее U_i + V_i = d_ij для занятых клеток таблицы.

         Проверим критерий оптимальности  : для свободных клеток.

         Из тех условий, где критерий  не выполняется, выбираем то  условие, где разница максимальна.  Это – ячейка (2 , 5). Перебросим в ячейку (2 ,5) 20 единиц груза из ячейки (1 , 2).