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

       Анализируя возможности, можно заметить, что он применим для решения достаточно широкого класса задач математического программирования.

       Если задачу принятия решений в области управления можно сформулировать в виде оптимизации вещественной функции n неотрицательных вещественных переменных подчиненных m произвольным ограничениям:

max f(x₁, x₂,…,x_n)

при

g1 (x₁,x₂,…,x_n)≤0

g2 (x₁,x₂,…,x_n)≤0

…….

g3 (x₁,x₂,…,x_n)≤0

то позволяет найти решение такой задачи, которая в формальной подстановке может быть задачей:

1.линейного программирования (когда целевая функция и все ограничения - линейны)

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

3.целочисленного программирования (когда ограничение целочисленности налагается на все переменные)

4.частично целочисленного программирования (когда ограничение целочисленности налагается на часть переменных)

Линейное программирование

Задание #7

Решить задачу линейного программирования с помощью Поиска решения…, показать графически область допустимых решений и целевую функцию. Найдем максимум функции F = -2x ₁ + 2x ₂ →max при ограничениях:

x₁+ x ₂ ≥1

-5x ₁ + x ₂ ≥0,3

x ₁ – x ₂ ≤1

x ₁ + x ₂ ≤6

x ₁ ≥0

x ₂ ≥0.

Сформируем страницу электронной таблицы и постановку задачи линейного программирования в диалоговом окне Поиск решения …

 

 

рис 3.3

       После выполнения поставленной задачи получаем следующие значения переменных.

 

рис 3.4

Как видим, при найденных значениях х₁,х₂ целевая функция принимает минимальное значение равное 2 и этому удовлетворяют все ограничения поставленной задачи.

 Графическое решение поставленной задачи выглядит так (рис. 3.5):

                                                                         

рис. 3.5

 

Задание #8

 

       Авиакомпания МОГОЛ по заказу армии должна перевезти на некотором участке 700 человек. В распоряжении компании имеется два типа самолетов, которые можно использовать для перевозки. Самолет первого типа перевозит 30 пассажиров и имеет экипаж 3 человека, второго типа – 65 и 5 соответственно.

Эксплуатация 1 самолета первого типа обойдется 5000$    , а второго 9000$. Сколько надо использовать самолетов каждого типа, если для формирования экипажей имеется не более 60 человек.

 

       Для начала, обозначим переменные: пусть X₁ – это оптимальное количество самолетов первого типа, X₂ – оптимальное количества самолетов второго типа. Очевидно, что стоимость эксплуатации самолетов должна быть минимальной. Следовательно,

5000X₁ + 9000X₂→min

           

Теперь определим ограничения. Для формирования экипажей имеется не более 60 человек, следовательно:

3X₁ +5X₂<=60

Пассажиров надо перевезти не менее 700 человек, следовательно:

30X₁ +65X₂ >=700

       Сформируем страницу электронной таблицы и постановку задачи линейного программирования в диалоговом окне:

 

 

       После выполнения поставленной задачи получаем следующие значения переменных. Как показано на рис 3.6

 

Рис 3.6

Т.е. нам необходимо примерно (X₁=8) 8 самолётов первого класса и (X₂=6) 6 самолётов второго класса, для перевозки пассажиров.    

Задание #9

       Решим еще одну задачу с помощью Подбор параметра…. Найдем максимум функции

       F =2x ₁ -x ₂ +x ₃ ® max

       При ограничениях:

       -x ₁ -3x ₂ +x ₃ ≥ -5

       x ₁ +2x ₂ +x ₃ ≤ 7

       x ₁ +x ₂ +2x ₃ ≤ 3

       x ₁ ≥0

      x ₂ ,≥0

      x ₃ ≥ 0

       Сформируем страницу электронной таблицы и постановку задачи линейного программирования в диалоговом окне Подбор параметра …

 

Рис 4.4

рис 4.5

       После выполнения поставленной задачи получаем следующие значения переменных:

рис 4.6

       Как видим, при найденных значениях целевая x₁, x₂, x₃ функция принимает максимальное значение равное 6 и при этом удовлетворяются все ограничения поставленной задачи.