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

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

Линейное программирование (ЛП) – один из первых и наиболее подробно изученных разделов математического программирования. Именно линейное программирование явилось тем разделом, с которого и начала развиваться сама дисциплина "математическое программирование". Термин "программирование" в названии дисциплины ничего общего с термином "программирование (т.е. составление программы) для ЭВМ" не имеет, т.к. дисциплина "линейное программирование" возникла еще до того времени, когда ЭВМ стали широко применяться для решения математических, инженерных, экономических и др. задач.

Термин "линейное программирование" возник в результате неточного перевода английского "linear programming". Одно из значений слова "programming" - составление планов, планирование. Следовательно, правильным переводом английского "linear programming" было бы не "линейное программирование", а "линейное планирование", что более точно отражает содержание дисциплины. Однако, термины линейное программирование, нелинейное программирование, математическое программирование и т.д. в нашей литературе стали общепринятыми и поэтому будут сохранены.

Итак, линейное программирование возникло после второй мировой войны и стало быстро развиваться, привлекая внимание математиков, экономистов и инженеров благодаря возможности широкого практического применения, а также математической стройности.

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

Линейное программирование применяется при решении экономических задач, в таких задачах как управление и планирование производства; в задачах определения оптимального размещения оборудования на морских судах, в цехах; в задачах определения оптимального плана перевозок груза (транспортная задача); в задачах оптимального распределения кадров и т.д.

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

Существует несколько методов решения задач ЛП. В данной работе будут рассмотрены некоторые из них, в частности:

Графический метод решения задачи ЛП;

Симплексный метод;

Решение задачи ЛП средствами табличного процессора Excel;

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

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

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

В данной работе будет рассматриваться такой метод решения задач НП, как метод множителей Лагранжа.

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

 

4. Динамическое программирование

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

Решение задач методами динамического программирования проводится на основе сформулированного Р.Э.Беллманом принципа оптимальности: оптимальное поведение обладает тем свойством, что каким бы ни было первоначальное состояние системы и первоначальное решение, последующее решение должно определять оптимальное поведение относительно состояния, полученного в результате первоначального решения.

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

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

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

Пусть процесс оптимизации разбит на n шагов. На каждом шаге необходимо определить два типа переменных – переменную состояния S и переменную управления X. Переменная S определяет, в каких состояниях может оказаться система на данном k-м шаге. В зависимости от S на этом шаге можно применить некоторые управления, которые характеризуются переменной X. Применение управления X на k-м шаге приносит некоторый результат Wk(S,Xk) и переводит систему в некоторое новое состояние S'(S,Xk). Для каждого возможного состояния на k-м шаге среди всех возможных управлений выбирается оптимальное управление X*k такое, чтобы результат, который достигается за шаги с k-го по n-й, оказался оптимальным. Числовая характеристика этого результата называется функцией Беллмана Fk(S) и зависит от номера шага k и состояния системы S.

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

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

В общем виде задача динамического программирования формулируется следующим образом: требуется определить такое управление X*, переводящее систему из начального состояния S0 в конечное состояние Sn, при котором целевая функция F(S0,X*) принимает наибольшее (наименьшее) значение.

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

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

целевая функция является аддитивной и равна сумме целевых функций каждого шага

;

выбор управления Xk на каждом шаге зависит только от состояния системы к этому шагу Sk-1 и не влияет на предшествующие шаги (нет обратной связи);

состояние системы Sk после каждого шага управления зависит только от предшествующего состояния системы Sk-1 и этого управляющего воздействия Xk (отсутствие последействия) и может быть записано в виде уравнения состояния:

;

на каждом шаге управление Xk зависит от конечного числа управляющих переменных, а состояние системы Sk зависит от конечного числа переменных;

оптимальное управление X* представляет собой вектор, определяемый последовательностью оптимальных пошаговых управлений:

X*=(X*1, X*2, …, X*k, …, X*n),

число которых и определяет количество шагов задачи.

