Основы математического моделирования социально-экономических процессов (стр. 3 )

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

Термин "линейное программирование" появился впервые только в 1951 году в работах Дж. Б. Данцига и Т. Купманса (США). В эти же годы Дж. Б. Дансингом разработан эффективный метод решения задач линейного программирования – симплекс метод.

Наиболее эффективно линейное программирование развивалось в СССР и США в 1955 – 65 годах, именно в этот период оно было одним из наиболее "модных" разделов прикладной математики. В настоящее время линейное программирование стало важным инструментом современной теоретической и прикладной математики.

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

Линейное программирование – наиболее разработанный и широко применяемый раздел математического программирования. Это объясняется следующим:

·  математические модели очень большого числа экономических задач линейны относительно искомых переменных;

·  эти типы задач в настоящее время наиболее изучены;

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

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

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

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

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

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

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

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

Имеются какие-то переменные х = (х1 , х2 , … хn ) и функция этих переменных f(x) = f (х1 , х2 , … хn ), которая носит название целевой функции. Ставится задача: найти экстремум (максимум или минимум) целевой функции f(x) при условии, что переменные x принадлежат некоторой области G:

В зависимости от вида функции f(x) и области G и различают разделы математического программирования: квадратичное программирование, выпуклое программирование, целочисленное программирование и т. д. Линейное программирование характеризуется тем, что

а) функция f(x) является линейной функцией переменных х1 , х2 , … хn

б) область G определяется системой линейных равенств или неравенств.

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

·  максимум или минимум целевой функции (критерий оптимальности);

·  систему ограничений в форме линейных уравнений и неравенств;

·  требование неотрицательности переменных.

Пример 1: Пусть имеется два станка (S1 , S2 ), на каждом из которых можно производить два вида продукции (P1 , P2 ). Станок S1 производит единицу продукции P1 за 1 час, а единицу продукции P2 - за 2 часа. Станок S2 затрачивает на единицу продукции P1 - 2 часа, а на единицу продукции P2 - 1 час. Станок S1 может работать в сутки не более 10 ч., а станок S2 - не более 8 ч. Стоимость единицы продукции P1 составляет C1 руб., а стоимость единицы продукции P2 - C2 руб.

Требуется определить такие объемы выпуска продукции P1 и P2 на станок, чтобы выручка от реализации производственной продукции была максимальной.

Вид ресурса	Число единиц ресурса, затрачиваемое на изготовление единицы продукции	Запас ресурса
P1	P2
S1	1	2	10
S2	2	1	8
Прибыль за единицу продукции	C1	C2	...

Составим математическую модель задачи:

Обозначим через х1 и х2 количества продукции P1 и P2, которое планируется произвести на каждом отдельном станке. Стоимость произведенной продукции F = c1 х1 + c2 х2 . Мы должны назначить х1 и х2 так, чтобы величина F была максимальной. Переменные х1 , х2 не могут принимать произвольных значений. Их значения ограничены условиями производства, а именно тем, что станки могут работать ограниченное время. На изготовление продукции P1 станок S1 тратит 1x1 часов, а на изготовление продукции P2 – 2x2 часов. Поскольку время работы станка S1 не превосходит 10 ч, то величины х1 и х2 должны удовлетворять неравенству x1 + 2x2<= 10.

Аналогично можно получить неравенство для станка S2: 2x1 + x2 <= 8.

Кроме того, величины х1 , х2 не могут быть отрицательными: x1 >= 0, x2 >= 0, по смыслу задачи.

Такие задачи кратко записываются следующим образом:

(2.1)

(2.2)

(2.3)

Итак, математическая модель задачи: найти такой план выпуска продукции Х = ( х1 , х2 ), удовлетворяющий системе (2.1) и условию (2.2), при котором функция (2.3) принимает максимальное значение.

Решения, удовлетворяющие системе ограничений (2.1) и требованием неотрицательности (2.2), являются допустимыми, а решения, удовлетворяющие одновременно и требованием (2.3) оптимальными.

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

	(2.4)
	(2.5)
	(2.6)

Коэффициенты ai, j, bi, cj, j = 1, 2, ... , n, i =1, 2, ... , m – любые действительные числа (возможно 0).

Итак, решения, удовлетворяющие системе ограничений (2.4) условий задачи и требованиям неотрицательности (2.5), называются допустимыми, а решения, удовлетворяющие одновременно и требованиям минимизации (максимализации) (2.6) целевой функции, - оптимальными.

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

В канонической форме задача является задачей на максимум (минимум) некоторой линейной функции F, ее система ограничений состоит только из равенств (уравнений). При этом переменные задачи х1, х2, ..., хn являются неотрицательными:

	(2.7)
	(2.8)
	(2.9)

