Задача 1.2.4

Постройте двойственные задачи к задачам из упражнения №3 прошлой лекции, сформулируйте для них условия признака оптимальности. Достаточно ли этих условий, чтобы найти решения задач?

Задача из упражнения №3: Решите задачу линейного раскроя со следующими данными. Для комплектации одного изделия необходимо две детали первого типа и одна деталь второго типа. Материал поступает в виде стандартных полос длиной 1 м. Деталь первого типа требует 15 см. материала, а деталь второго типа — 35 см.

Решение:

Для данной задачи имеем 3 варианта кроя полос длиной 1 м, при которых из получающегося остатка уже ни одну заготовку не выкроить:

1) , остаток 10 см;

2) , остаток 5 см;

3) , нет остатка.

Пусть на одном технологическом цикле кроится полос по соответствующим кроям и комплектуется v изделий. Длина технологического цикла, таким образом, составляет полос. Выход заготовок на одном цикле задается вектором . Вектор k = (2,1), указывает комплектность заготовок в одном изделии. Введём переменные

При условии, что нет ограничения на длину технологического цикла, приходим к следующей математической задаче:

в векторной форме: по координатам:

или

Запишем прямую задачу как задачу на отыскание минимума некоторой функции:

Решение прямой задачи: х₁ = 0, х₂ = 1/2, х₃ = 1/2, w = 3/2.

Возвращаясь к исходным переменным, получим:

t₁ = 0, t₂ = 1, t₃ = 1, z = 2, v = 3.

Следовательно, оптимальный раскрой следующий:

1) из одной полосы выкраивается заготовки по 2-му плану, т.е. 4 заготовки по 15 см и 1 заготовка 35 см;

2) из следующей полосы выкраивается заготовки по 3-му плану, т.е. по 2 заготовки каждого вида.

Получаем, что из каждого цикла в 2 полосы выкраиваются 6 заготовок по 15 см и 3 заготовки по 35 см. Из этих заготовок можно скомплектовать 3 изделия. Остаток из каждого цикла составляет 5 см.

Записываем двойственную задачу как задачу максимизации. Имеем 4 переменные и 3 ограничения в прямой задаче. Следовательно, в двойственной задаче будет 3 переменные и 4 ограничения. По правилу построения двойственной задачи, если j-е соотношение прямой задачи является неравенством, то соответствующая переменная у_j ≥ 0, если j-е соотношение представляет собой уравнение, то переменная двойственной задачи у_j – любое число.

Следовательно, переменные y₁ и y₂ должны быть неотрицательными, а 3-я переменная y₃ может быть любым числом.

Если переменная прямой задачи х_i ≥ 0, то i-е условие системы ограничений двойственной задачи на максимум является неравенством вида ≤.

Решение двойственной задачи: y₁ = 1/2, y₂ = 1/4, y₃ = – 3/2.

Значения целевых функций на обеих задачах совпадают и равны – 3/2.

Задача 1.3.1

Сформулируйте алгоритм одного шага процедуры последовательного улучшения для задачи в канонической форме 1, воспользовавшись результатами, полученными для формы 3 (перейдите в общем виде от формы 1 к форме 3).

Решение:

Задача в форме 1 Задача в форме 3

Чтобы перейти от формы 1 к форме 3 надо ввести m вспомогательных неотрицательных переменных (по числу ограничений) .

Тогда вектор x будет иметь размерность n+m, в векторах коэффициентов на последних m местах будут стоять нули, кроме –1 на i-том месте.

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

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