Симплексный метод решения задач линейного программирования.

21.07.2019

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, имеем:

Симплексная таблица ЛП. В случае базисных переменных {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) = Т (столбец свободных членов).

15. Аналитические методы. Методы линейного программирования.

15.1. Аналитические методы

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

Наилучшие в определенном смысле решения задач принято называть оптимальными . Без использования принципов оптимизации в настоящее время не решается ни одна более или менее сложная проблема. При постановке и решении задач оптимизации возникают два вопроса: что и как оптимизировать?

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

Итак, пусть в результате формализации прикладной задачи установлено, что целевая функция , где множество Х – обобщение ограничений, его называют множеством допустимых решений. Существо проблемы оптимизации заключается в поиске на множестве Х – множестве допустимых решений такого решения
, при котором целевая функцияf достигает наименьшего или наибольшего значения.

Составной частью методов оптимизации является линейное программирование.

15.2. Основные понятия линейного программирования

Первое упоминание (1938 г.) о математических методах в эффективном управлении производством принадлежит советскому математику Л. В. Канторовичу. Год спустя,в 1939 г., Л. В. Канторович опубликовал работу «Математические методы организации и планирования производства» и практически применил полученные результаты. Термин «линейное программирование» ввели американские математики Дж. Данциг и Т. Купманс в конце 40-х годов. Дж. Данциг разработал математический аппарат симплексного метода решения задач линейного программирования (1951 г.). Симплексный метод находит применение для решения широкого круга задач линейного программирования и до настоящего времени является одним из основных методов.

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

быть единственным для данной задачи;

измеряться в единицах количества;

линейно зависеть от входных параметров.

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

найти экстремум целевой функции

при ограничениях в виде равенств:

(2.2)

при ограничениях в виде неравенств:

(2.3)

и условиях неотрицательности входных параметров:

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

(2.5)

при условии

где
- входные переменные;

Числа положительные, отрицательные и равные нулю.

В матричной форме эта задача может быть записана так:

Задачи линейного программирования можно решить аналитически и графически.

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

, i=1,…,m,

, j=1,…,n.

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

15.4. Общая задача линейного программирования

Необходимо максимизировать (минимизировать) линейную функцию от n переменных.

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

, i =1,…, k ,

, i =1+ k ,…, m ,

, …,

Здесь k ≤ m , r ≤ n . Стандартная задача получается как частный случай общей приk = m , r = n ; каноническая – приk =0, r = n .

Пример.

Кондитерская фабрика производит несколько сортов конфет. Назовем их условно "A", "B" и "C". Известно, что реализация десяти килограмм конфет "А" дает прибыль 90 рублей, "В" - 100 рублей и "С" - 160 рублей. Конфеты можно производить в любых количествах (сбыт обеспечен), но запасы сырья ограничены. Необходимо определить, каких конфет и сколько десятков килограмм необходимо произвести, чтобы общая прибыль от реализации была максимальной. Нормы расхода сырья на производство 10 кг конфет каждого вида приведены в таблице 1.

Таблица 1. Нормы расходов сырья

на производство

Экономико-математическая формулировка задачи имеет вид

Найти такие значения переменных Х=(х1, х2, х3) , чтобы

целевая функция

при условиях-ограничениях:

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

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

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

Алгоритм симплексного метода решения задач линейного программирования

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

Привести задачу к каноническому виду
Найти начальное опорное решение с "единичным базисом" (если опорное решение отсутствует, то задача не имеет решение ввиду несовместимости системы ограничений)
Вычислить оценки разложений векторов по базису опорного решения и заполнить таблицу симплексного метода
Если выполняется признак единственности оптимального решения, то решение задачи заканчивается
Если выполняется условие существования множества оптимальных решений, то путем простого перебора находят все оптимальные решения

Пример решения задачи симплексным методом

Пример 26.1

Решить симплексным методом задачу:

Решение:

Приводим задачу к каноническому виду.

Для этого в левую часть первого ограничения-неравенства вводим дополнительную переменную x 6 с коэффициентом +1. В целевую функцию переменная x 6 входит с коэффицентом ноль (т.е. не входит).

Получаем:

Находим начальное опорное решение. Для этого свободные (неразрешенные) переменные приравниваем к нулю х1 = х2 = х3 = 0.

Получаем опорное решение Х1 = (0,0,0,24,30,6) с единичным базисом Б1 = (А4, А5, А6).

Вычисляем оценки разложений векторов условий по базису опорного решения по формуле:

Δ k = C б X k — c k

C б = (с 1 , с 2 , ... , с m) — вектор коэффициентов целевой функции при базисных переменных
X k = (x 1k , x 2k , ... , x mk) — вектор разложения соответствующего вектора А к по базису опорного решения
С к — коэффициент целевой функции при переменной х к.

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

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

В последней строке таблицы с оценками Δ k в столбце "А 0 " записываются значения целевой функции на опорном решении Z(X 1).

Начальное опорное решение не является оптимальным, так как в задаче на максимум оценки Δ 1 = -2, Δ 3 = -9 для векторов А 1 и А 3 отрицательные.

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

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

Приращение целевой функции находится по формуле: .

Вычисляем значения параметра θ 01 для первого и третьего столбцов по формуле:

Получаем θ 01 = 6 при l = 1, θ 03 = 3 при l = 1 (таблица 26.1).

Находим приращение целевой функции при введении в базис первого вектора ΔZ 1 = — 6*(- 2) = 12, и третьего вектора ΔZ 3 = — 3*(- 9) = 27.

Следовательно, для более быстрого приближения к оптимальному решению необходимо ввести в базис опорного решения вектор А3 вместо первого вектора базиса А6, так как минимум параметра θ 03 достигается в первой строке (l = 1).

Производим преобразование Жордана с элементом Х13 = 2, получаем второе опорное решение Х2 = (0,0,3,21,42,0) с базисом Б2 = (А3, А4, А5). (таблица 26.2)

Это решение не является оптимальным, так как вектор А2 имеет отрицательную оценку Δ2 = — 6. Для улучшение решения необходимо ввести вектор А2 в базис опорного решения.

Определяем номер вектора, выводимого из базиса. Для этого вычисляем параметр θ 02 для второго столбца, он равен 7 при l = 2. Следовательно, из базиса выводим второй вектор базиса А4. Производим преобразование Жордана с элементом х 22 = 3, получаем третье опорное решение Х3 = (0,7,10,0,63,0) Б2 = (А3, А2, А5) (таблица 26.3).

Это решение является единственным оптимальным, так как для всех векторов, не входящих в базис оценки положительные

Δ 1 = 7/2, Δ 4 = 2, Δ 6 = 7/2.

Ответ: max Z(X) = 201 при Х = (0,7,10,0,63).

Метод линейного программирования в экономическом анализе

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

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

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

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

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

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

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

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

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

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

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

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

Среди оптимизационных задач в теории принятия решений наиболее известны задачи линейного программирования, в которых максимизируемая функция F(X) является линейной, а ограничения А задаются линейными неравенствами. Начнем с примера (см. ).

Производственная задача. Цех может производить стулья и столы. На производство стула идет 5 единиц материала, на производство стола - 20 единиц (футов красного дерева). Стул требует 10 человеко-часов, стол - 15. Имеется 400 единиц материала и 450 человеко-часов. Прибыль при производстве стула - 45 долларов США, при производстве стола - 80 долларов США. Сколько надо сделать стульев и столов, чтобы получить максимальную прибыль?

Обозначим: Х 1 - число изготовленных стульев, Х 2 - число сделанных столов. Задача оптимизации имеет вид:

45 Х 1 + 80 Х 2 → max ,

5 Х 1 + 20 Х 2 ≤ 400 ,

10 Х 1 + 15 Х 2 ≤ 450 ,

В первой строке выписана целевая функция - прибыль при выпуске Х 1 стульев и Х 2 столов. Ее требуется максимизировать, выбирая оптимальные значения переменных Х 1 и Х 2 . При этом должны быть выполнены ограничения по материалу (вторая строчка) - истрачено не более 400 футов красного дерева. А также и ограничения по труду (третья строчка) - затрачено не более 450 часов. Кроме того, нельзя забывать, что число столов и число стульев неотрицательны. Если Х 1 = 0, то это значит, что стулья не выпускаются. Если же хоть один стул сделан, то Х 1 положительно. Но невозможно представить себе отрицательный выпуск - Х 1 не может быть отрицательным с экономической точки зрения, хотя с математической точки зрения такого ограничения усмотреть нельзя. В четвертой и пятой строчках задачи и констатируется, что переменные неотрицательны.

Условия производственной задачи можно изобразить на координатной плоскости. Будем по горизонтальной оси абсцисс откладывать значения Х 1 , а по вертикальной оси ординат - значения Х 2 . Тогда ограничения по материалу и последние две строчки оптимизационной задачи выделяют возможные значения (Х 1 , Х 2) объемов выпуска в виде треугольника (рис.1).

Таким образом, ограничения по материалу изображаются в виде выпуклого многоугольника, конкретно, треугольника. Этот треугольник получается путем отсечения от первого квадранта примыкающей к началу координат зоны. Отсечение проводится прямой, соответствующей второй строке исходной задачи, с заменой неравенства на равенство. Прямая пересекает ось Х 1 , соответствующую стульям, в точке (80,0). Это означает, что если весь материал пустить на изготовление стульев, то будет изготовлено 80 стульев. Та же прямая пересекает ось Х 2 , соответствующую столам, в точке (0,20). Это означает, что если весь материал пустить на изготовление столов, то будет изготовлено 20 столов. Для всех точек внутри треугольника выполнено неравенство, а не равенство - материал останется.

Аналогичным образом можно изобразить и ограничения по труду (рис.2).

Таким образом, ограничения по труду также изображаются в виде треугольника. Этот треугольник также получается путем отсечения от первого квадранта примыкающей к началу координат зоны. Отсечение проводится прямой, соответствующей третьей строке исходной задачи, с заменой неравенства на равенство. Прямая пересекает ось Х 1 , соответствующую стульям, в точке (45,0). Это означает, что если все трудовые ресурсы пустить на изготовление стульев, то будет сделано 45 стульев. Та же прямая пересекает ось Х 2 , соответствующую столам, в точке (0,30). Это означает, что если всех рабочих поставить на изготовление столов, то будет сделано 30 столов. Для всех точек внутри треугольника выполнено неравенство, а не равенство - часть рабочих будет простаивать.

Мы видим, что очевидного решения нет - для изготовления 80 стульев есть материал, но не хватает рабочих рук, а для производства 30 столов есть рабочая сила, но нет материала, Значит, надо изготавливать и то, и другое. Но в каком соотношении?

Чтобы ответить на этот вопрос, надо "совместить" рис.1 и рис.2, получив область возможных решений, а затем проследить, какие значения принимает целевая функция на этом множестве (рис.3).

Таким образом, множество возможных значений объемов выпуска стульев и столов (Х 1 , Х 2), или, в других терминах, множество А, задающее ограничения на параметр управления в общей оптимизационной задаче, представляет собой пересечение двух треугольников, т.е. выпуклый четырехугольник, показанный на рис.3. Три его вершины очевидны - это (0,0), (45,0) и (0,20). Четвертая - это пересечение двух прямых - границ треугольников на рис.1 и рис.2, т.е. решение системы уравнений

5 Х 1 + 20 Х 2 = 400 ,

10 Х 1 + 15 Х 2 = 450 .

Из первого уравнения: 5 Х 1 = 400 - 20 Х 2 , Х 1 = 80 - 4 Х 2 . Подставляем во второе уравнение: 10 (80 - 4 Х 2) + 15 Х 2 = 800 - 40Х 2 + 15 Х 2 = 800 - 25 Х 2 = 450, следовательно, 25 Х 2 = 350, Х 2 = 14, откуда Х 1 = 80 - 4 х 14 = 80 -56 = 24. Итак, четвертая вершина четырехугольника - это (24, 14).

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

Целевая функция 45 Х 1 + 80 Х 2 принимает минимальное значение, равное 0, в вершине (0,0). При увеличении аргументов эта функция увеличивается. В вершине (24,14) она принимает значение 2200. При этом прямая 45 Х 1 + 80 Х 2 = 2200 проходит между прямыми ограничений 5 Х 1 + 20 Х 2 = 400 и 10 Х 1 + 15 Х 2 = 450, пересекающимися в той же точке. Отсюда, как и из непосредственной проверки двух оставшихся вершин, вытекает, что максимум целевой функции, равный 2200, достигается в вершине (24,14).

Таким образом, оптимальный выпуск таков: 24 стула и 14 столов. При этом используется весь материал и все трудовые ресурсы, а прибыль равна 2200 долларам США.

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

45 Х 1 + 80 Х 2 → max , 400 W 1 + 450 W 2 → min ,

5 Х 1 + 20 Х 2 ≤ 400 , 5 W 1 + 10 W 2 ≥ 45,

10 Х 1 + 15 Х 2 ≤ 450 , 20 W 1 + 15 W 2 ≥ 80,

Х 1 ≥ 0 , W 1 ≥ 0,

Х 2 ≥ 0 . W 2 ≥ 0.

Почему двойственная задача столь важна? Можно доказать, что оптимальные значения целевых функций в исходной и двойственной задачах совпадают (т.е. максимум в исходной задаче совпадает с минимумом в двойственной). При этом оптимальные значения W 1 и W 2 показывают стоимость материала и труда соответственно, если их оценивать по вкладу в целевую функцию. Чтобы не путать с рыночными ценами этих факторов производства, W 1 и W 2 называют "объективно обусловленными оценками" сырья и рабочей силы.

Линейное программирование как научно-практическая дисциплина. Из всех задач оптимизации задачи линейного программирования выделяются тем, что в них ограничения - системы линейных неравенств или равенств. Ограничения задают выпуклые линейные многогранники в конечном линейном пространстве. Целевые функции также линейны.

Впервые такие задачи решались советским математиком Л.В. Канторовичем (1912-1986) в 1930-х годах как задачи производственного менеджмента с целью оптимизации организации производства и производственных процессов, например, процессов загрузки станков и раскройки листов материалов. После второй мировой войны аналогичными задачами занялись в США. В 1975 г. Т. Купманс (1910-1985, родился в Нидерландах, работал в основном в США) и академик АН СССР Л.В. Канторович были награждены Нобелевскими премиями по экономике.

Рассмотрим несколько задач линейного программирования.

Задача об оптимизации смеси (упрощенный вариант). На химическом комбинате для оптимизации технологического процесса надо составить самую дешевую смесь, содержащую необходимое количество определенных веществ (обозначим их Т и Н). Энергетическая ценность смеси (в калориях) должна быть не менее заданной. Пусть для простоты смесь составляется из двух компонентов - К и С. Сколько каждого из них взять для включения в смесь? Исходные данные для расчетов приведены в табл.3.

Табл.3. Исходные данные в задаче об оптимизации смеси.

3,8 К + 4,2 С → min ,

0,10 К + 0,25 С ≥ 1,00 ,

1,00 К + 0,25 С ≥ 5,00 ,

110,00 К + 120,00 С ≥ 400,00 ,

Ее графическое решение представлено на рис.4.

Рис.4. Графическое решение задачи об оптимизации смеси.

На рис.4 ради облегчения восприятия четыре прямые обозначены номерами (1) - (4). Прямая (1) - это прямая 1,00К + 0,25С = 5,00 (ограничение по веществу Н). Она проходит, как и показано на рисунке, через точки (5,0) на оси абсцисс и (0,20) на оси ординат. Обратите внимание, что допустимые значения параметров (К, С) лежат выше прямой (1), в отличие от ранее рассмотренных случаев в предыдущей производственной задаче.

Прямая (2) - это прямая 110,00 К + 120,00 С = 400,00 (ограничение по калориям). Обратим внимание, что в области неотрицательных С она расположена всюду ниже прямой (1). Действительно, это верно при К=0, прямая (1) проходит через точку (0,20), а прямая (2) - через точку (0, 400/120). Точка пересечения двух прямых находится при решении системы уравнений

1,00 К + 0,25 С = 5,00 ,

110,00 К + 120,00 С = 400,00 .

Из первого уравнения К = 5 - 0,25 С. Подставим во второе: 110 (5- 0,25 С) + 120 С = 400, откуда 550 - 27,5 С + 120 С = 400. Следовательно, 150 = - 92,5 С, т.е. решение достигается при отрицательном С. Это и означает, что при всех положительных С прямая (2) лежит ниже прямой (1). Значит, если выполнено ограничения по Н, то обязательно выполнено и ограничение по калориям. Мы столкнулись с новым явлением - некоторые ограничения с математической точки зрения могут оказаться лишними. С экономической точки зрения они необходимы, отражают существенные черты постановки задачи, но в данном случае внутренняя структура задачи оказалась такова, что ограничение по калориям не участвует в формировании допустимой области параметров и нахождении решения.

Прямая (4) - это прямая 0,1 К + 0,25 С = 1 (ограничение по веществу Т). Она проходит, как и показано на рисунке, через точки (10,0) на оси абсцисс и (0,4) на оси ординат. Обратите внимание, что допустимые значения параметров (К,С) лежат выше прямой (4), как и для прямой (1).

Следовательно, область допустимых значений параметров (К, С) является неограниченной сверху. Из всей плоскости она выделяется осями координат (лежит в первом квадранте) и прямыми (1) и (4) (лежит выше этих прямых). Область допустимых значений параметров (К, С) можно назвать "неограниченным многоугольником". Минимум целевой функции 3,8 К + 4,2 С может достигаться только в вершинах этого "многоугольника". Вершин всего три. Это пересечения с осями абсцисс (10,0) и ординат (0,20) прямых (1) и (4) (в каждом случае из двух пересечений берется то, которое удовлетворяет обоим ограничениям). Третья вершина - это точка пересечения прямых (1) и (4), координаты которой находятся при решении системы уравнений

0,10 К + 0,25 С = 1,00 ,

1,00 К + 0,25 С = 5,00 .

Из второго уравнения К = 5 - 0,25 С, из первого 0,10 (5 - 0,25 С) + 0,25 С = 0,5 - 0,025 С + 0,25 С = 0,5 + 0,225 С = 1, откуда С = 0,5/0,225 = 20/9 и К = 5 - 5/9 = 40/9. Итак, А = (40/9; 20/9).

Прямая (3) на рис.4 - это прямая, соответствующая целевой функции 3,8 К + 4,2 С. Она проходит между прямыми (1) и (4), задающими ограничения, и минимум достигается в точке А, через которую и проходит прямая (3). Следовательно, минимум равен 3,8х40/9 + 4,2х20/9 = 236/9. Задача об оптимизации смеси полностью решена.

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

3,8 К + 4,2 С → min , W 1 + 5 W 2 + 400 W 3 → max ,

0,10 К + 0,25 С ≥ 1,00 , 0,1 W 1 + 1,10 W 2 + 110 W 3 ≤ 3,8 ,

1,00 К + 0,25 С ≥ 5,00 , 0,25W 1 + 0,25 W 2 + 120 W 3 ≤ 4,2 ,

110,00 К + 120,00 С ≥ 400,00 , W 1 ≥ 0 ,

К ≥ 0 , W 2 ≥ 0 ,

С ≥ 0 . W 3 ≥ 0 .

Минимальное значение в прямой задаче, как и должно быть, равно максимальному значению в двойственной задаче, т.е. оба числа равны 236/9. Интерпретация двойственных переменных: W 1 - "стоимость" единицы вещества Т, а W 2 - "стоимость" единицы вещества Н, измеренные "по их вкладу" в целевую функцию. При этом W 3 = 0, поскольку ограничение на число калорий никак не участвует в формировании оптимального решения. Итак, W 1 , W 2 , W 3 - это т.н. объективно обусловленные оценки (по Л.В. Канторовичу) ресурсов (веществ Т и Н, калорий).

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