К канонической форме можно преобразовать любую задачу линейного программирования.

Правило приведения ЗЛП к каноническому виду:

1. Если в исходной задаче некоторое ограничение (например, первое) было неравенством, то оно преобразуется в равенство, введением в левую часть некоторой неотрицательной переменной, при чем в неравенства «≤» вводится дополнительная неотрицательная переменная со знаком «+»; в случаи неравенства «≥» - со знаком «-»

(2.10)

Вводим переменную

.

Тогда неравенство (2.10) запишется в виде:

(2.11)

В каждое из неравенств вводится своя “уравнивающая” переменная, после чего система ограничений становится системой уравнений.

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

, l - свободный индекс

3. Если в ограничениях правая часть отрицательна, то следует умножить это ограничение на (-1)

4. Наконец, если исходная задача была задачей на минимум, то введением новой целевой функции F1 = - F мы преобразуем нашу задачу на минимум функции F в задачу на максимум функции F1.

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

В стандартной форме задача линейного программирования является задачей на максимум (минимум) линейной целевой функции. Система ограничений ее состоит из одних линейных неравенств типа « <= » или « >= ». Все переменные задачи неотрицательны.

	(2.12)

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

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

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

Введем дополнительные переменные x3 , x4 , x5 . Причем в первое неравенство введем неотрицательную переменную x3 со знаком минус, а во второе и в третье – со знаком плюс переменные x4 , x5 запишем задачу в виде:

Переведем max на min, домножив целевую функцию на (-1)

что и дает эквивалентную задачу в канонической форме.

Модульная единица 2. Методы решения задач линейного программирования

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

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

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

На рис. 2.1 изображено выпуклое множество (выпуклый многоугольник), а на рис. 2.2 - невыпуклое.

рис. 2.1	рис. 2.2

Определение 2. Пересечение конечного числа выпуклых множеств также выпуклое множество.

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

Утверждение 1. Множеством решений системы m линейных неравенств с n переменными является выпуклый многогранник в n-мерном пространстве (исключая случай, когда система несовместна).

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

Ранее говорилось, что ограничениями любой задачи линейного программирования являются либо система линейных уравнений, либо система линейных неравенств. Совокупность решений таких систем при условии их совместности, образует выпуклые множества с конечным числом угловых точек. В частном случае, когда в систему ограничений - неравенств входят только две переменные x1 и x2 это множество можно изобразить на плоскости (см.3).

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

Справедливость этого утверждения иллюстрируется в примере 3.

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

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

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

	(2.13)
	(2.14)
	(2.15)

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

a1x1 + a2x2 ≤ b.

Рассмотрим прямую на плоскости с уравнением a1x1 + a2x2 = b.

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

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

Рис. 2.3

1. Основной случай - получающаяся область имеет вид ограниченного (замкнутого) выпуклого многоугольника (см. рис. 2.4).

2. Неосновной случай - получается неограниченный (незамкнутый) выпуклый многоугольник, имеющий вид, подобный изображенному на рис. 2.5.

рис. 2.4	рис. 2.5

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

Алгоритм графического метода решения задач ЛП:

1.  Построить область допустимых решений.

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

3.  Если область допустимых решений является непустым множеством, построить нормаль линий уровня n = (c1 ,c2 ) и одну из линий уровня, имеющую общие точки с этой областью.

4.  Линию уровня переместить до опорной прямой в задаче на максимум в направлении нормали, в задаче на минимум - в противоположном направлении.

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

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

Рассмотрим геометрическое истолкование задачи из Примера 2.1.1Пусть имеется два станка (S1 , S2 ), на каждом из которых можно производить два вида продукции (P1 , P2 ). Станок S1 производит единицу продукции P1 за 1 час, а единицу продукции P2 - за 2 часа. Станок S2 затрачивает на единицу продукции P1 - 2 часа, а на единицу продукции P2 - 1 час. Станок S1 может работать в сутки не более 10 ч., а станок S2 - не более 8 ч. Стоимость единицы продукции P1 составляет C1 руб., а стоимость единицы продукции P2 - C2 руб.

Требуется определить такие объемы выпуска продукции P1 и P2 на станок, чтобы выручка от реализации производственной продукции была максимальной.

Вид ресурса	Число единиц ресурса, затрачиваемое на изготовление единицы продукции	Запас ресурса
P1	P2
S1	1	2	10
S2	2	1	8
Прибыль за единицу продукции	C1	C2	...

Составим математическую модель задачи:

