14.Постановка задачи нелинейного программирования в общем виде.
Среди задач нелинейного программирования наиболее глубоко изучены
задачи выпуклого программирования. Это задачи, в результате решения которых
определяется минимум выпуклой (или максимум вогнутой) функции, заданной
на выпуклом замкнутом множестве.
15.Постановка задачи целочисленного программирования в общем виде
B задачах целочисленного программирования неизвестные могут
принимать только целочисленные значения.
16.Постановка задачи квадратичного программирования в общем виде.
B свою очередь, среди задач выпуклого программирования более подробно исследованы задачи квадратичного программирования. B результате решения таких задач требуется в общем случае найти максимум (или минимум) квадратичной функции при условии, что ее переменные удовлетворяют некоторой системе линейных неравенств или линейных уравнений либо некоторой системе, содержащей как линейные неравенства, так и линейные уравнения.
17.Постановка задачи стохастического программирования в общем виде.
Если в целевой функции или в функциях, определяющих область возможных изменений переменных, содержатся случайные величины, то такая задача относится к задаче стохастического программирования.
18. Постановка задачи динамического программирования в общем виде.
Задача, процесс нахождения решения которой является многоэтапным,
относится к задаче динамического программирования
1.В чем состоит задача оптимизации?
Под оптимизацией понимают процесс выбора наилучшего варианта из всех возможных. С точки зрения инженерных расчетов методы оптимизации позволяют выбрать наилучший вариант конструкции, наилучшее распределение ресурсов и т.д. В процессе решения задачи оптимизации обычно необходимо найти оптимальные значения некоторых параметров, определяющих данную задачу.
2. Приведите математическую запись задачи оптимизации.
3. Что означает найти решение задачи оптимизации?
найти такое решение, при котором значение целевых функций были бы приемлемыми для постановщика задачи.
4. В каком случае задача оптимизации не имеет решения?
Оптимизация — в математике, информатике и исследовании операций задача нахождения экстремума (минимума или максимума) целевой функции в некоторой области конечномерного векторного пространства, ограниченной набором линейных и/или нелинейных равенств и/или неравенств.
5. В каком случае для решения задачи оптимизации необходимо использовать методы математического программирования?
6. Укажите характерные черты задачи линейного программирования.
7. Приведите общий вид математической модели задачи линейного
программирования.
Задачи оптимизации, в которых целевая функция и ограничения являются линейными функциями, разрешаются так называемыми методами линейного программирования.
8. Что собой представляет область допустимых решений.
Область допустимых решений представляет собой выпуклый многогранник, имеющий конечное число вершин. Процедура поиска решения заключается в переходе от одной вершины к другой, так чтобы значение функции улучшалось. Процедура поиска завершается в случае, когда из текущей вершины будет невозможен переход, связанный с улучшением функции.
9. Приведите определение понятия «оптимальное решение».
Оптимальное решение — решение, которое по тем или другим признакам предпочтительнее других В технике оптимальный (вариант, решение, выбор и т. д.) — наилучший (вариант, решение, выбор, …) среди допустимых при наличии правила предпочтения одного другому. Это одно из решений при котором целевая функция принимает свое max(min) значение
10. Чем допустимое решение отличается от оптимального решения.
Определение. Любое решение системы ограничений называется допустимым решением ЗЛП. Допустимое решение, в котором целевая функция достигает максимального или минимального значения, называется оптимальным решением. Это совокупность чисел удовл ограничению задачи X={x1 … xm }
11. Приведите правила приведения задачи линейного программирования к
каноническому виду.
1 Если исходная задача на макс целевой функции то следует изменить знак и искать мин целевой функции.
2 Если в ограничении правая часть отриыательная, то следует множить ограничения на “-1”
3 Если в ограничениях имеются неравенства то путем введения неотрицательных элементов они преобразуются в равенства
4 Если некоторые переменные Хк не имееют ограничений по знаку, то она заменяется разностью XK = XK - XL
12. Приведите область применения графического метода для решения задач
линейного программирования.
Графический метод решения задачи линейного программирования основан на геометрической интерпретации задачи линейного программирования и применяется в основном при решении задач двумерного пространства и только некоторых задач трёхмерного пространства, так как довольно трудно построить многогранник решений, который образуется в результате пересечения полупространств. Задачу пространства размерности больше трёх изобразить графически вообще невозможно.
13. Приведите примеры возможных конфигураций области допустимых
решений при решении задачи линейного программирования графическим
методом.
Случай 1. Прямая , передвигаясь в направлении вектора или противоположно ему, постоянно пересекает многоугольник решений и ни в какой точке не является опорной к нему. В этом случае линейная функция не ограничена на многоугольнике решений как сверху, так и снизу.
Случай 2. Прямая, передвигаясь, всё же становится опорной относительно многоугольника решений. Тогда в зависимости от вида области линейная функция может быть ограниченной сверху и неограниченной снизу, ограниченной снизу и неограниченной сверху, либо ограниченной как снизу, так и сверху.
14. Приведите систему ограничений, которая образует в качестве области
допустимых решений выпуклый многоугольник.
15. Приведите систему ограничений, которая образует в качестве области
допустимых решений выпуклую многоугольную неограниченную область.
16. Приведите систему ограничений, которая не образует область допустимых решений.
17. Приведите систему ограничений, которая образует в качестве области
допустимых решений луч.
18. Приведите систему ограничений, которая образует в качестве области
допустимых решений отрезок.
19. Приведите систему ограничений, которая образует в качестве области
допустимых решений точку.
20. Каким образом строится вектор-градиент целевой функции.
Коэффициенты, стоящие при неизвестных целевой функции берутся за координаты вектора и наносятся на координатную ось. От точки с координатами (0;0) ведётся прямая к точке пересечения координат вектора. Через точку с координатами (0;0) проводим перпендикуляр прямой вектора.
21. Какой смысл имеет вектор-градиент целевой функции.
С помощью вектора-градиента мы показываем на ОДР место нахождения точек min, max.
22. Какими рассуждениями руководствуются при определении максимального значения целевой функции, решая задачу линейного программирования графическим методом.
Идя параллельно перпендикуляру прямой вектора мы находим точку max. Последняя точка ОДР, через которую проходит параллельная линия перпендикуляра и есть точка max.
23. Какими рассуждениями руководствуются при определении минимального
значения целевой функции, решая задачу линейного программирования
графическим методом.
Идя параллельно перпендикуляру прямой вектора мы находим точку min. Первая точка ОДР, через которую проходит параллельная линия перпендикуляра и есть точка min.
24. Приведите геометрическую идею симплекс-метода.
25. Приведите порядок решения ЗЛП симплекс-методом.
26. Что означает ситуация когда в симплекс-таблице все коэффициенты в
столбце свободных членов положительные.
25. Приведите порядок решения ЗЛП симплекс-методом.
26. Что означает ситуация когда в симплекс-таблице все коэффициенты в
столбце свободных членов положительные.
27. Что означает ситуация когда в симплекс-таблице один из коэффициентов
столбца свободных членов отрицательный и среди коэффициентов этой строки
есть несколько отрицательных коэффициентов.
28. Что означает ситуация когда в симплекс-таблице один из коэффициентов
столбца свободных членов отрицательный и среди коэффициентов этой строки нет отрицательных.
29. Что означает ситуация когда в симплекс-таблице все коэффициенты столбца свободных членов и строки целевой функции положительные.
30. Что означает ситуация при отыскании оптимального решения когда в строке
целевой функции симплекс-таблицы есть несколько отрицательных
коэффициентов.
31. Что означает ситуация при отыскании оптимального решения когда в строке
целевой функции симплекс-таблицы есть отрицательный коэффициент и
столбец в котором он находится, содержит несколько положительных
коэффициентов.
32. Что означает ситуация при отыскании оптимального решения когда в
симплекс-таблице в строке целевой функции есть отрицательный коэффициент
и столбец в котором он находится не содержит положительных коэффициентов.
33. В чем заключается анализ моделей на чувствительность при решении задач линейного программирования?
Анализ моделей на чувствительность – это процесс, реализуемый после получения оптимальных решений. Позволяет выявить чувствительность оптимального решения к параметрам исходной модели
34. В чем заключается решение задачи об изменении запасов ресурсов, которая решается в рамках анализа моделей на чувствительность?
Рассматривается степень влияния на оптимальное решение увеличения и уменьшения спроса на продукцию или запасов исходного сырья, так же рассматривается влияние рыночных цен на оптимальное решение.
35. Дайте определение дефицитного ресурса и недефицитного ресурса.
Деф.р. – соответствует активному ограничению и используется полностью
Активное ограничение проходит через точку оптимума.
Недеф. Ресурс – соотв не активному ограничению, остается в избытке
36. В чем заключается задача анализа изменения запасов ресурсов для
дефицитных ресурсов?
Необходимо определить предельно допустимое увеличение запасов деф. Ресурсов, позволяющее улучшить найденное оптимальное решение.
37. В чем заключается задача анализа изменения запасов ресурсов для
недефицитных ресурсов?
Необходимо определить предельно допустимое снижение запасов недеф. Ресурса не изменяющее найденное раннее значение целевой функции
38. В чем заключается задача об определении наиболее выгодного ресурса?
Какому ресурсу следует отдать предпочтение при вложении дополнительных средств
39. В чем заключается задача об определении пределов изменения
коэффициентов целевой функции?
Изменение коэффициентов целевой функции влияет на наклон прямой, которая представляет собой целевую функцию. При рассмотрении данной задачи необходимо ответить на вопросы
-Какой диапазон изменения того или иного коэффициента целевой функции, при котором точка экстремума не изменится.
- На сколько следует изменить тот или иной коэффициент целевой функции, чтобы сделать недефицитный ресурс дефицитным и наобарот
40. В чем заключается принцип двойственности в линейном
программировании.
Принцип двойственности заключается в том, что для каждой задачи линейного программирования можно составить двойственную задачу
41. Приведите правила формирования двойственной задачи из прямой задачи?
1) Свободные члены ограничений п.з. служит коэффициент целевой функции д.з. , коэффициенты целевой функции п.з. служат свободными членами ограничений двойственной задачи. Число переменных двойственной задачи равно числу ограничений прямой задачи, а число ограничений д. з. равно числу переменных п.з.
2)Матрицей коэф. ограничений двойственной задачи служит матрица полученная путем транспонирования матрицы коэф. ограничений прямой задачи
3)каждому ограничению неравенства прямой задачи соответствует положительная переменная двойственной задачи
4)Максимизация целевой функции п.з. соответствует минимизация целевой функции д.з.
42. Приведите формулировку основной теоремы двойственности.
Пусть рассматриваемая пара двойственных задач, если одна из них обладает оптимальным решением, то и другая имеет оптимальное решение, причем экспериментальные значения целевых функций равны.
43. Приведите экономическую интерпретацию двойственной задачи.