Табл.4. Производственные мощности (в шт.)

	Кофеварки	Самовары
Штамповка


Объем выпуска
Удельная прибыль (на одно изделие)

При этом штамповка и отделка проводятся на одном и том же оборудовании. Оно позволяет штамповать за заданное время или 20000 кухонь, либо 30000 кофеварок, либо и то, и другое, не в меньшем количестве. А вот сборка проводится на отдельных участках.

Задача линейного программирования имеет вид:

Х 1 ≥ 0 , Х 2 ≥ 0 , Х 3 ≥ 0 , (0)

Х 1 / 200 + Х 2 / 300 + Х 3 / 120 ≤ 100 , (1)

Х 1 / 300 + Х 2 / 100 + Х 3 / 100 ≤ 100 , (2)

Х 1 / 200 ≤ 100 , (3)

Х 2 / 120 ≤ 100 , (4)

Х 3 / 80 ≤ 100 , (5)

F = 15 Х 1 + 12 Х 2 + 14 Х 3 → max .

Здесь:
(0) - обычное в экономике условие неотрицательности переменных,
(1) - ограничение по возможностям штамповки (выраженное для облегчения восприятия в процентах),
(2) - ограничение по возможностям отделки,
(3) - ограничение по сборке для кухонь,
(4) - то же для кофемолок,
(5) - то же для самоваров (как уже говорилось, все три вида изделий собираются на отдельных линиях).

Наконец, целевая функция F - общая прибыль предприятия.

Заметим, что неравенство (3) вытекает из неравенства (1), а неравенство (4) - из (2). Поэтому неравенства (3) и (4) можно сразу отбросить.

Отметим сразу любопытный факт. Как будет установлено, в оптимальном плане Х 3 = 0, т.е. самовары выпускать невыгодно.

Линейное программирование сформировалось как отдельный раздел прикладной математики в 40 – 50-х гг. ХХ в. благодаря работам советского ученого, лауреата Нобелевской премии Л.В. Канторовича. В 1939 году им была опубликована работа «Математические методы организации и планирования производства», в которой он с использованием математики решил экономические задачи о наилучшей загрузке машин, раскрое материалов с наименьшими расходами, распределении грузов по нескольким видам транспорта и другие, предложив метод разрешающих множителей 8 .

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

Понятие линейного программирования было введено американским математиком Д. Данцигом, который в 1949 г. предложил алгоритм решения задачи линейного программирования, получивший название «симплексный метод».

Математическое программирование, в которое входит линейное программирование, в настоящее время является одним из направлений исследования операций. В зависимости от вида решаемых задач в нем выделяют такие области, как линейное, нелинейное, дискретное, динамическое программирование и др. Термин «программирование» введен в связи с тем, что неизвестные переменные, которые находятся в процессе решения задачи, обычно определяют программу или план работы некоторого экономического объекта.

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

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

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

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

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

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

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

Общая задача линейного программирования (ЗЛП) состоит в нахождении экстремального значения (максимума или минимума) линейной функции, называемой целевой 10:

от n переменных x 1 , x 2 , …, х n при наложенных функциональных ограничениях:

(3.2)

и прямых ограничениях (требовании неотрицательности переменных)

, (3.3)

где a ij , b i , c j – заданные постоянные величины.

В системе ограничений (3.2) знаки «меньше или равно», «равно», «больше или равно» могут встречаться одновременно.

ЗЛП в более краткой записи имеет вид:

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

;

Вектор `Х = (x 1 , x 2 , …, х n ) компоненты которого удовлетворяют функциональным и прямым ограничениям задачи называют планом (или допустимым решением ) ЗЛП.

Все допустимые решения образуют область определения задачи линейного программирования, или область допустимых решений (ОДР). Допустимое решение, которое доставляет максимум или минимум целевой функции f (`X ), называется оптимальным планом задачи и обозначается f (`X * ), где ` Х * =(x 1 * , x 2 * , …, х n * ).