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

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

       Если задачу принятия решений в области управления можно сформулировать в виде оптимизации вещественной функции 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 и при этом удовлетворяются все ограничения поставленной задачи.

Системы нелинейных алгебраических уравнений

Задание #12

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

       Команда Сервис/Подбор параметра… обладает широким спектром функций, одна из которых позволяет сконструировать постановку задачи для решения систем нелинейных алгебраических уравнений. В качестве примера рассмотрим решение системы уравнений:

 

           

 

       2А³+АВС+5А²=124

       12В+2А=8

       3С+4АС= -6

       Сформируем лист электронной таблицы как показано на рис 5.5.

           

 

рис 5.5

 

Систему уравнений разместим в клетках А6, А7, А8, а вместо переменных А, В, С укажем адреса клеток А3, В3 и С3 соответственно, которые содержат приближенные значения переменных.

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

 

рис 5.6

       В такой постановке одно из уравнений системы (любое) выступает как целевая функция, а два других как ограничения. После щелчка на кнопке ОК в клетках А3, В3 и С3 получим решение системы уравнений (рис 5.7).

 

рис 5.7

       Таким образом получаем, что решениями системы уравнений являются следующие значения: А=3, 28 В=0, 12 и С=-0, 37.

Здесь, как и в ранее приведенных примерах, большое значение имеет выбор начального приближения, который может обусловить не только нахождение разных решений, но и не обеспечить нахождения ни одного. Это еще раз говорит о необходимости тщательного выбора начального приближения решения. Что можно сделать исходя из косвенных знаний об области расположения интересующего нас решения или владея методами отделения корней.

 

 

Список литературы

⇐ Предыдущая1234

Поделиться: