4 Методические указания

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

Решение задачи ЛП включает следующие этапы:

1. определение переменных задачи;

2. определение ограничений в виде линейных уравнений или неравенств;

3. задание целевой функции, подлежащей минимизации или максимизации;

4. решение задачи каким-либо методом.

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

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

Задача ЛП с двумя неизвестными имеет следующий вид:

среди неизвестных и , удовлетворяющих системе

найти такие, при которых целевая функция

достигает наименьшего (наибольшего) значения.

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

Рисунок 1

С учетом этого задачу можно сформулировать так: среди всех точек выпуклого многоугольника М найти такую, координаты которой минимизируют (максимизируют) целевую функцию

Если зафиксировать какое-нибудь значение функции Z=d, то получится линейное уравнение с двумя неизвестными графиком которого является прямая плоскости. При изменении d от до + прямая смещаясь параллельно самой себе (рис.1), при некотором значении достигает многоугольника М и имеет с ним общую точку А (точка входа), а затем, пройдя многоугольник М, при некотором значении будет иметь с ним последнюю общую точку В (точка выхода).

Целевая функция достигает наименьшего значения в точке входа А, а наибольшего значения в точке выхода В.

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

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

1. определить переменные задачи;

2. определить ограничения в виде линейных неравенств или уравнений;

3. задать линейную целевую функцию, подлежащую минимизации или максимизации;

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

5. построить прямую, соответствующую целевой функции;

6. параллельным переносом этой прямой найти точку входа или выхода (в зависимости от требования задачи);

7. определить координаты этой точки и вычислить в них значение целевой функции;

8. проверить оптимальность полученного решения и использование ресурсов.

Пример №1 выполнения контрольного задания

Выпускается два вида изделий А и Б. Предприятие располагает ресурсами: материальными до 300 единиц, финансовыми до 100 единиц, трудовыми до 200 единиц. Для изготовления одного изделия А необходимо 5 единиц материальных, 2 единицы финансовых и 2 единицы трудовых ресурсов, а изделия Б  5 единиц материальных, 1 единица финансовых и 4 единицы трудовых ресурсов. Прибыль от реализации одного изделия А составляет 8 условных единиц, а изделия Б  12 условных единиц. Требуется так спланировать объем выпуска продукции, чтобы прибыль была максимальной.

Сформулируем задачу математически. Обозначим через и количество изделий А и Б, которое необходимо выпускать (это искомые переменные величины). Имеющиеся ресурсы зададим в виде ограничений, выраженных неравенствами:

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

Целевая функция выражает прибыль от реализации производственной продукции и имеет вид

.

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

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

Прямую получаемую из первого неравенства, удобно провести, соединяя пару подходящих точек, например и , (рис. 2).

Рисунок 2

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

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

Полученное таким образом пространство решений  многоугольник АВСDO (заштрихован), который является областью допустимых решений (ОДР). Любая точка внутри ОДР является решением системы неравенств. Из всех этих допустимых решений нужно найти такое, при котором целевая функция принимает максимальное значение.

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

Решая эту систему, получим: ,

Вычислим значение целевой функции при этих значениях неизвестных:

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

в вершине А при величина ,

в вершине С при величина Z _С =400. Координаты вершины С есть результат пересечения прямых и и определяются решением соответствующей системы уравнений.

Проверка показала, что максимальное значение целевой функции Z=640 условных единиц достигается в вершине В, так как в соседних вершинах Z _С < Z _В и Z _А < Z _В.

Полученное решение означает, что для достижения максимальной прибыли, которая равна 640 условных единиц, необходимо производить 20 единиц изделий А и 40 штук изделий Б.

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

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

1. 5  20 + 5  40 = 300, следовательно, материальные ресурсы использованы полностью, т.е.  = 0;

2. 2  20 + 40 = 80, следовательно, финансовые ресурсы использованы не полностью, т.е.  = 20;

3. 2  20 + 4  40 = 200, следовательно, трудовые ресурсы использованы полностью, т.е.  = 0.

Таким образом, проверка использования ресурсов показывает, что материальные и трудовые ресурсы используются полностью, а 20 единиц финансовых ресурсов остаются неиспользованными.

Пример №2 выполнения контрольного задания

Предприятие выпускает два вида изделий А и Б. На изготовление изделия А требуется 1 м² металлического листа, 2 м труб и 1 чел-ч (человеко час) трудозатрат. На изделие Б  3,5 м² листа, 0,5 м труб 1 чел-ч трудозатрат. Имеется 350 м² листа, 240 м труб и 150 чел-ч трудозатрат. По плану требуется выпускать не менее 110 изделий, обеспечивая прибыль не менее 1400 единиц. Необходимо определить оптимальное число изделий каждого вида, обеспечивающее максимальную прибыль, если прибыль от реализации одного изделия А составляет 10 рублей, а от изделия Б  20 рублей.

Пусть  число изделий А, а  число изделий Б. Прибыль от реализации изделий А составляет 10 рублей, а от реализации изделий Б – рублей, т.е. необходимо максимизировать целевую функцию

.