Обозначим через х1 и х2 количества продукции P1 и P2, которое планируется произвести на каждом отдельном станке. Стоимость произведенной продукции F = c1 х1 + c2 х2 . Мы должны назначить х1 и х2 так, чтобы величина F была максимальной. Переменные х1 , х2 не могут принимать произвольных значений. Их значения ограничены условиями производства, а именно тем, что станки могут работать ограниченное время. На изготовление продукции P1 станок S1 тратит 1x1 часов, а на изготовление продукции P2 – 2x2 часов. Поскольку время работы станка S1 не превосходит 10 ч, то величины х1 и х2 должны удовлетворять неравенству x1 + 2x2<= 10.

Аналогично можно получить неравенство для станка S2: 2x1 + x2 <= 8.

Кроме того, величины х1 , х2 не могут быть отрицательными: x1 >= 0, x2 >= 0, по смыслу задачи.

Такие задачи кратко записываются следующим образом:

(2.1)

(2.2)

(2.3)

Итак, математическая модель задачи: найти такой план выпуска продукции Х = ( х1 , х2 ), удовлетворяющий системе (2.1) и условию (2.2), при котором функция (2.3) принимает максимальное значение.

Решения, удовлетворяющие системе ограничений (2.1) и требованием неотрицательности (2.2), являются допустимыми, а решения, удовлетворяющие одновременно и требованием (2.3) оптимальными.

Пример 2.3.1Возьмем с1 = 1 и с2 = 1

Математическая модель задачи:

Решение:

1. Построение области допустимых решений целевой функции F.

Построим прямоугольную систему координат. Так как, x1 и x2 неотрицательны, то можно ограничится рассмотрением первого квадранта.

Рассмотрим первое ограничение:

x1+2x2 =

x1 = 0 x2 = 5

x1 = 10 x2 = 0

Рассмотрим второе ограничение:

2x1+x2 = 8 (2)

x1 = 0 x2 = 8

x1 = 4 x2 = 0

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

2. Построить нормаль линий уровня n = (c1 ,c2 ).

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

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

решая которую, получаем точку максимума С (2;4), Fmax = 6.(см. рис.2.6)

рис.2.6

Тема 2.4. Симплекс-метод линейного программирования.

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

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

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

Этот метод является универсальным, применимым к любой задаче линейного программирования в канонической форме. Система ограничений здесь - система линейных уравнений, в которой количество неизвестных больше количества уравнений. Если ранг системы равен r, то мы можем выбрать r неизвестных, которые выразим через остальные неизвестные. Для определенности предположим, что выбраны первые, идущие подряд, неизвестные X1, X2, ..., Xr. Тогда наша система уравнений может быть записана как

К такому виду можно привести любую совместную систему, например, методом Гаусса. Правда, не всегда можно выражать через остальные первые r неизвестных (мы это сделали для определенности записи). Однако такие r неизвестных обязательно найдутся. Эти неизвестные (переменные) называются базисными, остальные свободными.

Придавая определенные значения свободным переменным и вычисляя значения базисных (выраженных через свободные), мы будем получать различные решения нашей системы ограничений. Таким образом, можно получить любое ее решение. Нас будут интересовать особые решения, получаемые в случае, когда свободные переменные равны нулю. Такие решения называются базисными, их столько же, сколько различных базисных видов у данной системы ограничений. Базисное решение называется допустимым базисным решением или опорным решением, если в нем значения переменных неотрицательны. Если в качестве базисных взяты переменные X1, X2, ..., Xr, то решение {b1, b2,..., br, 0, ..., 0} будет опорным при условии, что b1, b2,..., br ≥ 0.

Симплекс-метод основан на теореме, которая называется фундаментальной теоремой симплекс-метода. Среди оптимальных планов задачи линейного программирования в канонической форме обязательно есть опорное решение ее системы ограничений. Если оптимальный план задачи единственен, то он совпадает с некоторым опорным решением. Различных опорных решений системы ограничений конечное число. Поэтому решение задачи в канонической форме можно было бы искать перебором опорных решений и выбором среди них того, для которого значение F самое большое. Но, во-первых, все опорные решения неизвестны и их нужно находить, a, во-вторых, в реальных задачах этих решений очень много и прямой перебор вряд ли возможен. Симплекс-метод представляет собой некоторую процедуру направленного перебора опорных решений. Исходя из некоторого, найденного заранее опорного решения по определенному алгоритму симплекс-метода мы подсчитываем новое опорное решение, на котором значение целевой функции F не меньше, чем на старом. После ряда шагов мы приходим к опорному решению, которое является оптимальным планом.