Условная оптимизация. Как уже отмечалось выше, на данном этапе отыскиваются функция Беллмана и оптимальные управления для всех возможных состояний на каждом шаге, начиная с последнего в соответствии с алгоритмом обратной прогонки. На последнем n-м шаге найти оптимальное управление X*n и значение функции Беллмана Fn(S) не сложно, так как

Fn(S)=max{Wn(S,Xn)},

где максимум ищется по всем возможным значениям Xn.

Дальнейшие вычисления производятся согласно рекуррентному соотношению, связывающему функцию Беллмана на каждом шаге с этой же функцией, но вычисленной на предыдущем шаге:

Fk(S)=max{Wk(S,Xk)+Fk+1(S'(S,Xk))}. (1)

Этот максимум (или минимум) определяется по всем возможным для k и S значениям переменной управления X.

Безусловная оптимизация. После того, как функция Беллмана и соответствующие оптимальные управления найдены для всех шагов с n-го по первый (на первом шаге k=1 состояние системы равно ее начальному состоянию S0), осуществляется второй этап решения задачи. Находится оптимальное управление на первом шаге X1, применение которого приведет систему в состояние S1(S,x1*), зная которое можно, пользуясь результатами условной оптимизации, найти оптимальное управление на втором шаге, и так далее до последнего n-го шага.

Лабораторная работа №1 (Задача линейного программирования)

Задание:

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

Решить задачу графическим методом;

Привести задачу к канонической форме записи;

Составить симплексную таблицу;

Произвести решение задачи симплексным методом ручным способом или с использование компьютера;

Осуществить постановку двойственной задачи ЛП;

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

Проверить результаты решения в табличном процессоре Excel;

Составить отчет с приведение результатов по каждому пункту.

Ресурсы	Запасы	Продукция
		Р1	Р2
S1	18	0.2	3
S2	13.1	0.7	2
МВ	23	2.3	2
Прибыль от единицы продукции в У.Е.		3	4

Решение:

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

 

, получим

изобразим граничные прямые.

Линейная функция F=f(x) является уравнением прямой линии c1x1 + c2x2 = const. Построим график целевой функции при f(x)=0. для построения прямой 3x1 + 4x2 = 0 строим радиус-вектор N = (3; 4) и через точку 0 проводим прямую, перпендикулярную ему. Построенную прямую F=0 перемещаем параллельно самой себе в направлении вектора N.

Рисунок 1 – Графический метод

Из рисунка 1 следует, что опорной по отношению к построенному многоугольнику решений эта прямая становится в точке B, где функция F принимает максимальное значение. Точка В лежит на пересечении прямых 0,7x1 + 2x2 ≤ 13,1 и 2,3x1 + 2x2 =23/ Для определения ее координат решим систему уравнений:

 

Оптимальный план задачи: х1 = 6.187; х2 = 4.38, подставляя значения х1 и х2 в целевую функцию, получаем Fmax= 3*6.187+4*4.38=36.08.

Таким образом, для того, чтобы получить максимальную прибыль в размере 36.06 долларов, необходимо запланировать производство 6 ед. продукции P1 и 4 ед. продукции P2.

Канонический вид задачи ЛП. Запишем в канонической форме задачу распределения ресурсов. Добавив к исходной системе ограничений неотрицательные переменные х3 ≥ 0, х4 ≥ 0, х5 ≥ 0, имеем:

При этом в далее получаемом решении переменные х3 и х4 будут соответствовать объемам неиспользованного сырья S1 и S2, а х5 – неиспользованному машинному времени.

Симплексная таблица ЛП. В случае базисных переменных {x3, x4, x5} начальная симплекс таблица будет выглядеть:

Таблица 1.

	-х1	-х2
х3 =	0,2	3	18
х4 =	0,7	2	13,1
х5 =	2,3	2	23
f(x) =	3	4

Она уже соответствует опорному плану x(0) = [0 0 18 13,1 23]Т (столбец свободных членов).

Симплексный метод решения задачи ЛП. Для того, чтобы опорный план был оптимален, при максимизации целевой функции необходимо, чтобы коэффициенты в строке целевой функции были неотрицательными, т.е. при поиске максимума мы должны освободиться от отрицательных коэффициентов в строке f(x).

Алгоритм симплекс метода.