Расход металлического листа составляет труб трудозатрат Поэтому ограничения задачи имеют вид:

Первые три неравенства описывают ограничения по ресурсам, четвертое и пятое соответственно плановое задание по общему числу изделий и ограничение по прибыли.

Рисунок 3

Система ограниченийнеравенств определяет многоугольник допустимых решений (рис. 3). Определим полуплоскости, задаваемые неравенствамиограничениями задачи. Для этого построим прямые, заменив в ограничениях знаки неравенств на знаки равенств. Чтобы выяснить, какую часть плоскости описывает неравенство, подставим в него пробную точку, например (0, 0), и установим, удовлетворяет ли она неравенству.

Первое неравенство: прямую , задаваемую уравнением =350 строим по точкам =0, =350/3,5=100 и =0, =350. Пробная точка (0, 0) удовлетворяет неравенству 0<350, т.е. она входит в искомую полуплоскость (отмечена стрелкой у прямой).

Второе неравенство: прямую, задаваемую уравнением =240, строим аналогично – при =0, =240/0,5=480 и =0, =240/2=120. Точка (0, 0) принадлежит искомой полуплоскости.

Последнее неравенство: ему соответствует прямая, задаваемая уравнением =1400. При =0 получим =1400/20=70 и при =0 получим =140. Точка (0, 0) не удовлетворяет неравенству (ложно), следовательно, необходимо взять полуплоскость, не содержащую точку (0, 0).

Пересечение полуплоскостей дает выпуклый многоугольник ABCDE. Для нахождения максимума Z надо построить линию уровня целевой функции. Пусть Z=0, тогда уравнение линии уровня будет =0. Оно описывает прямую, проходящую через начало координат параллельно прямой =1400, т. е. =–0,5 . Прямую Z перемещаем параллельно самой себе до величины Z₁, т. е. до тех пор, пока она не выйдет из многоугольника. Получаем точку С, где пересекаются прямые:

Решая полученную систему уравнений, находим оптимальное решение  координаты точки С: =70, =80. Вычислим максимальное значение целевой функции

рублей.

Замечание. Допустим, что в рассматриваемой задаче требовалось бы найти минимум целевой функции

.

В этом случае линия целевой функции совпала бы с прямой =1400 , т.е. все точки отрезка АЕ являлись бы оптимальными решениями (бесчисленное множество решений).

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

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

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

Таким образом, симплекс-метод предполагает следующие процедуры:

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

2. Выбрать свободные (небазисные) и базисные (несвободные) переменные. Выразить базисные через свободные переменные.

3. Определить начальное допустимое базисное решение путем приравнивания к нулю небазисных переменных.

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

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

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

6. Найти новое базисное решение, соответствующее новым составам небазисных и базисных переменных. Перейти к пункту 4.

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

Решим симплекс-методом задачу, изложенную в примере 1.

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

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

Изменим задачу максимизации на задачу минимизации, приняв целевую функцию в виде

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

В качестве начального допустимого базисного решения возьмем такое, которое соответствует нулевым значениям свободных переменных, т. е. Тогда Этому решению соответствует нулевое значение целевой функции Z=0 и точка О в начале координат на рис. 2.

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

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

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

Из первого уравнения следует, что можно увеличить до значения =60, так как при большей величине базисная переменная станет отрицательной. Однако при данном значении базисная переменная в третьем уравнении станет отрицательной, что недопустимо. При исключении базисной переменной во втором уравнении свободная переменная =100 что также приводит к отрицательному значению Наибольшее значение =50 определяется из третьего уравнения при =0.

Величина из третьего уравнения выражается по формуле

Подставляя величину в первое и второе уравнения, получаем

Таким образом, новое базисное решение:

.

Значение целевой функции выразим через свободные переменные, заменив , получим

При =0 и =0 величина Z=600.

Новое решение лучше предыдущего, поскольку значение целевой функции уменьшилось с 0 до 600. Этому решению соответствует точка A на рис. 2.

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

Следующий шаг начинается с выбора нового базиса. Быстрее всех нулевого значения достигнет переменная =0 при =20. Дальнейшее увеличение поэтому невозможно. Величина определяется по аналогии с определением величины на предыдущем шаге и будет равна:

Тогда переменные и определяются из уравнений:

Следовательно, получаем новое решение, соответствующее значениям и определяемое соотношениями:

Значение целевой функции определим из выражения

,

т. е. Z=640.

Поскольку в выражении целевой функции коэффициенты при и положительные, то при увеличении значений этих переменных целевая функция возрастает. Следовательно, минимальное значение целевой функции Z_min=640 соответствует нулевым значениям переменных и , а полученное решение является оптимальным (см. вершину B на рис. 2).

Таким образом, для получения максимальной прибыли при заданных ресурсах необходимо запланировать изготовление изделий А в количестве 20 штук и изделий Б в количестве 40 штук. Суммарная прибыль равна 640 единицам.

Значения переменных , и показывают как использованы ресурсы: так как = 0 и = 0, то материальные и трудовые ресурсы используются полностью, а величина =20 означает, что 20 единиц финансовых ресурсов остаются неиспользованными.