1.9. Задачи и вопросы для практических работ
Задача 1. Производственная
программа фирмы представлена в виде
задачи
при ограничениях
,
;
,
.
а) Построить каноническую форму задачи;
б) построить область допустимых решений и линии уровня целевой функции.
в) найти графическое решение задачи и обосновать его оптимальность
г) оценить в отдельности влияние на оптимальное решение задачи коэффициентов целевой функции, технологических параметров и величин ресурсов.
Задача 2. Оптимизируемый объект описывается с помощью задачи
,
,
,
.
а) Построить каноническую форму задачи;
б) найти все тройки линейно зависимых векторов матрицы расширенной задачи;
в) построить всевозможные базисы расширенной задачи, вычислить базисные решения и построить соответствующие вершины расширенного пространства решений
г) решить задачу с помощью табличного симплекс-метода, выделив все промежуточные базисы, базисные решения, текущие варианты.
д) оценить выбор максимальной симплекс – разности на ход алгоритма.
Задача 3. Построить двойственную задачу оптимизируемого объекта, описанного в задаче 2 и найти ответы на следующие вопросы:
а) в каком виде присутствует решение двойственной задачи в последней (оптимальной) таблице прямой задачи?;
б) проверить равенство целевых функций прямой и двойственной задач;
в) проверить, выполняются ли условия дополняющей нежесткости Слейтера для прямой и двойственной задач?;
г) убедиться в том, что двойственные
переменные связаны с последним оптимальным
базисом прямой задачи соотношением
или в эквивалентной форме
,
где
- оптимальный базис,
- вектор коэффициентов при оптимальных
базисных переменных.
Задача 4. Задача линейного
программирования представлена в виде:
максимизировать функцию
при ограничениях
,
,
.
а) Построить графическую картину задачи и найти ее решение;
б) построить расширенную задачу и найти всевозможные начальные базисы и базисные решения;
в) начиная с единичного базиса,
иллюстрировать все этапы рекуррентной
формулы
и найти оптимальное решение задачи;
г) в координатной плоскости
показать проекции всех направлений
движения, величин шагов, вершин расширенной
области, в том числе и оптимальную
вершину;
д) оценить вычислительную (или алгоритмическую) сложность табличного и рекуррентного алгоритмов симплекс-метода.
Ответ:
.
Задача 5. Найти начальный базис задачи линейного программирования
(D, f):
,
,
,
,
,
используя метод искусственных переменных.
Задача 6. Найти все целочисленные решения задачи
,
, - целые
с помощью метода ветвей и границ. Построить и проанализировать соответствующее дерево решений и оценить альтернативные варианты ветвления.
Задача 7. Решить задачу целочисленного линейного программирования методом ветвей и границ
(D, f):
,
, - целые
Построить всевозможные деревья решений и дать графическую иллюстрацию процесса ветвления.
Задача 8. Производственный план,
отвечающий ограничениям
,
,
,
должен максимизировать критерии
,
.
Исследовать этот план, ответив на
следующие вопросы:
а) графически найти локальные оптимальные решения данной задачи;
б) показать области допустимых решений
и оценок, а также подмножества оптимальных
по Парето решений
и соответствующую эффективную границу
;
в) задаваясь различными значениями
коэффициентов важности
,
,
найти графическим путем экстремум
скалярной функции
и исследовать влияние
и
на оптимальное решение;
г) выбрать одну из целевых функций в качестве главной и найти оптимальное решение при различных ограничениях для значений другой функции;
д) графически найти точку
,
расположенную наиболее близко к точке
где
и
наибольшие значения координат
и
.
Как выглядит точка
,
которая находится на минимальном
расстоянии от “утопической” точки
,
где
и
- наибольшие значения критериев
и
на множестве D.
Задача 9. Проектируемый объект и критерий качества его функционирования представлены в виде модели оптимизируемой задачи
.
а) Применить метод множителей Лагранжа по отношению к этой и двойственной ей задачам и найти соответствующие условия теоремы Куна – Таккера;
б) графическим способом найти соответствующие оптимальные решения и проверить выполнение условий двойственности;
в) интерпретировать физический смысл
переменных прямой и двойственной задач
и убедиться в справедливости условий
,
j = 1,2;
,
i = 1, 2, где L
– соответствующая функция Лагранжа
исходной задачи.