Графическое решение задачи целочисленного ЛП

При наличии в задаче линейного программирования двух переменных, задача может быть решена графическим методом.
В системе координат X₁0X₂ находят область допустимых решений, строят вектор С и линию уровня. перемещая линию уровня по направлению С для задач на максимум, определяют наиболее удаленную от начала координат точку и ее координаты.
В случае, когда координаты этой точки нецелочисленные, в области допустимых решений строят целочисленную решетку и находят на ней такие целые числа x₁ и x₂, которые удовлетворяют системе ограничений и при которых значение целевой функции наиболее близко к экстремальному нецелочисленному решению. Координаты такой вершины являются целочисленным решением.
Аналогично решается задача на минимум. Целочисленному минимуму целевой функции будет соответствовать координаты вершины целочисленной решетки, лежащей в области допустимых решений, наиболее близкой к началу координат в направлении вектора С.

Задача целочисленного линейного программирования формулируется следующим образом: найти максимум (минимум) линейной целевой функции:

Z = ∑c_jx_j→max(min)
на множестве, задаваемом ограничениями:

∑a_ijx_j, i=1,m.
х_j≥0, j=1,n,
х_j – целые числа,

Решение задачи целочисленного программирования с двумя переменными методом ветвей и границ

Графическое решение задачи параметрического ЛП с двумя переменными. (Параметр находится в целевой функции). Экономическая трактовка задачи (для задачи оптимального производственного планирования)

22) Поставить (решать не нужно!) задачу двухкритериальной оптимизации по заданной текстовой задаче и двум заданным критериям. (Текстовая задача может быть задачей оптимального производственного планирования или транспортной задачей)

Решение задачи управления дискретной динамической системой методом динамического программирования (ограничения в задаче имеют тот же вид, как в задаче распределения капитальных вложений)

Доказать, что в случае отсутствия вырождения в задаче линейного программирования на нахождение минимума линейной функции преобразования по симплекс-методу приводят к конечной последовательности монотонно убывающих значений линейной функции.

В частном случае общей задачи ЛП система уравнений имеет предпочитаемый вид, при этом правые части всех уравнений неотрицательны. Для того чтобы при последовательном исключении неизвестных для приведения СЛАУ к предпочитаемому виду или перехода от одного предпочитаемого вида к другому свободные члены всех уравнений системы оставались неотрицательными, необходимо руководствоваться следующими правилами выбора разрешающей неизвестной и разрешающего уравнения. В качестве разрешающей неизвестной можно принять любую неизвестную, при которой есть хоть один положительный коэффициент, а затем в качества разрешающего уравнения следует взять то уравнение, которое соответствует наименьшему среди отношений свободных членов уравнений к соответствующим положительным коэффициентам при выбранной неизвестной в этих уравнениях. СЛАУ подвергается симплексным преобразованиям, если процесс исключения неизвестных осуществляется в соответствии с указанными правилами выбора разрешающей неизвестной и разрешающего уравнения. Может случиться, что указанное минимальное отношение достигается при нескольких значениях индекса i. Тогда любое из соответствующих им уравнений можно принять за разрешающее. Принято говорить в этом случае, что рассматриваемая СЛАУ является вырожденной. Вырожденной СЛАУ называют такую систему, у которой в какой-либо предпочитаемой форме хотя бы один свободный член ранен нулю. Остается заметить, что СЛАУ не будет иметь ни одного неотрицательного решения, если в процессе симплексных преобразований в ней появится уравнение, в котором свободный член строго положителен, а среди коэффициентов при неизвестных нет ни одного положительного. Если в процессе решения задачи ЛП симплекс-методом найдется хотя бы одна свободная неизвестная x_j такая, что ∆_j>0, а коэффициенты , то задача будет неразрешимой в силу неограниченности целевой функции на множестве допустимых решений.

25.В каком случае задача оптимального производственного планирования не имеет оптимального плана? Ответ обосновать.

«задача оптимального производственного планирования» - «линейного производства»

(«≤», max).

Отсутствие оптимального решения – неограниченность целевой функции.

Х₃ Х₅ Х₇

Х₁ 300 1 -1 0 0

Х₅ 250 0 -3 1 0

Х₇ 0 -4 0 1

250 = - 3Х₃+Х₅

Х₅=250 + 3Х₃

Отсутствие оптим реш – неограничен целевой функции. Отсутствие конечного оптимума (F_max=∞ или F_min=-∞). Вывод: Если на к-либо шаге получаем, что во всех уравнениях системы бесконечны оценочные отношения той переменной, которая переводится в основные, то задача не имеет конечного оптимума (F_max=∞, если задача на отыскание макимума, и F_min=-∞, если задача на отыскание минимума). если система ограничений непротиворечива, то выполнение конечного числа последовательных шагов симплексного метода приводит к нахождению оптимального решения задачи (оно может быть неединственным), либо к установлению того факта, что линейная функция не имеет конечного оптимума.

26.В каком случае при решении задачи линейного программирования симплекс-методом значения линейной функции двух последовательных планов могут совпасть? Ответ обосновать

П₀ Х₀ Х₃ Х₅ Х₇ β

Х₁ 1 -1 0 0

Х₅ * 0 -3 1 0

Х₇ 0 -4 0 1

1240 -10 -10/3

1240 – β • * ≠ 0

Значения линейной функции двух последовательных планов могут совпадать, если среди базисного плана есть 0 – вырожденный план