Тема 12. Целочисленное программирование

Математическая формулировка задачи целочисленного программирования. Классификация задач целочисленного программирования. Классификация методов решения задач целочисленного программирования. Метод отсечения в линейной задаче целочисленного программирования. Использование метода динамического программирования в задаче целочисленного программирования. Метод ветвей и границ в задачах целочисленного программирования.

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

1. Сделать два шага в итерационном методе Ньютона поиска нуля функции f(x) = x³-2x-4.
В качестве начального приближения взять x₀ = 1.

2. Найти минимальное значение функции двух переменных

f(x,y) = x²-2x+y²-2y+6. При каких значениях переменных оно достигается?

3. Сделать один шаг в итерационном методе секущих поиска нуля функции f(x) = x³-2x-4.
В качестве начального приближения взять x₀ = 1, x₁ = 3.

4. Решите следующую задачу линейного программирования найти максимальное значение величины z=x+y→max при заданных ограничениях: x+2y≤5; 3x+y≤8; x,y≥0.

5. Решите следующую задачу линейного программирования: найти минимальное значение величины z = x+y→min x-y≥3; 3x-y≤-3; x,y≤0.

6. Найти условный экстремум функции F(x,y)=xy при условии x+y = 1, используя метод неопределенных множителей Лагранжа.

7. Найти условный экстремум функции F(x,y) = xy+x при условии x-2y = 1, используя метод неопределенных множителей Лагранжа.

8. Записать уравнение Эйлера для функционала: F[y(x)] = ∫(xy′+(y′)²)dx.

9. Записать уравнение Эйлера для функционала: F[y(x)] = ∫(1+(y′)²)dx.

10. Записать уравнение Эйлера для функционала: F[y(x)] = ∫((y′)²+2yy′)dx.

11. Записать первые 5 чисел ряда Фибоначчи.

12. Сделать два шага в итерационном методе Ньютона поиска нуля функции f(x) = 3x³-x-2.
В качестве начального приближения взять x₀ = 0.

13. Известно, что уравнение Эйлера для некоторого функционала имеет вид:

y′′ = 0; y(0) = 0, y(1) = 1. Найти уравнение экстремали.

14. Найти точку экстремума функции двух переменных f(x,y) = xy+y²-x²+y

15. Исследовать функцию f(x) = 2x²-2xy+y²-2x+2 на безусловный экстремум

16. Используя графический метод, найти минимум функции F = 4x+3y при ограничениях: 4x+y-3≥0; x+5y-15≥0; x,y≥0.

17. Используя симплекс-метод, найти минимум функции F=2x+3y при ограничениях:
4x+y-2≥0; x+2y-4≥0; x,y≥0.

18. Используя графический метод, найти минимум функции F=x+3y при ограничениях:
x-2≤0; y-2≤0; x,y≥0.

19. Используя графический метод, найти максимум функции F=x+2y при ограничениях:
y-2≤0; 5x-y≤8; x,y≥0.

20. В плоскости (x,y) указать область, для которой выполняются следующие условия: x+y≥2; x,y≥0.

21. В плоскости (x,y) указать область, для которой выполняются следующие условия: y-x≤2; y ≥0; x≤0.

22. Записать уравнение Эйлера для функционала: F[y(x)] = ∫x(y′)²dx.

23. Записать уравнение Эйлера для функционала: F[y(x)] = ∫yy′dx.

24. Прибыль фирмы F менялась в зависимости от года-x и от номера месяца в году следующим образом F(x,у) = 50-x²+10x-y²+10y.

Определить, в каком году и в каком месяце прибыль была максимальной.

25. Фирма выпускает два вида товаров а и б. Цена товара а - 2$ за штуку и цена товара
б - 1$ за штуку. Какое количество товара а (х) и товара б (y) надо выпускать ежедневно, чтобы выручка была максимальной. При этом надо учитывать, что за день может быть произведено не более 10 штук товара б (y≤10) и количество y не менее чем на 3 должно превышать количество х [(y-x)≥3]. Определить величину максимальной ежедневной выручки.

26. Фирма выпускает автомобили двух видов х штук в день по цене 1000$ и y штук в день по цене 2000$. Сколько автомобилей каждого вида надо выпускать ежедневно, чтобы прибыль была максимальной? При этом надо учитывать, что в день может быть изготовлено не более
10 автомобилей обоих видов т.е. (x+y) ≤10 и что число автомобилей y не может превышать число автомобилей х более, чем на 2 т.е. (y-x) ≤2. Определите, какова величина максимальной прибыли.

27. Фирма выпускает автомобили двух видов х штук в день по цене 1000$ и y штук в день по цене 2000$. Сколько автомобилей каждого вида надо выпускать ежедневно, чтобы прибыль была максимальной. При этом надо учитывать, что в день может быть изготовлено не более
9 автомобилей обоих видов, т.е. (x+y) ≤9 и что число автомобилей y не может превышать число автомобилей х более чем в 2 раза т.е. y ≤2x. Определите, какова величина максимальной прибыли.

28. Найти точку экстремума функции двух переменных f(x,y) = 2xy+y²-x²+2x.

29. Сделать один шаг в итерационном методе секущих поиска нуля функции f(x) = 3x³-x-2.
В качестве начального приближения взять x₀ = 0, x₁ = 2.

30. В плоскости (x,y) указать область, определяемую неравенствами: (x²+y²) ≤1; (x-y) ≤0.

31. Найти условный экстремум функции F(x,y) = x² +y² при условии y = x+1, используя метод неопределенных множителей Лагранжа.

32. Найти условный экстремум функции F(x,y) = x² +2y² при условии y = x+1, используя метод неопределенных множителей Лагранжа.

33. Найти условный экстремум функции F(x,y) = x²+y²+x при условии y = x+1, используя метод неопределенных множителей Лагранжа.