2. Линейное программирование. Виды задач линейного программирования: оптимального использования ресурсов и оптимизации годовой производственной программы предприятия.

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

По типу решаемых задач методы ЛП разделяются на универсальные и специальные. С помощью универсальных методов могут решаться любые задачи линейного программирования (ЗЛП).

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

Рисунок 1 – Экстремум целевой функции

Математическая модель ЗЛП записывается следующим образом:

max (или min) Z=z(X), (1)

X  D.

ОДР может быть представлена системой линейных уравнений или неравенств.

Вектор Х=(х₁, х₂, .... x_п) является вектором управления или управляющим воздействия.

Допустимый план Х, при котором критерий оптимальности Z=z(X) достигает экстремального значения, называется оптимальным и обозначается через X*, экстремальное значение целевой функции — через Z*=z(X*).

Виды задач линейного программирования

Наиболее распространенный тип задач – задача оптимального использования ресурсов. Пусть некоторая производственная единица (цех, предприятие, объединение и т.д.), исходя из конъюнктуры рынка, технических возможностей и имеющихся ресурсов, может выпускать n различных видов продукции, известных под номерами j.

При выпуске продукции предприятие ограничено имеющимися ресурсами, количество которых обозначим m, а вектор ресурсов В = (b₁, b₂, ..., b_т). Известны также технологические коэффициенты a_ij, которые показывают норму расхода i-го ресурса на производство единицы j-ой продукции. Эффективность выпуска единицы j-и продукции характеризуется прибылью p_j.

Требуется определить план выпуска продукции Х=(х₁, х₂, ..., x_п), максимизирующий прибыль предприятия при заданных ресурсах.

Целевая функция выглядит следующим образом

, (1)

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

Часто ассортимент продукции устанавливается вышестоящей организацией, т. е. его объемы должны быть заключены в некоторых границах D^н_j и D^в_j:тогда задается следующее ограничение: (3)

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

Сохраняя прежние обозначения, запишем через α_j и с_j соответственно отпускную цену и затраты на единицу j-й продукции. В качестве критерия оптимальности могут быть приняты:

1) максимум прибыли

2) минимум затрат на производство

3) максимум выпуска в стоимостном выражении (выручки от реализации продукции)

2. Линейное программирование. Виды задач линейного программирования: оптимального использования ресурсов и размещения заказов или загрузки взаимозаменяемых групп оборудования.

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

По типу решаемых задач методы ЛП разделяются на универсальные и специальные. С помощью универсальных методов могут решаться любые задачи линейного программирования (ЗЛП).

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

Рисунок 1 – Экстремум целевой функции

Математическая модель ЗЛП записывается следующим образом:

max (или min) Z=z(X), (1) X  D.

ОДР может быть представлена системой линейных уравнений или неравенств.

Вектор Х=(х₁, х₂, .... x_п) является вектором управления или управляющим воздействия.

Допустимый план Х, при котором критерий оптимальности Z=z(X) достигает экстремального значения, называется оптимальным и обозначается через X*, экстремальное значение целевой функции — через Z*=z(X*).

Наиболее распространенный тип задач – задача оптимального использования ресурсов. Пусть некоторая производственная единица (цех, предприятие, объединение и т.д.), исходя из конъюнктуры рынка, технических возможностей и имеющихся ресурсов, может выпускать n различных видов продукции, известных под номерами j.

При выпуске продукции предприятие ограничено имеющимися ресурсами, количество которых обозначим m, а вектор ресурсов В = (b₁, b₂, ..., b_т). Известны также технологические коэффициенты a_ij, которые показывают норму расхода i-го ресурса на производство единицы j-ой продукции. Эффективность выпуска единицы j-и продукции характеризуется прибылью p_j.

Требуется определить план выпуска продукции Х=(х₁, х₂, ..., x_п), максимизирующий прибыль предприятия при заданных ресурсах.

Целевая функция выглядит следующим образом

, (1)

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

Часто ассортимент продукции устанавливается вышестоящей организацией, т. е. его объемы должны быть заключены в некоторых границах D^н_j и D^в_j:тогда задается следующее ограничение: (3)

Задача о размещении заказов или загрузке взаимозаменяемых групп оборудования. Речь идет о распределения заказов между m (i=1,…, m) предприятиями (цехами, станками, исполнителями) с различными производственными и технологическими характеристиками, но взаимозаменяемыми в смысле выполнения заказов. Требуется составить такой план размещения заказов, при котором задание было бы выполнено, а показатель эффективности достигал экстремального значения.

Сформулируем задачу математически. Пусть на т однородных группах оборудования нужно изготовить п видов продукции. План выпуска каждого вида продукции на определенный период задан набором х_j (j=1,2, …п). Мощность каждого вида оборудования ограничена и равна b_i. Известна технологическая матрица A=||a_ij||, где a_ij—число единиц j-ой продукции, выпускаемой в единицу времени на i-м оборудовании. Матрица С – матрица затрат, где c_ij—затраты, связанные с выпуском единицы j-й продукции на i-м оборудовании. Х — вектор объема выпускаемой продукции.

Модель задачи примет следующий вид:

целевая функция — минимизация расходов на реализацию всех заказов

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

а) по мощности оборудования ;

б) на выпуск продукции ;

в) условие неотрицательности .

Данную задачу называют распределительной или задачей распределения.

Если по некоторым видам продукции допускается превышение плана, то ограничение (б) примет вид .

В качестве целевой прибыли также можно принять:

а) максимум прибыли ;

б) минимум затрат станочного времени .

Т.к. любая модель содержит упрощающие предпосылки, для корректного применения полученных результатов необходимо четкое понимание сути этих упрощений, что, в конечном счете, и позволяет сделать вывод об их допустимости или недопустимости. Наиболее существенным упрощением в рассмотренных моделях является предположение о прямопропорциональной (линейной) зависимости между объемами расхода ресурсов и объемами производства, которая задается с помощью норм затрат a_ij.

2. Формы записи задач линейного программирования.

Существует 3 формы записи ЗЛП:

1. в виде функций

max( или min)Z= , max( или min)Z= ,

.

2. векторная форма

(скалярное произведение векторов)

при ограничениях A₁х₁+A₂х₂+..+A_nx_n = B

x>=0.

Где векторы С = (С_1, С₂.. С_n), Х = (Х_1, Х₂.. Х_n), и .

3. матричная форма

при ограничениях AХ = B

X>=0,

где С = (с₁, с₂,…с_n),

2. Каноническая форма задач линейного программирования.

Если все ограничения в задаче линейного программирования являются уравнениями и на все переменные x_j налагаются условия неотрицательности, то она называется задачей линейного программирования в канонической форме или канонической задачей линейного программирования (КЗЛП).

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

.

Для того чтобы перейти от ЗЛП к КЛЗП, необходимо перейти от ограничений неравенств к ограничениям равенствам и заменить переменные, которые не подчиняются условиям неотрицательности.

Правила приведения ЗЛП к каноническому виду:

1. если в ограничениях правая часть отрицательная, то следует умножить это ограничение на -1;

2. если среди ограничений имеются неравенства, то путем введения дополнительных неотрицательных переменных они преобразуются в равенства;

3. если некоторая переменная xk не имеет ограничений по знаку, то она заменяется в целевой функции и во всех ограничениях разностью между двумя новыми неотрицательными переменными: xk=x^*k - xl, где l - сводный индекс, x^*k>=, xl>=0.