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

Автор: Пользователь скрыл имя, 11 Апреля 2011 в 16:40, контрольная работа

Краткое описание

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

Файлы: 1 файл

мат програмирование.doc

— 964.50 Кб (Скачать)

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

Задача 1

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

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

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

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

      Решение.

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

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

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

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

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

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

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

 

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

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

Базис Cб В 2 3 0 0 0
А1 А2 А3 А4 А5
А3 0 48 2 2 1 0 0
А4 0 38 1 2 0 1 0
А5 0 54 3 1 0 0 1
Fi - Ci   0 -2 -3 0 0 0
 

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

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

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

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

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

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

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

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

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

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

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

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

Базис Cб В 2 3 0 0 0
А1 А2 А3 А4 А5
А3 0 10 1 0 1 - 0
А5 0 19 0,5 1 0 0,5 0
А2 3 35 2,5 0 0 -0,5 1
Fi - Ci   57 -0,5 0 0 1,5 0
 

        Таким образом, новыми базисными  переменными становятся А3, А5, А2. 

 

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

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

         Вычисляем:

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

Новыми  базисными переменными становятся A5, A2, A1

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

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

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

     Базис Cб В 2 3 0 0 0
А1 А2 А3 А4 А5
А5 0 10 1 0 1 -1 0
А2 3 14 0 1 -0,5 1 0
А1 2 10 0 0 -2,5 2 1
Fi - Ci   62 0 0 1,5 1 0,5
 

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

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

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

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

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

Задача 2

      Имеются три пункта отправления А123 однородного груза и пять пунктов В1, В2, В3, В4, В5   его назначения. На пунктах А123 находится груз в количествах 50, 30, 70 тонн. В пункты В1, В2, В3, В4, В5   требуется доставить соответственно 20, 30, 50, 30, 20 тонн груза. Расстояния в сотнях километрах между пунктами отправления и назначения приведены в матрице D:

Пункты

отправления

Пункты  назначения
В1 В2 В3 В4 В5
А1 9 5 1 1 9
А2 7 1 4 9 4
А3 5 3 4 9 9
 

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

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

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

Информация о работе Математическое програмирование