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

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

Задача 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

	Имеются три пункта отправления А1,А2,А3 однородного груза и пять пунктов В1, В2, В3, В4, В5   его назначения. На пунктах А1,А2,А3 находится груз в количествах 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) для решения задачи использовать методы северо-западного угла и потенциалов. 

	Решение.

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

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

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

                 

     

      

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



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

Пункты

отправления

Пункты назначения

Запасы



В1

В2

В3

В4

В5



А1

            9

20

            5

30

             1

             1

             9

50

А2

           7

           1

             4

30

             9

            4

30

А3

           5

            3

             4

20

             9

30

            9

20

70

Потребности

20

30

50

30

20

150



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

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

         Полагаем U1 =0, а далее Ui + Vi = dij для занятых клеток таблицы.









Пункты

отправления



Пункты назначения

Запасы





В1

В2

В3

В4

В5







V1 =9

V2 =5

V3 =4

V4 =9

V5 =9



А1

U1 =0

          9

20

          5

30

          1

         1

          9

50

А2

U2 =0

         7

         1

          4

30

          9

         4

30

А3

U3 =0

          5

          3

          4

20

          9

30

          9

20

70

Потребности



20

30

50

30

20

150



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



 

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









Пункты

отправления



Пункты назначения

Запасы





В1

В2

В3

В4

В5







V1 =9

V2 =5

V3 =4

V4 =9

V5 =9



А1

U1 =0

          9



          5

30

          1

         1

20

          9

50

А2

U2 =0

          7

         1

          4

30

          9

          4

30

А3

U3 =0

         5

20

          3

          4

20

          9

10

          9

20

70

Потребности



20

30

50

30

20

150



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

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

         Полагаем U1 =0, а далее Ui + Vi = dij для занятых клеток таблицы.









Пункты

отправления



Пункты назначения

Запасы





В1

В2

В3

В4

В5







V1 =5

V2 =5

V3 =4

V4 =1

V5 =9



А1

U1 =0

          9



          5

30

          1

         1

20

          9

50

А2

U2 =0

          7

         1

          4

30

          9

          4

30

А3

U3 =0

         5

20

          3

          4

20

          9

10

          9

20

70

Потребности



20

30

50

30

20

150



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



 

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

 

Пункты

отправления



Пункты назначения

Запасы





В1

В2

В3

В4

В5







V1 =5

V2 =5

V3 =4

V4 =1

V5 =9



А1

U1 =0

          9



          5

10

          1

20

         1

20

          9

50

А2

U2 =0

          7

         1

          4

10

          9

          4

20

30

А3

U3 =0

         5

20

          3

20

          4

20

          9

10

          9



70

Потребности



20

30

50

30

20

150



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

         Полагаем U1 =0, а далее Ui + Vi = dij для занятых клеток таблицы.







Пункты

отправления



Пункты назначения

Запасы





В1

В2

В3

В4

В5







V1 =2

V2 =5

V3 =1

V4 =1

V5 =1



А1

U1 =0

          9



          5

10

          1

20

         1

20

          9

50

А2

U2 =3

          7

         1

          4

10

          9

          4

20

30

А3

U3 =3

         5

20

          3

20

          4

20

          9

10

          9



70

Потребности



20

30

50

30

20

150

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



 

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



Пункты

отправления



Пункты назначения

Запасы





В1

В2

В3

В4

В5







V1 =2

V2 =5

V3 =1

V4 =1

V5 =1



А1

U1 =0

          9



          5



          1

20

         1

30

          9

50

А2

U2 =3

          7

         1

10

          4



          9

          4

20

30

А3

U3 =3

         5

20

          3

20

          4

30

          9



          9



70

Потребности



20

30

50

30

20

150

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

         Полагаем U1 =0, а далее Ui + Vi = dij для занятых клеток таблицы.







Пункты

отправления



Пункты назначения

Запасы





В1

В2

В3

В4

В5







V1 =3

V2 =1

V3 =1

V4 =1

V5 =4



А1

U1 =0

          9



          5



          1

20

         1

30

          9

50

А2

U2 =0

          7

         1

10

          4



          9

          4

20

30

А3

U3 =2

         5

20

          3

20

          4

30

          9



          9



70

Потребности



20

30

50

30

20

150



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



 

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

         Найдем минимальную стоимость перевозок.



Ответ: 

































Задача 3

         Дана задача выпуклого программирования. Требуется:

1)     найти решение графическим методом

2)     написать функцию Лагранжа данной задачи и найти ее седловую точку, используя решение задачи, полученное графически.



 

	Решение.

          Графическое решение задачи следующее:



 

          Система неравенств определяет область, ограниченную двумя прямыми и координатными осями. График целевой функции представляет собой окружность переменного радиуса с центром в точке (5, 10). Значение целевой функции графически представляет собой квадрат радиуса этой окружности. Минимальным радиусом, удовлетворяющим системе ограничений, будет  такой радиус, который обеспечивает касание окружности с границей области так, как это показано на рисунке.

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

      

          Получили  точку (3 , 8), значение целевой функции в этой точке равно 

Запишем задачу в традиционном виде:



 

         Функция  называется функцией Лагранжа, а переменные   - коэффициентами Лагранжа.

         Точка   называется седловой точкой функции Лагранжа, если для любых   выполняются неравенства:



          Если функции  f, g дифференцируемы, то условия определяющие седловую точку (условия Куна-Таккера):

   

  

  

  В данном случае получаем: 

 



 

         Подставим в эти выражения значения:





         Получаем 



        Седловая точка функции Лагранжа: 

Проверим условие cедловой точки:



          Условия выполнены, седловая точка.

Ответ: 

 



 







 

Задача 4

	Для двух предприятий выделено 900 единиц денежных средств. Как распределить все средства в течение 4 лет, чтобы доход был наибольшим, если известно, что доход от х единиц, вложенных в первое предприятие равен , а доход от у единиц, вложенных во второе предприятие равен . Остаток средств к концу года составляет  - для первого предприятия,  - для второго предприятия. Решить задачу методом динамического программирования.

	Решение.

         Процесс распределения средств разобьем на 4 этапа – по соответствующим годам.

         Обозначим  - средства, которые распределяются на k–ом шаге как сумма средств по предприятиям.

         Суммарный доход от обоих предприятий на k–ом шаге:



          Остаток средств от обоих предприятий на k–ом шаге:



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

         Рекуррентные соотношения Беллмана для этих функций





          Проведем оптимизацию, начиная с четвертого шага:

         4-й шаг.

         Оптимальный доход равен:

 , т.к. линейная возрастающая функция достигает максимума в конце рассматриваемого промежутка, т.е. при .

         3-й шаг.

 

 т.к. линейная возрастающая функция достигает максимума в конце рассматриваемого промежутка, т.е. при .

            2-й шаг.

  т.к. линейная возрастающая функция достигает максимума в конце рассматриваемого промежутка, т.е. при .

            1-й шаг.



 т.к. линейная возрастающая функция достигает максимума в конце рассматриваемого промежутка, т.е. при .

         Результаты оптимизации:

  

  

    

      

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

Так как  , , получаем 







         Представим распределение средств в виде таблицы:

предприятие

год



1

2

3

4

1

900

90

9

0,9

2

0

0

0

0



        При таком распределении средств за 4 года будет получен доход, равный 

Ответ: 

 







           

27