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

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

Графический метод решения подобной задачи рассмотрим на примере.

Пример. Найти наибольшее и наименьшее значения функции  при выполнении ограничений:

                                          

    Вначале отметим на координатной плоскости область, в которой выполняются все указанные условия: область допустимых решений (ОДР). Для этого нарисуем границы области, которые задаются следующими линиями: . Линии 4) и 5) совпадают с координатными осями, чтобы нарисовать остальные, отметим по две точки, которые принадлежат этим линиям. Удобно в качестве таковых брать точки, расположенные на координатных осях. Чтобы их найти, приведем уравнения прямых линий к виду уравнений прямой “в отрезках”: . Прямая проходит через значения  и , отложенные на соответствующих осях. Привести уравнения прямых к уравнению “в отрезках” можно разделив обе части уравнения на число, стоящее в правой части:

                                   

Каждая прямая делит координатную плоскость на две полуплоскости, в одной из которых выполняется заданное неравенство, а в другой не выполняется. Чтобы определить, с какой стороны от прямой выполняется соответствующее неравенство, подставляем в левую часть неравенства координаты какой-нибудь точки, не лежащей на прямой, например, начало координат. Подставляя эти значения х и у в первое неравенство, получим . Значит, первое неравенство выполняется ниже прямой 1), т.к. начало координат находится под прямой 1).Отмечаем этот факт штриховкой с соответствующей стороны линии. Аналогичным образом находим полуплоскости, в которых выполняются остальные неравенства. Из рис. 1 видно, что все неравенства вместе выполняются в четырехугольнике ABCD, который и будет областью допустимых решений (ОДР).

    Чтобы найти, в какой точке этой области достигается наибольшее значение функции , а в какой – наименьшее, нанесем на координатную плоскость линии уровня функции . Линиями уровня называются линии, на которых функция принимает постоянное значение. Чтобы их нарисовать, укажем для  какое-либо значение, например,  Тогда первая линия уровня задается уравнением . Она проходит через точки (0;-1) и (2;0), изображена пунктиром. Если взять для  значение 4, получим вторую линию уровня , она проходит через точки (0;-2) и (4;0), также изображена пунктиром.

Рис.1.

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

В рассматриваемом примере ОДР замкнута, поэтому в ней можно найти и наибольшее и наименьшее значение произвольной линейной функции. Если ОДР незамкнута, то можно найти или наибольшее или наименьшее значение в зависимости от вида области.

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

Для изготовления различных изделий А и В предприятие использует три вида сырья На производство единицы изделия А требуется затратить сырья первого вида 6 кг, сырья второго вида 5 кг, третьего – 3 кг. На производство единицы изделия В соответственно 3, 10 и 12 кг. Производство обеспечено сырьем первого вида в количестве 714 кт, сырьем второго вида в количестве 910 кг и сырьем третьего вида – 948 кг. Прибыль от реализации единицы готового изделия А составляет 3 тыс. руб., изделии В 9 тыс. руб. Составить план производства изделий А и В, при котором прибыль от их реализации максимальна.

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

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

                        

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

Прямые 1), 2) и 3) предварительно приведем к виду уравнений “в отрезках”.

Рис. 2. Затем отмечаем те полуплоскости, в которых выполняются заданные неравенства. Все вместе они выполняются в области ОABCD, заштрихованной на рис.2. Затем отмечаем линии уровня целевой функции, взяв для F два значения: 180 и 360. Линии

уровня задаются уравнениями:

                                             

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

    Точка С лежит на пересечении прямых 2) и 3), поэтому для определения ее координат решаем систему:

                                                                       

    Решение системы дает  и . Следовательно, при планируемом производстве 48 единиц изделий А и 67 единиц изделий В прибыль от их реализации будет максимальной и составит  (тыс. руб.).

2. Составление и решение балансового уравнения

Балансовое уравнение появляется в линейной модели экономики (модели Леонтьева) и может применяться для анализа и планирования деятельности предприятия, отрасли, а также экономики страны в целом. Рассмотрим суть этой модели на простейшем примере.

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

или

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

Введем в рассмотрение три матрицы: матрицу А, составленную из технологических коэффициентов (технологическую матрицу или матрицу Леонтьева), матрицу X, характеризующую выпуск продукции (производственный вектор) и матрицу Y (вектор товарной продукции или конечного спроса).

Используя введенные обозначения и помня правила действий с матрицами, систему можно записать в матричном виде:

.

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

.

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

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

№ цеха Количество валовой продукции

Из нее использовано для

производства продукции

цехами

Товарная (конечная) продукция Новый товарный план
    1 2 3    
1 100 10 5 40 45 100
2 100 30 - 30 40 50
3 200 20 40 - 140 80

 

Вычислим технологические коэффициенты и составим технологическую матрицу А.

.

.

Вычислим матрицу полных производственных затрат

а) по формуле обратной матрицы:

.

б) по приближенной формуле :

Определим новый производственный план, учитывая, что

 

3. Решение прямоугольных систем линейных уравнений

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

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

Рассмотрим пример.

Найти решение системы линейных уравнений

при различных способах выбора базиса.

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

из второго и третьего уравнений системы, прибавим. Эту систему можно решать как квадратную, например, методом Гаусса. Чтобы исключить  ко второму первое, умноженное на 2, а к третьему - первое, умноженное на 4.

Чтобы исключить  из третьего уравнения, прибавим к нему второе, умноженное на (-9).

Разделим обе части третьего уравнения на (-17) и найдем . Из второго уравнения найдем . Из первого уравнения

.

Итак, решение системы при первом способе выбора базиса:

Для проверки найденное решение подставим во все уравнения исходной системы.

Раскрывая скобки и приводя подобные, убеждаемся, что все уравнения системы обращаются в тождества.

Выберем теперь в качестве базисных переменные . Перенесем в левую, a  - в правую часть полученного решения.

Запишем полученную систему в матричном виде:

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

 

Поэтому

Сделав проверку, выпишем вид решения при втором способе выбора базиса:

Чтобы найти вид решения при базисных переменных  перепишем найденное решение так:

 или .

Решая аналогично предыдущему шагу, находим

Наконец, выбираем в качестве базисных неизвестные .

Преобразуем предыдущее решение:

.

Решая выписанное матричное уравнение, найдем



Дата: 2019-02-25, просмотров: 225.