Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Часть 3
Линейное программирование
3.1. Введение в линейное программирование
Линейное программирование (ЛП) – наука о методах исследования и отыскания экстремальных (наибольших и наименьших) значений линейной функции, на неизвестные которой наложены линейные ограничения.
Эта линейная функция называется целевой, а ограничения, которые математически записываются в виде уравнений или неравенств, называются системой ограничений.
В общем виде математическая модель задачи линейного программирования (ЗЛП) записывается как
при ограничениях:
где – неизвестные; – заданные постоянные величины.
Все или некоторые уравнения системы ограничений могут быть записаны в виде неравенств.
Чтобы составить математическую модель задачи ЛП, необходимо:
ввести обозначения переменных;
учитывая ограничения в использовании экономических показателей задачи и их количественные закономерности, записать систему ограничений;
исходя из цели экономических исследований, составить целевую функцию.
3.2. Формулировка основных типов задач ЛП,
построение их математических моделей
Задачи, решаемые методами ЛП, очень разнообразны по содержанию. Но их математические модели схожи и условно объединяются в три большие группы задач:
транспортные задачи;
задачи о составлении плана;
задачи о смеси (о диете).
Рассмотрим примеры конкретных экономических задач каждого типа, подробно остановимся на построении модели каждой задачи.
3.2.1. Транспортная задача
Задача 1.
На двух торговых базах А и В имеется 30 гарнитуров мебели, по 15 на каждой. Всю мебель требуется доставить в два мебельных магазина, С и Д причем в С надо доставить 10 гарнитуров, а в Д – 20. Известно, что доставка одного гарнитура с базы А в магазин С обходится в одну денежную единицу, в магазин Д – в три денежных единицы. Соответственно с базы В в магазины С и Д: две и пять денежных единиц. Составить план перевозок так, чтобы стоимость всех перевозок была наименьшей.
Данные задачи для удобства разметим в таблице. На пересечении строк и столбцов стоят числа, характеризующие стоимость соответствующих перевозок (табл. 3.1).
Таблица 3.1
|
магазины базы |
С |
Д |
отправлено гарнитуров |
|
А |
1 |
3 |
15 |
|
В |
2 |
5 |
15 |
|
получено гарнитуров |
10 |
20 |
30 30 |
Составим математическую модель задачи.
Необходимо ввести переменные. В формулировке вопроса говорится, что необходимо составить план перевозок. Обозначим через х1, х2 количество гарнитуров, перевозимых с базы А в магазины С и Д соответственно, а через у1, у2 – количество гарнитуров, перевозимых с базы В в магазины С и Д соответственно. Тогда количество мебели, вывозимое со склада А, равно (х1 + х2), а со склада В – (у1 + у2). Потребность магазина С равна 10 гарнитурам, и в него привезли (х1 + у1) штук, т. е. х1 + у1 = 10. Аналогично, для магазина Д имеем х2 + у2 = 20. Заметим, что потребности магазинов в точности равны количеству гарнитуров, имеющихся на складах, поэтому х1 + у2 = 15 и у1 + у2 = 15. Если бы со складов вы увезли меньше, чем по 15 комплектов, то магазинам не хватило бы мебели для удовлетворения их потребностей.
Итак, переменные х1, х2, у1, у2 по смыслу задачи неотрицательны и удовлетворяют системе ограничений:
(3.1)
Обозначив через F транспортные расходы, посчитаем их. на перевозку одного комплекта мебели из А в С тратится одна ден. ед., на перевозку x1 комплектов – x1 ден. ед. Аналогично, на перевозку x2 комплектов из А в Д затратится 3x2 ден. ед.; из В в С – 2y1 ден. ед., из В в Д – 5y2 ден. ед.
Итак,
F = 1x1 + 3x2 + 2y1 + 5y2 → min (3.2)
(мы хотим, чтобы общая стоимость перевозок была минимальной).
Сформулируем задачу математически.
На множестве решений системы ограничений (3.1) найти такое решение, которое обращает в минимум целевую функцию F (3.2), или найти оптимальный план (x1, x2, y1, y2), определяемый системой ограничений (3.1) и целевой функцией (3.2).
Задача, которую мы рассмотрели может быть представлена в более общем виде, с любым числом поставщиков и потребителей.
В рассмотренной нами задаче наличие груза у поставщиков (15 + 15) равно общей потребности потребителей (10 + 20). Такая модель называется закрытой, а соответствующая задача – сбалансированной транспортной задачей.
В экономических расчетах немалую роль играют и так называемые открытые модели, в которых указанное равенство не соблюдается. Либо запас у поставщиков больше потребности у потребителей, либо спрос превышает наличие товара. заметим, что тогда в систему ограничений несбалансированной транспортной задачи наряду с уравнениями будут входить и неравенства.
Рассмотрим пример несбалансированной транспортной задачи.
Задача 2.
В пунктах А и В расположены кирпичные заводы, а в С и Д – карьеры, снабжающие их песком. потребность заводов в песке меньше, чем производительность карьеров. Известно, сколько песка нужно каждому из заводов и сколько добывается в каждом карьере. Также известна стоимость перевозки 1 т песка из каждого карьера к заводам (числа на стрелочках). Нужно так спланировать снабжение заводов песком, чтобы затраты на перевозку были наименьшими. Данные задачи на схеме.
Постоим математическую модель задачи.
Введем переменные:
x11 – количество тонн песка, перевозимого с карьера С на завод А;
x12 – с карьера С на завод А;
x21 – количество тонн песка в А с карьера Д;
x22 – количество тонн песка с карьера Д на завод В.
На завод А должно быть доставлено 40 т с обоих карьеров, значит x11 + x21 = 40, на завод В должно быть доставлено 50 т, значит x12 + x22 = 50. Из карьера С вывезено не более 70 т, т. е. x11 + x12 ≤ 70, аналогично x21 + x22 ≤ 30. Имеем систему ограничений:
(3.3)
И целевая функция F, выражающая стоимость перевозок, имеет вид
F = 2x11 + 6x12 + 5x21 + 3x22→min. (3.4)
3.2.2. Задача о составлении плана
Задача 3.
Некоторому заводу требуется составить оптимальный план выпуска двух видов изделий, которые обрабатываются на четырех видах машин. Известны определенные возможности и производительность оборудования; цена изделий, обеспечивающая прибыль заводу, составляет 4 тыс. руб. за изделие I вида, 6 тыс. руб. – за изделие II вида. Составить план выпуска этих изделий так, чтобы от реализации их завод получил наибольшую прибыль. В таблице указано время, необходимое для обработки каждого из двух видов изделий на оборудовании всех четырех видов (табл. 3.2).
Таблица 3.2
|
|
Виды машин |
|||
|
1 |
2 |
3 |
4 |
|
|
I |
1 |
0,5 |
1 |
0 |
|
II |
1 |
1 |
0 |
1 |
|
Возможное время работы машин |
18 |
12 |
12 |
9 |
Построим математическую модель.
В задаче необходимо определить план выпуска изделий, обозначим за x количество изделий I вида, за y – количество изделий II вида. Тогда посчитаем, сколько времени затратит первая машина на обработку всех производственных изделий. Она тратит одну единицу времени на одного изделие I вида, значит на x штук изделий потратит 1x ед. времени, на обработку y изделий II вида затратится 1y ед. времени. Всего резерв времени работы первой машины – 18 единиц времени. Значит, x + y ≤ 18. Аналогичные рассуждения со второй машиной, третьей и четвертой дадут систему ограничений:
(3.5)
Общая прибыль будет выражена в целевой функции:
F = 4x + 6y → max. (3.6)
Задача состоит в нахождении на множестве решений системы (3.5) такого решения, при котором значение целевой функции (3.6) было бы максимальным.
3.2.3 Задача составления смеси
Еще одна распространенная задача ЛП – задача о составлении смеси. Примером таких задач может быть задача о составлении таких смесей нефтепродуктов, которые бы удовлетворяли определенным техническим требованиям и были наиболее дешевыми по стоимости. Либо задачи о рационе, когда известна потребность в определенных веществах и содержание этих веществ в различных продуктах. Необходимо составить рацион так, чтобы удовлетворить потребности в необходимых веществах и при этом продуктовая корзина имела бы минимальную стоимость при заданных ценах на продукты.
Практически подобные задачи ставятся, к примеру, в любом животноводческом хозяйстве и имеют очень большой спектр применения.
Рассмотрим пример.
Задача 4.
Для откорма цыплят на птицефабрике в их рацион необходимо включать не менее 33 единиц вещества А, 23 единиц питательного вещества В, 12 единиц С. Для откорма используются три вида корма. Данные о содержании питательных веществ в каждом виде корма заданы таблицей. Также известна стоимость кормов. Необходимо составить наиболее дешевый рацион (табл. 3.3).
Таблица 3.3
|
Корма-продукты |
Вещества |
Стоимость 1 ед. корма |
||
|
А |
В |
С |
||
|
I |
4 |
3 |
1 |
20 |
|
II |
3 |
2 |
1 |
20 |
|
III |
2 |
1 |
2 |
10 |
Для понимания задачи можете представить себе, что вещества А, В, С – это жиры, белки, углеводы, а продукты I, II, III – то, чем кормят цыплят, например пшено, комбикорм, витаминные добавки. Тогда первая строка таблицы показывает содержание в одной единице пшена: 4 ед. белка, 3 ед. жиров, одной ед. углеводов. Вторая строка – содержание белков, жиров, углеводов в 1 ед. II продукта и т. д.
Если постановка задачи ясна, приступим к построению математической модели.
В качестве ответа на поставленную задачу мы должны предложить рацион, т. е. указать сколько и каких кормов взять, чтобы необходимое количество питательных веществ было соблюдено и при этом он стоил как можно дешевле.
Поэтому, обозначим за x1 количество кормов типа I в рационе, за x2 – количество кормов типа II и, соответственно, x3 – количество корма III в рационе. Тогда, вещества А при употреблении такого рациона цыплята получат 4x1 – при потреблении продуктов типа I, 3x2 – при потреблении II продукта, 2x3 – при потреблении III. Всего вещества А необходимо употребить по условию задачи не менее 33 единиц, следовательно 4x1 + 3x2 + 2x3 ≥ 33.
Аналогично рассуждая с веществами В и С, имеем:
3x1 + 2x2 + 1x3 ≥ 23 и x1 + x2 + 2x3 ≥ 12.
Таким образом, получим систему ограничений:
(3.7)
Переменные неотрицательны по смыслу задачи. При этом стоимость рациона выражается функцией:
F = 20x1 + 20x2 + 10x3 → min, (3.8)
т. к. 20, 20, 10 – стоимость одной ед. продуктов I, II, III типов соответственно, а в рационе их содержится x1, x2, x3 единиц.
Система ограничений (3.7) вместе с целевой функцией (3.8) и составляют математическую модель исходной задачи. Решить ее – значит найти x1, x2, x3, удовлетворяющие системе ограничений и обращающие значение функции F в минимальное.
Вопросы для самоконтроля
1. Постановка транспортной задачи. опишите построение математической модели.
2. Что такое сбалансированная и несбалансированная транспортная задача?
3. Что подсчитывается в целевой функции транспортной задачи?
4. Что отражает каждое неравенство системы ограничений задачи о плане?
5. Что отражает каждое неравенство системы ограничений задачи о смеси?
6. Что обозначают переменные в задаче о плане и задаче о смеси?
3.3. Графический способ решения задач ЛП
3.3.1. Решение систем линейных неравенств графически
Если в задаче ЛП неизвестных всего два, как, к примеру, в задаче 3, то ее можно решить графически.
Система ограничений такой задачи состоит из неравенств от двух переменных:
и целевая функция имеет вид F = C1x + C2y, которую необходимо максимизировать.
Ответим на вопрос: какие пары чисел (x; y) являются решениями системы неравенств, т. е. удовлетворяют каждому из неравенств одновременно?
Предварительно необходимо понять, что является решением одного линейного неравенства с двумя неизвестными.
Решить линейное неравенство с двумя неизвестными – это значит определить все пары значений неизвестных, при которых неравенство выполняется.
Например, неравенству 3x – 5y ≥ 42 удовлетворяют пары (x, y) : (100, 2);
(3, –10) и т. д. Задача состоит в нахождении всех таких пар.
Рассмотрим два неравенства: ax + by ≤ c, ax + by ≥ c. Прямая ax + by = c делит плоскость на две полуплоскости так, что координаты точек одной из них удовлетворяют неравенству ax + by > c, а другой неравенству ax + + by < c.
Действительно, возьмем точку с координатой x = x0; тогда точка, лежащая на прямой и имеющая абсциссу x0, имеет ординату y0 =
Итак, .
Пусть для определенности a < 0, b > 0, c > 0. Все точки с абсциссой x0, лежащие выше P (например, точка М), имеют yM > y0, а все точки, лежащие ниже точки P, с абсциссой x0, имеют yN < y0. Поскольку x0 – произвольная точка, то всегда с одной стороны от прямой будут находиться точки, для которых ax + by > c, образующие полуплоскость, а с другой стороны – точки, для которых ax + by < c.
Рис. 3.1
Знак неравенства в полуплоскости зависит от чисел a, b, c.
Отсюда вытекает следующий способ графического решения систем линейных неравенств от двух переменных. Для решения системы необходимо:
1. Для каждого неравенства выписать уравнение, соответствующее данному неравенству.
2. Построить прямые, являющиеся графиками функций, задаваемых уравнениями.
3. Для каждой прямой определить полуплоскость, которая задается неравенством. Для этого взять произвольную точку, не лежащую на прямой, подставить ее координаты в неравенство. если неравенство верное, то полуплоскость, содержащая выбранную точку, и является решением исходного неравенства. Если неравенство неверное, то полуплоскость по другую сторону прямой является множеством решений данного неравенства.
4. Чтобы решить систему неравенств, необходимо найти область пересечения всех полуплоскостей, являющихся решением каждого неравенства системы.
Эта область может оказаться пустой, тогда система неравенств не имеет решений, несовместна. В противном случае говорят, что система совместна.
Решений может быть конечное число и бесконечное множество. Область может представлять собой замкнутый многоугольник или же быть неограниченной.
Рассмотрим три соответствующих примера.
Пример 1. Решить графически систему:
x + y – 1 ≤ 0;
–2x – 2y + 5 ≤ 0.
Решение:
рассмотрим уравнения x + y – 1 = 0 и –2x – 2y + 5 = 0, соответствующие неравенствам;
построим прямые, задающиеся этими уравнениями.
x + y – 1 = 0
|
x |
0 |
1 |
|
y |
1 |
0 |
–2x – 2y + 5 = 0
|
x |
0 |
2,5 |
|
y |
2,5 |
0 |
Рис.3. 2
Определим полуплоскости, задаваемые неравенствами. Возьмем произвольную точку, пусть (0; 0). Рассмотрим x + y – 1 0, подставим точку (0; 0): 0 + 0 – 1 ≤ 0. значит, в той полуплоскости, где лежит точка (0; 0), x + y – 1 ≤ 0, т. е. полуплоскость, лежащая ниже прямой, является решением первого неравенства. Подставив эту точку (0; 0), во второе, получим: –2 ∙ 0 – 2 ∙ 0 + 5 ≤ 0, т. е. в полуплоскости, где лежит точка (0; 0), –2x – 2y + 5 ≥ 0, а нас спрашивали, где –2x – 2y + 5 ≤ 0, следовательно, в другой полуплоскости – в той, что выше прямой.
Найдем пересечение этих двух полуплоскостей. Прямые параллельны, поэтому плоскости нигде не пересекаются, значит система данных неравенств решений не имеет, несовместна.
Пример 2. Найти графически решения системы неравенств:
Рис. 3.3
1. Выпишем уравнения, соответствующие неравенствам, и построим прямые.
x + 2y – 2 = 0
|
x |
2 |
0 |
|
y |
0 |
1 |
y – x – 1 = 0
|
x |
0 |
2 |
|
y |
1 |
3 |
y + 2 = 0;
y = –2.
2. Выбрав точку (0; 0), определим знаки неравенств в полуплоскостях:
0 + 2 ∙ 0 – 2 ≤ 0, т. е. x + 2y – 2 ≤ 0 в полуплоскости ниже прямой;
0 – 0 – 1 ≤ 0, т. е. y – x – 1 ≤ 0 в полуплоскости ниже прямой;
0 + 2 = 2 ≥ 0, т. е. y + 2 ≥ 0 в полуплоскости выше прямой.
3. Пересечением этих трех полуплоскостей будет являться область, являющаяся треугольником. Нетрудно найти вершины области, как точки пересечения соответствующих прямых
.
Таким образом, А(–3; –2), В(0; 1), С(6; –2).
Рассмотрим еще один пример, в котором получившаяся область решения системы неограничена.
Пример 3. Решить графически систему
Выпишем уравнения, соответствующие неравенствам, и построим прямые. Рис. 3.4
x + y – 1 = 0
|
x |
0 |
1 |
|
y |
1 |
0 |
y – x – 1 = 0
|
x |
0 |
–1 |
|
y |
1 |
0 |
Определим знаки в полуплоскостях. Выберем точку (0; 0):
0 – 0 – 1 ≤ 0, т. е. y – x – 1 ≤ 0 ниже прямой;
0 + 0 – 1 ≤ 0, т. е. x + y – 1 ≤ 0 ниже прямой.
Пересечением двух полуплоскостей является угол с вершиной в точке А(0;1). Эта неограниченная область является решением исходной системы неравенств.
3.3.2. Решение задачи ЛП графически
Итак, мы научились решать системы линейных неравенств и выяснили, что решением является некоторая многоугольная область.
Вернемся к ЗЛП. Любая ЗЛП состоит из ограничений, являющихся системой неравенств, и целевой функции.
Определение. Любое решение системы ограничений называется допустимым решением ЗЛП.
Определение. Допустимое решение, в котором целевая функция достигает максимального или минимального значения, называется оптимальным решением.
В силу этих определений задача ЛП может быть сформулирована следующим образом: среди всех точек выпуклой области, являющейся решением системы ограничений, выбрать такую, координаты которой минимизируют (максимизируют) линейную функцию F = с1x + с2y.
Заметим, что переменные x, y в ЗЛП принимают, как правило, неотрицательные значения (x ≥ 0, y ≥ 0), поэтому область расположена в I четверти координатной плоскости.
Рассмотрим линейную функцию F = с1x + с2y и зафиксируем какое-нибудь ее значение F. пусть, к примеру, F = 0, т. е. с1x + с2y = 0. графиком этого уравнения будет прямая, проходящая через начало координат (0;0) (рис. 3.5).
Рис. 3.5
При изменении этого фиксированного значения F = d, прямая с1x + с2y = d будет смещаться параллельно и «зачертит» всю плоскость. Пусть D – многоугольник – область решения системы ограничений. При изменении d прямая с1x + с2y = d, при некотором значении d = d1 достигнет многоугольника D, назовем эту точку А «точкой входа», и затем, пройдя многоугольник, при некотором значении d = d2 будем иметь с ним последнюю общую точку В, назовем В «точкой выхода».
Очевидно, что своего наименьшего и наибольшего значения целевая функция F = с1x + с2y достигнет в точках «входа» А и «выхода» В.
Учитывая, что оптимальное значение на множестве допустимых решений целевая функция принимает в вершинах области D, можно предложить следующий план решения ЗЛП:
построить область решений системы ограничений;
построить прямую, соответствующую целевой функции, и параллельным переносом этой прямой найти точку «входа» или «выхода» (в зависимости от требования минимизировать или максимизировать целевую функцию);
определить координаты этой точки, вычислить в них значение целевой функции.
Заметим, что вектор (с1, с2), перпендикулярный прямой, показывает направление роста целевой функции.
При графическом решении ЗЛП возможны два случая, которые требуют особого обсуждения.
Случай 1 (рис. 3.6).
При перемещении прямой с1x + + с2y = d «вход» или «выход» (как на рисунке) произойдет по стороне многоугольника. Это случится, если в многоугольнике есть стороны, параллельные прямой с1х + с2у = d.
В этом случае точек «выхода» («входа») бесчисленное множество, а именно – любая точка отрезка АВ. Это означает, что целевая функция
принимает максимальное
Рис. 3.6 (минимальное) значение не в одной точке, а во всех точках, лежащих на соответствующей стороне многоугольника D.
Случай 2 (рис. 3.7).
Рассмотрим случай, когда область допустимых значений неограниченна, например, случалось в рассмотренном примере 3 или здесь, на рис. 3.7.
В случае неограниченной области целевая функция может быть задана таким образом, что соответствующая ей прямая не имеет точки «выхода» (или «входа»). Тогда максимальное значение функции (минимальное) не достигается никогда – говорят, что функция не ограничена.
Рис. 3.7
Рассмотрим подробно на примере решение задачи 3 темы 3.2.2 о составлении плана графически.
Необходимо найти максимальное значение целевой функции F = 4x + 6y → max, при системе ограничений
Построим область допустимых решений, т. е. решим графически систему неравенств. Для этого построим каждую прямую и определим полуплоскости, заданные неравенствами.
x + y = 18
|
x |
12 |
9 |
|
y |
6 |
9 |
0,5x + y = 12
|
x |
12 |
18 |
|
y |
6 |
3 |
x = 12 – параллельна оси OY;
y = 9 – параллельна оси OX;
x = 0 – ось OY;
y = 0 – ось OX;
x ≥ 0 – полуплоскость правее оси OY;
y ≥ 0 – полуплоскость выше оси OX;
y ≤ 9 – полуплоскость ниже y = 9;
x ≤ 12 – полуплоскость левее x = 12;
0,5x + y ≤ 12 – полуплоскость ниже прямой 0,5x + y = 12;
x + y ≤ 18 – полуплоскость ниже прямой x + y = 18.
Рис. 3.8
Пересечением всех этих полуплоскостей является очевидно, пятиугольник ОАВСД, с вершинами в точках О(0; 0), А(0; 9), В(6; 9), С(12; 6), Д(12; 0). Этот пятиугольник и образует область допустимых решений задачи.
Рассмотрим целевую функцию задачи F = 4x + 6y → max.
|
x |
3 |
0 |
|
y |
–2 |
0 |
Построим прямую, отвечающую значению функции F = 0 : 4x + 6y = 0. Будем двигать эту прямую параллельным образом. Из всего семейства прямых 4x + 6y = const последней вершиной, через которую пройдет прямая при выходе за границу многоугольника, будет вершина С (12; 6). Именно в ней F = 4x + 6y достигнет своего максимального значения.
Значит, при x = 12, y = 6 функция F достигает своего максимального значения F = 4 ∙ 12 + 6 ∙ 6 = 84, равного 84. Точка с координатами (12; 6) удовлетворяет всем неравенствам системы ограничений, и в ней значение целевой функции оптимально F* = 84 (оптимальное значение будем обозначать «*»).
Задача решена. Итак, необходимо выпустить 12 изделий I вида и 6 изделий II вида, при этом прибыль составит 84 тыс. руб.
Еще раз обратим внимание на то, что графический метод применялся нами для решения задач, которые имели в системе ограничений только две переменные. В принципе этот метод может применяться и для систем неравенств, имеющих три переменных. Геометрически ситуация будет иная, роль прямых будут играть плоскости в трехмерном пространстве, а решением неравенства от трех переменных будет являться полупространство, находящееся по одну сторону от плоскости. Роль областей будут играть многогранники, являющиеся пересечением полупространств. Идея метода остается в этом случае той же. Желающие ознакомиться подробнее могут обратиться к книге А. С. Солодовникова «Системы линейных неравенств» (популярные лекции по математике).
Вопросы для самоконтроля
1. Что является графиком функции ах + bх = с?
2. Где находятся точки плоскости, удовлетворяющие неравенству ax + bx ≤ c?
3. Что называют точкой «входа» и «выхода» в области решения системы ограничений?
4. Как Вы себе представляется различные случаи пересечения полуплоскостей?
3.4. Каноническая форма задач ЛП
В каждой задаче ЛП ищутся значения переменных при условии, чтобы:
эти значения удовлетворяли некоторой системе линейных уравнений или неравенств;
при этих значениях целевая функция обращалась бы в минимум или максимум.
Одним из универсальных методов ЛП является симплексный метод, который, однако, можно применять, если задача ЛП имеет каноническую форму.
Определение. Задача ЛП имеет каноническую форму, если все ограничения системы состоят только из уравнений (кроме неравенств, выражающих неотрицательность переменных) и целевую функцию необходимо минимизировать.
Примером такой задачи ЛП в канонической форме является задача 1 – сбалансированная транспортная задача с системой ограничений (3.1) и целевой функцией (3.2).
Однако в большинстве экономических задач чаще всего в систему ограничений первоначально входят не только уравнения, а и неравенства, как было у нас в задачах 2, 3, 4.
Утверждение. Любая общая задача ЛП может быть приведена к канонической форме.
Приведение общей задачи ЛП к канонической форме достигается путем введения новых (их называют дополнительными) переменных. Вернемся к задаче 3. Система ограничений (3.3) этой задачи состоит из четырех неравенств. Введя дополнительные переменные y1 ≥ 0, y2 ≥ 0, y3 ≥ 0, y4 ≥ 0, можно перейти к системе ограничений:
(3.9)
Эти дополнительные переменные yi имеют абсолютно ясный экономический смысл, а именно означают величину неиспользованного времени работы (простоя машины i-го вида).
Например, если бы машины первого вида работали все 18 ч, то x + y = 18, следовательно, y1 = 0. Но мы допускаем возможность неполного использования времени работы первой машины x + y < 18. В этом случае y1 приобретает положительное значение и может рассматриваться как неиспользованный лимит времени. Например, зная решение этой задачи из пункта 3.3.2, x = 12, y = 6, мы можем из системы ограничений (3.9) сделать вывод, что y1 = y2 = y3 = 0, а y4 = 12 – 6 = 6. Т. е. машины первого, второго, третьего вида используют свое рабочее время полностью. А вот четвертая машина загружена лишь наполовину, 6 часов, и при заданном оптимальном плане простаивает. Возможно, после таких выводов руководителю предприятия захочется загрузить ее другой работой, сдать в аренду на это время и т. д.
Итак, введением дополнительных переменных мы можем любое ограничение типа неравенства привести к уравнению.
Рассмотрим задачу о смеси (задача 4). Система ограничений (3.7) имела вид:
Неравенства были обращены в сторону «больше», поэтому вводя дополнительные переменные y1, y2, y3 ≥ 0, их необходимо вычесть из левой части, чтобы уравнять ее с правой. Получим систему ограничений в канонической форме:
Переменные yi также будут иметь экономический смысл. Если вы вспомните практическое содержание задачи, то переменная y1 будет означать количество излишнего вещества А в смеси, y2 – количество излишков вещества В в смеси, y3 – излишки С в смеси.
Задача нахождения максимального значения целевой функции может быть сведена к нахождению минимума для функции –F ввиду очевидности утверждения max F = –min (–F). Посмотрите на рисунок 3.9: если в какой-то точке x = x0 функция y = F(x) достигает своего максимума, то функция y = –F(x), симметричная ей относительно оси OX, в этой же точке x0 достигнет минимума, причем Fmax = – (–Fmin) при x = x0.
Вывод. Для представления задачи ЛП в канонической форме необходимо:
неравенства, входящие в систему ограничений задачи, преобразовать в уравнения с помощью введения дополни-тельных переменных;
если целевая функция F →max (максимизируется), она заменяется на функцию –F → min (которая минимизируется).
Рис. 3.9
Вопросы для самоконтроля
1. Каков канонический вид задачи линейного программирования?
2. Как преобразовать задачу ЛП к каноническому виду?
3.5. Аналитическое введение в симплекс-метод
Симплекный метод имеет широчайшее применение в связи с развитием ЭВМ и является универсальным методом линейного программирования. его алгоритм состоит из ряда шагов, четко определенных действий, следуя которым вы приходите к решению задачи ЛП. Сейчас нас будет интересовать идея этого метода, которая при общем взгляде на алгоритм, или на «замурованную» программу в ЭВМ, не столь ясна, как если бы рассмотреть ее на конкретном примере.
Итак, если мы решаем ЗЛП в канонической форме, то система ограничений – это обычная система линейных уравнений. При решении задач ЛП получаются системы линейных уравнений, имеющие, как правило, бесконечно много решений.
Например, пусть дана система
Здесь число уравнений равно 2, а неизвестных – 3, уравнений меньше. Выразим x1 и x2 через x3:
Это общее решение системы. если переменной x3 придавать произвольные числовые значения, то будем находить частные решения системы. Например, x3 = 1 x1 = 1 x2 = 6. Имеем (1, 6, 1) – частное решение. Пусть x3 = 2 x1 = –3, x2 = 1, (–3, 1, 2) – другое частное решение. Таких частных решений бесконечно много.
Переменные x1 и x2 называются базисными, а переменная x3 – не базисная, свободная.
Совокупность переменных x1 и x2 образует базис: Б (x1, x2). Если x3 = 0, то полученное частное решение (5, 11, 0) называется базисным решением, соответствующим базису Б (x1, x2).
Базисным называется решение, соответствующее нулевым значениям свободных переменных.
В качестве базисных можно было взять и другие переменные: (x1, x3) или (x2, x3).
Как переходить от одного базиса Б (x1, x2) к другому базису Б (x1, x3)?
Для этого надо переменную x3 перевести в базисные, а x2 – в небазисные т. е. в уравнениях надо x3 выразить через x2 и подставить в 1-е:
Базисное решение, соответствующее базису Б (x1, x3), таково: (–19/5; 0; 11/5).
Если теперь от базиса Б (x1, x3) нам захочется перейти к базису Б (x2, x3), то
Базисное решение, соответствующее базису Б (x2, x3): (0;19/4; 7/8).
Из трех найденных базисных решений решение, соответствующее базису Б (x1, x3) – отрицательное x1 0, нас в ЗЛП интересуют только неотрицательные решения.
Если задача ЛП имеет решение, то оно достигается на множестве базисных неотрицательных решений системы ограничений канонической формы.
Поэтому идея симплекс-метода и состоит в последовательном переходе от одного базиса к другому, лучшему с точки зрения значения целевой функции.
Пример 4.
Решить задачу ЛП.
Функцию F = x2 – x1 min необходимо минимизировать при заданной системе ограничений:
|
–2x1 + x2 + x3 = 2; x1 + x2 + x5 = 5; x1 – 2x2 + x4 = 12; xi ≥ 0, i = 1, 5. |
Эти ограничения могут рассматриваться как произошедшие из неравенств, а переменные x3, x5, x4 – как дополнительные.
Запишем ограничения, выбрав базис из переменных Б{ x3, , x4, x5}:
Этому базису соответствует базисное неотрицательное решение
x1 = 0, x2 = 0, x3 = 2, x4 = 2, x5 = 5 или (0, 0, 2, 2, 5).
Теперь нужно выразить F через небазисные переменные, в нашем случае это уже сделано: F = x2 – x1.
Проверим, достигла ли функция F своего минимального значения. Для этого базисного решения F = 0 – 0 = 0 – значение функции равно 0. Но его можно уменьшить, если x1 будет возрастать, т. к. коэффициент в функции при x1 отрицателен. Однако при увеличении x1 значения переменных x4, x5 уменьшаются (смотрите второе и третье равенство системы ограничений). Переменная x1 не может быть увеличена больше чем до 2, иначе x4 станет отрицательной (ввиду равенства 2), и не больше, чем до 5, иначе x5 – отрицателен. Итак, из анализа равенств следует, что переменную x1 можно увеличить до 2, при этом значение функции уменьшится.
Перейдем к новому базису Б2, введя переменную x1 в базис вместо x4.
Б2{x1, x3, x5}.
Выразим эти базисные переменные через небазисные. Для этого сначала выразим x1 из второго уравнения и подставим в остальные, в том числе и в функцию.
Имеем:
F = –2 – x2 + x4.
Базисное решение, соответствующее базису Б2{x1, x3, x5}, имеет вид (2, 0, 6, 0, 3), и функция принимает значение F = –2 в этом базисе.
Значение функции можно и дальше уменьшать, увеличивая x2. Однако, глядя на систему, x2 можно увеличивать лишь до 1, т. к. иначе из последнего равенства x5 = 3 – 3x2 + x4 следует, что при x2 > 1 x5 станет отрицательной. А у нас все переменные в ЗЛП предполагаются неотрицательными. Остальные уравнения системы не дают ограничений на x2. Поэтому увеличим x2 до 1, введя его в базис вместо x5: Б3{x1, x2, x3}.
Выразим x2 через x5 и подставим во все уравнения:
|
. |
Базисное решение, соответствующее базису Б3{х1, х2, х3}, выписывается (4, 1, 9, 0, 0), и функция принимает значение F = –3. Заметим, что значение F уменьшилось, т. е. улучшилось по сравнению с предыдущим базисом.
Посмотрев на вид целевой функции , заметим, что улучшить, т. е. уменьшить значение F нельзя и только при x4 = 0, x5 = 0 значение F = –3. как только x4, x5 станут положительными, значение F только увеличится, т. к. коэффициенты при x4, x5 положительны. Значит, функция F достигла своего оптимального значения F* = –3. Итак, наименьшее значение F, равное –3, достигается при x1* = 4, x2* = 1, x3* = 9, x4* = 0, x5* = 0.
Пример завершен.
На этом примере очень наглядно продемонстрирована идея метода: постепенно переходя от базиса к базису, при этом всегда обращая внимание на значения целевой функции, которые должны улучшиться, мы приходим к такому базису, в котором значение целевой функции улучшить нельзя, оно оптимально. Заметим, что базисов конечное число, поэтому количество шагов, совершаемых нами до того нужного базиса, конечно. Осталось эту идею воплотить в четкий алгоритм, чтобы избежать тяжелого вычислительного процесса, и отдать полученный в результате симплекс-метод на «вооружение» машине-компьютеру.
Вопросы для самоконтроля
1. Сформулируйте основную идею симплексного метода.
2. Что такое базис пространства решений?
3. Как вы считаете, сколько базисов может иметь система, в которой два уравнения и три неизвестных?
4. Что происходит с целевой функцией при переходе от одного базиса к другому?
Содержание
Часть 3. Линейное программирование…………………………………… 1
3.1. Введение в линейное программирование..………………………. 1
3.2. Формулировка основных типов задач ЛП, построение их
математических моделей………………………………………………. 2
3.3. Графический способ решения задач ЛП………………………… 8
3.4. Каноническая форма задач ЛП…………………………………… 16
3.5. Аналитическое введение в симплекс-метод……………………… 18
PAGE 13
EMBED CorelDraw.Graphic.7
EMBED CorelDraw.Graphic.7
EMBED CorelDraw.Graphic.7
EMBED CorelDraw.Graphic.7
EMBED CorelDraw.Graphic.7
EMBED CorelDraw.Graphic.7
EMBED CorelDraw.Graphic.7
EMBED CorelDraw.Graphic.7
EMBED CorelDraw.Graphic.7
EMBED CorelDraw.Graphic.7