Задание 1. Применение методов линейного программирования

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

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

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

Требуется:

• 1) Построить математическую модель задачи.
• 2) Выбрать метод решения и привести задачу к канонической форме.
• 3) Решить задачу (симплекс-методом).
• 4) Дать геометрическую интерпретацию решения.
• 5) Проанализировать результаты решения.
• 6) Составить к данной задаче двойственную и, используя соответствие переменных, выписать ответ двойственной задачи.
• 7) Решить двойственную задачу (двойственным симплекс-методом).
• 8) Дать экономическую интерпретацию двойственных оценок.

Решение:

1) Чтобы сформулировать эту задачу математически, обозначим через, и количество единиц продукции соответственно видов A, B и C, которое необходимо выпускать для получения максимальной прибыли. Согласно условиям задачи прибыль от выпуска продукции вида, А составит 4 ден.ед., от вида В — 5 ден.ед., от вида С — 1 ден.ед. Следовательно, целевая функция прибыли z выразится формулой:

.

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

.

Согласно условиям задачи на изготовление всей продукции будет использовано ед. сырья I вида, запасы которого составляют 7 ед., а так как по условия запасы сырья I вида необходимо израсходовать полностью, то должно выполняться равенство: .

На изготовление всей продукции будет использовано ед. сырья II вида, запасы которого составляют 14 ед., тогда должно выполняться неравенство: .

Для сырья III вида должно выполняться неравенство: .

Следовательно, система ограничений будет иметь вид:

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

2) Целевая функция и неравенства являются линейными, следовательно, это задача линейного программирования. Приведем ее к каноническому виду, прибавляя к левым частям второго и третьего ограничений по одной дополнительной неотрицательной переменной (соответственно). При этом получим равенства. Первое ограничение оставим без изменений, так как оно уже является равенством. Дополнительные переменные введем в целевую функцию с нулевыми коэффициентами. Целевая функция при этом не изменится, так как исследуется на максимум. В результате получим следующую каноническую форму задачи линейного программирования:

.

при ограничениях.

.

3) Решим задачу симплекс-методом. Найдем начальный опорный план задачи. Все ограничения системы имеют предпочтительный вид. Базис образуют переменные,. Для получения опорного решения приравняем свободные переменные к нулю, а базисные — свободным членам, то есть, ,. Тогда начальный опорный план задачи:, а значение целевой функции в этой точке .

Выразим целевую функцию через свободные переменные. Составим исходную симплекс-таблицу.

Так как в z-строке есть отрицательные, то опорный план не является оптимальным. Ведущий столбец первый, так как ему соответствует отрицательный элемент -4. Ведущую строку выбираем по минимальному симплексному отношению:. Таким образом, вторая строка ведущая, — ведущий элемент. Значит переменная будет включена в базис, а переменная из базиса выводится.

Каждый элемент ведущей строки разделим на ведущий элемент. Запишем полученную строку в новую симплекс таблицу. Остальные элементы ведущего столбца делаем нулевыми. Первую строку переписываем, так как элемент её первого столбца уже равен 0. Чтобы в третьей строке вместо 1 получить 0, необходимо каждый элемент строки, полученной из ведущей, умножить на (-1) и прибавить почленно к 1-й строке. Чтобы в z-строке вместо -4 получить 0 нужно строку, полученную из ведущей, умножить на 4 и прибавить к z-строке. Таблицы пересчитываем до тех пор, пока в z-строке все элементы (не считая значения) станут неотрицательными.

Так как в z-строке все элементы больше или равны нулю, то найден оптимальный план:, .

Оптимальный план не единственный, так как в z-строке есть нули, соответствующие не только базисным переменным. Найдем второй оптимальный план.

.

Общее решение запишем как выпуклую линейную комбинацию опорных решений и: , где и,. Следовательно, .

4) Выразим из первого уравнения системы ограничений базисную переменную: ,, , следовательно,. Следовательно, система ограничений примет вид:

.

Полученную графическим способом.

(рисунок 1).

Построим вектор-градиент. Перпендикулярно к нему строим одну из прямых семейства. Например, при. Параллельно перемещаем ее в направлении вектора до последней точки пересечения с областью допустимых решений. В нашем случае прямая совпадает с прямой. Поэтому искомых точек экстремума будет множество: все точки отрезка. Координаты точек и можно определить по рисунку:

.

где и, .

• 5) Итак, чтобы получить максимальную прибыль, равную 47 ден.ед. необходимо: 1. По выпускать 4 ед. продукции вида А, 6 ед. продукции вида В и 1 ед. продукции вида С. Все сырье будет использовано.
• 2. По — выпускать 3 ед. продукции вида А, 7 ед. продукции вида В и не выпускать продукцию вида С. При этом 1 ед. сырья вида будет не использована, так как .
• 6)Составим к данной задаче двойственную. Каждому ограничению исходной задачи поставим в соответствие двойственную переменную, .

И наоборот, число переменных исходной задачи равно числу ограничений двойственной.

Зная оптимальное решение прямой задачи, выпишем ответ двойственной задачи. Базисным переменным прямой задачи, поставим в соответствие свободные переменные двойственной задачи .

Перепишем их под последнюю симплекс-таблицу:

Решение двойственной задачи находим по последней симплекс-таблице в строке оценок.

(так как в целевой функции коэффициент при равен 1).

(так как в целевой функции коэффициент при равен 0).

(так как в целевой функции коэффициент при равен 0).

.

7) Решим двойственную задачу двойственным симплекс-методом. Приведем задачу к каноническому виду:

Задача имеет базисное решение (псевдо-план), .

Поскольку в столбце значений свободных членов все элементы больше или равны нулю, то найден оптимальный план: .

Решение единственно, так как нулевые элементы z-строки соответствуют только базисным переменным, , .

8) Дадим экономическую интерпретацию двойственных оценок.

Переменные обозначают оценки единицы сырья I, II и III видов соответственно. Так как, то сырье I и III видов (по теореме о дополняющей нежесткости) полностью используется при оптимальном плане производства продукции., значит сырье IIго вида используется не полностью. Поэтому двойственные оценки определяют дефицитность используемого сырья, то есть сырье I и III видов является дефицитным, а IIго вида — нет.

Увеличение сырья I-го вида на 1 ед. приведет к тому, что появится возможность найти оптимальный план производства продукции, при котором общая стоимость возрастет на ден.ед. и станет равной 47+1=48 ден.ед. Аналогично, увеличение сырья III-го вида на 1 ед. приведет к увеличению общей стоимости на 4 ден.ед.: 47+4=51 ден.ед.