Учебное пособие по курсу «Математика»
Сравнительно большое число экономических задач сводится к линейным математическим моделям. Традиционно оптимизационные линейные математи ческие модели называют моделями линейного программирования. При этом под линейным программированием понимается линейное планирование, т.е. получе ние оптимального плана, который и является решением задачи с линейной стру к турой.
В самом общем виде математическая модель задачи линейного программирования записывается следу ющим образом:
Максимизировать (минимизировать) целевую функцию:
при ограничениях:
Здесь - управляющие переменные, или решения задачи, L – целевая функция, или критерий эффективности задачи, остальные величины - параметры зада чи.
Очевидно, что как целевая функция, так и все ограничения ли нейны по управляющим переменным. В приведенной постановке зада ча содержит n переменных и m ограниче ний.
Решить задачу линейного программирования – означает найти такие значе ния управляющих переменных, удовлетворяющих ограни че ниям, при кото рых целевая функция принимает максимальное, или минимальное значение.
Рассмотрим примеры некоторых типичных экономических задач, оптимальное решение которых может быть найдено с помощью построе ния и расчета соответствующих линейных математических моделей, имеющих вид, приведенный выше.
Задача 1. Планирование производства. Для изготовления различных ви дов изделий используются разные ресурсы. Общие запасы каждого ресурса, ко личества ресурса каждого типа, затрачиваемого на изготовление одного изделия каждого вида, заданы. Нужно составить план производства изделий, обеспечи вающий максимальную суммарную прибыль от реализации изделий.
Задача 2. Формирование минимальной потребительской продово льственной корзины. Задан ассортимент продуктов, имеющихся в продаже. Каждый продукт содержит определенное количество разных питательных веществ (вита минов и калорий). Известен требуемый человеку минимум питательных веществ каждого вида. Необходимо определить требуемую потребительскую продовольственную корзину, имеющую минимальную стоимость.
Задача 3. Расчет оптимальной загрузки оборудования. Предприятию необходимо выполнить производственный заказ на имеющемся оборудовании. Для каждой единицы оборудования заданы: фонд рабочего времени, себестои мость изготовления единицы продукции каждого вида, а также производитель ность, т.е. число единиц продукции каждого вида, которое можно произвести в единицу времени. Нужно распределить изготовление продукции между обору дованием таким образом, чтобы себестоимость всей продукции была минимальна.
Задача 4. Раскрой материала. На раскрой (распил) поступает материал нескольких видов в определенном количестве. Из этого материала необходимо изготовить различные изделия. Материал может быть раскроен разными спосо бами. Каждый способ имеет свою себестоимость и позволяет получить разное количество изделий каждого вида. Определить способ раскроя, при котором сум марная себестоимость минимальна.
Задача 5. Составление плана реализации товара. Фирма реализует раз личные товары, используя при этом определенный набор средств (технических, людских, денежных). Общий запас средств, количество средств каждого вида, ис пользуемых при реализации единицы любого товара и прибыль от его продажи, заданы. Надо сформировать план реализации товаров, приносящий фирме максимальную прибыль.
3.1.1. Графический метод решения задач линейного программирования
Если число переменных в задаче линейного программирования равно двум, а ограничения представляют собой систему неравенств, то такую задачу можно решать графическим мето дом.
Таким образом, графический метод решения применим к задачам линей ного программирования, математическая модель которых имеет вид:
Алгоритм графического решения таких задач включает в себя два этапа, или шага.
Шаг 1. Находят область допустимых решений (ОДР) задачи путем сов местного решения всех неравенств системы ограничений. При этом решением каж дого из неравенств этой системы будет полуплоскость, включающая границу, т.е. прямую линию с уравне нием, аналогичным неравенству, если только в нем оставить знак равенства. Как правило, вид ОДР существенно зависит от вида неравенств системы ограничений. Основные, наиболее часто встречаю щиеся, виды ОДР представлены на рис. 3.1.
На рис. 3.1.а показана ОДР в виде замкнутого выпуклого многоугольника. Рис. 3.1.б изображает ОДР в виде разомкнутого выпуклого многоугольника. На рис. 3.1.в изображен случай, когда неравенства ограничений несовместны, т.е. не имеют общего решения и, следовательно, ОДР не существует. Наконец, на рисунке 3.1.г изображен случай, когда ОДР состоит только из одной точки А.
Шаг 2. Строят линию уровня целевой функции при C = 0. Находят координаты вектора градиента целевой функции и строят вектор градиента с началом в начале координат. Затем двигают линию уровня целевой функции параллельно самой себе в направлении вектора градиента до тех пор, пока не достигнут последней на ее пути вершины многоугольника ОДР. Именно координаты этой вершины и будут являться оптимальными значениями управ ляющих переменных, доставляющими максимум целевой функции. При реше нии задач на минимум осуществляют продвижение линии уровня, построенной для заведомо большого значения уровня, в направлении вектора антиградиента, имеющего ту же норму, но противоположно направлен ного вектору градиента.
ПРИМЕР: При продаже двух видов товара используется два типа ресурсов. Нормы затрат ресурсов на реализацию единицы товара и общий объем запаса каждого ресурса заданы таблицей:
| Ресурсы | Нормы затрат ресурсов на 1 товара | Запас ресурсов | |
| 1-го вида | 2-го вида | ||
| 1 | 2 | 2 | 12 |
| 2 | 3 | 0 | 9 |
Прибыль от реализации одной единицы товара первого вида составляет 2 условные единицы, а второго – 1 условную единицу. Требуется найти оп тимальный план реализации товаров, обеспечивающий торговому предприя тию максимальную прибыль.
Сравнение с задачами приведенного выше перечня показывает, что это типовая задача 5. Линейную математическую модель задачи можно записать в виде:
В этой модели управляющие переменные количества реализуемых товаров первого и второго видов, соответственно, P – прибыль. Система нера венств – это ограничения по ресурсам. Суммарное количество ресурсов на реализацию товаров первого и второго видов не превышает общего количества запасов ресурсов каж дого типа.
Поскольку в модели задачи две управляющие переменные, а ограничения записаны в виде неравенств, можно эту задачу решить графическим методом. Следуя алгоритму, сначала на координатной плоскости построим область допустимых решений – ОДР. Каждое неравенство системы ограничений определяет в этой плоскости полуплоскость, лежащую выше или ниже прямой, определяемой соответствующим уравнением.
Процесс отыскания ОДР представлен на рис. 3.2, на котором найденная ОДР заштрихована и представляет собой выпуклый замкнутый четырехугольник (трапецию).
На рис. 3.3 ОДР обведена жирной чертой и представляет собой трапецию OABC. Также в соответствии с алгоритмом, построим линию уровня целевой функции при C = 0. На рис. 3.3 она показана в виде пунктирной линии, проходящей через начало коорди нат. Там же в виде стрелки, исходящей из начала координат, представлен вектор градиента целевой функции, имеющий координаты (2; 1). Если продвигать линию уровня по направлению вектора градиента, то конечной верши ной ОДР на этом пути будет точка В. Следовательно, ее координаты и будут ис комым оп ти мальным решением исходной задачи: , доставляющим максимум целевой функции, равный .
Таким образом, для получения максимальной прибыли в размере 9 услов ных единиц надо продать 3 изделия первого вида и 3 изделия второго вида.
3.1.2. Симплекс-метод решения задач линейного программирования
Симплекс-метод является универсальным, т.к. позволяет решить практически любую задачу линейного программирования.
Чаще всего, при графическом решении задач линейного программиро вания ОДР представляет собой замкнутый выпуклый многоугольник. В случае n переменных ОДР будет многомерным многогранником, подобным симплексу. Как правило, оптимальное решение – это координаты какой-либо вершины этого многогранника. Основная идея симплекс-метода заключается в последовательном целенаправленном обходе вершин такого симплекса. При этом в каждой следующей вершине симплекса значение целевой функции, в общем случае, улучшается.
Однако, перед применением симплекс – метода исходную задачу линейно го программирования следует записать в канонической форме:
В канонической форме записи все переменные неотрицательны, а ограниче ниями являются уравнения. Переход от произвольной к канонической форме записи задачи линейного программирования производится с помощью следующих дей ствий:
Если требуется найти минимум целевой функции L, то, заменяя функ цию L на функцию (- L), переходят к задаче максимизации.
Если ограничение содержит неравенство со знаком «не более», то от не го переходят к равенству, добавляя в левую часть ограничения до полнительную неотрицательную переменную.
Если ограничение содержит неравенство со знаком «не менее», то от него переходят к равенству, вычитая из левой части ограничения до полнительную неотрицательную переменную.
Если в задаче какая-либо из переменных произвольна по величине, то от нее избавляются, заменяя ее разностью двух других дополнитель ных неотрицательных переменных.
Задача линейного программирования, записанная в канони ческой форме, называется основной задачей линейного програм ми рования.
Пусть записана основная задача линейного программирования. Предполо жим, что все уравнения системы ограничений независимы, т.е. выражают неза висимые друг от друга условия задачи. Если это не так, то лишние, зависимые от других, уравнения просто исключают. Основную задачу линейного програм мирования имеет смысл решать только тогда, когда число уравнений системы ограни чений меньше числа входящих в них неизвестных, т.е. когда: m < n. В против ном случае, если m = n, то система имеет единственное решение и пропадает смысл задачи максимизации, если же m > n, то система переопределена и, в об щем случае, не имеет решения.
Итак, если количество линейно независимых уравнений строго меньше ко личества неизвестных (переменных), то система уравнений ограничений имеет бесконечное множество решений, и, следова тельно, среди них можно выбирать оптимальное, т.е. то, которое доставляет максимум целевой функции задачи.
Реализа ция симплекс-метода включает в себя два крупных этапа:
Определение начального решения, удовлетворяющего ограни чениям.
Последовательное улучшение начального решения и получение оптимального решения задачи.
Пусть система уравнений ограничений содержит ровно m линейно незави симых уравнений, и, кроме того, m < n, тогда эту систему можно разрешить относительно m неизвестных, например: , выразив их через осталь ные (n – m) неизвестные.
После про ведения таких преобразований основная задача линейного программирования оказывается записанной в стандарт ном виде:
После того, как задача записана в стандартном виде, можно приступать к ее решению с помощью симплекс – метода, пошаговый алгоритм которого заключается в следующем:
Шаг 1. Получение начального решения. Выбираются m пере мен ных, на зываемых базисными и обладающих следующим свойст вом: они входят с коэф фициентом единица (безразлично, с плюсом или с минусом) только в одно уравнение системы ограничений, и с коэффи циентом нуль (т.е. не входят) – в остальные уравнения систе мы ограничений.
Остальные (n – m) переменных называются свободными. При этом все сво бодные переменные полагают равными нулю, но тогда базисные переменные будут равны свободным членам уравнений системы ограничений.
Если m базисных переменных это: (если это не так, то пере менные всегда можно перенумеровать), тогда начальное решение будет иметь вид:
Если все , то начальное решение является допусти мым, и можно переходить к шагу 2. В противном случае повто ря ют алгоритм поиска начального решения, т.е. преобразованиями уравнений системы ограничений добиваются выполнения условия .
Шаг 2. Выражение целевой функции только через свобод ные перемен ные. На этом шаге убеждаются в том, что целевая функция выражена только че рез свободные переменные. Если это не так, пользуясь соответствующими уравнениями системы ограничений, выражают целевую функцию только через свободные переменные, т.е. приводят ее к виду: . Далее переходят к шагу 3.
Шаг 3. Проверка решения на оптимальность. Составляется начальная симплекс–таблица. В левой колонке этой таблицы помещают базисные пере менные, а в крайней правой колонке – свободные члены соответствующих урав нений системы ограничений. На пересечении i-ой строки и j-го столбца разме щают коэффициент при j-ой переменной в i-ом ограничении. В последней от черкнутой строке (L – строке) размещают коэффициент при j-ой переменной в целевой функции, взятый с противоположным знаком. В последнем столбце L –строки (т.е. в правом нижнем углу таблицы) помещают значение свободного члена целевой функции со своим знаком. Чаще всего этим значением оказывается нуль. Пример начальной симплекс–таблицы:
| Базисные переменные | Коэффициенты при переменных | Свободные члены | |||
| | | … | | | |
| … | … | … | … … … … | … | … |
| | | | … | | 0 |
Для проверки решения на оптимальность просматривается последняя L – строка таблицы. Если коэффициенты, стоящие при свободных переменных неот рицательны, то полученное решение оптимально. Полученное решение единственно, если все эти коэффициенты строго положительны. Если среди не отрицательных коэффициентов при свободных переменных встречается хотя бы один нулевой, то задача имеет бесконечное множество решений. Если же в последней строке таблицы есть хотя бы один отрицательный коэффициент (при свободных переменных), а в соответствующем этому ко эффициенту столбце нет ни одного положительного элемента, то целевая функ ция не ограничена на ОДР.
Наконец, если хотя бы один из коэффициентов, стоящих при свободных переменных, отрицательный и в соответствующем ему столбце есть хотя бы один положительный элемент, то полученное решение может быть улучшено. И можно переходить к шагу 4.
Шаг 4. Получение нового решения. Этот шаг условно может быть раз делен на три более мелких шага.
Шаг 4.1. Выбор переменной, вводимой в список базисных перемен ных. Просматривается последняя строка симплекс – таблицы. Среди элементов этой строки выбирается максимальный по модулю отрицательный элемент. Столбец, в котором стоит этот элемент, называется разрешающим. Если, напри мер, это p-ый столбец, то переменная вводится в список базисных перемен ных.
Шаг 4.2. Выбор переменной, выводимой из списка базисных перемен ных. Находят отношения элементов столбца свободных членов к элементам разрешающего столбца. При этом при делении на отрицательный, или нулевой элемент разрешающего столбца результат деления полагают равным +. Среди всех этих отношений находят минимальное. Строка, соответствующая мини маль ному отношению, на зывается разрешающей. Пусть, например, это q-ая строка, тогда базисная переменная выводит ся из списка базисных перемен ных. Элемент симплекс – таблицы, стоящий на пе ресечении разрешающих строки и столбца называется разрешающим, в рассмотренном случае это будет элемент .
Шаг. 4.3. Выполнение симплекс – преобразования и переход к новой симплекс – таблице. Элемент новой симплекс-таблицы вычисляется с по мощью следующего симплекс – преобразования:
При проведении симплекс–преобразования весьма удобно поль зо вать ся правилом треугольника:
Для получения элемента новой симплекс–таб лицы надо от элемента предыдущей симплекс–таблицы, стоящего на том же месте, отнять следующее выражение: произведение элемента разрешающей стро ки, стоящего в одном столбце с данным элементом, на элемент данной стро ки, стоящий в одном столбце с разрешающим элементом, деленное на разреша ющий элемент.
Таким образом, при переходе к новой симплекс–таблице все элементы разрешающей строки делятся на разрешающий элемент; все элементы разрешающего столбца, кроме разрешающего элемента, старой таблицы в новой таблице обнуляются, а все остальные элементы старой симплекс–таблицы, включая коэф фициенты целевой функции и свободные члены, пересчи тываются по соответствующей формуле с использованием правила треугольника.
Новое решение имеет следующую структуру: все свободные переменные в нем полагаются равными нулю, а все базисные переменные – свободным чле нам, стоящим в одной строке с ними. После построения новой симплекс–таб лицы следует вернуться к выполнению шага 3.
ПРИМЕР: Найти оптимальное решение задачи линейного программирования заданной математической моде лью вида:
Для решения этой задачи симплекс–методом необходимо привести ее к каноническому виду, добавив в левые части неравенств ограничений по одной дополнительной неотрицательной переменной:
Убедившись, что полученный вид модели является стандарт ным, приступаем к реализации алгоритма решения задачи симплекс– методом.
Шаг 1. Базисные переменные: , а свободные: . При этом началь ное решение имеет вид: при этом .
Шаг 2. Целевая функция уже выражена через свободные переменные.
Шаг 3. Составим начальную симплекс–таблицу (верхняя в каскаде таблиц):
-
БП
СЧ
1
0
1
0
4
0
1
0
1
2
L
-1
-1
0
0
0
1
0
1
0
4
0
1
0
1
2
L
0
-1
1
0
4
1
0
1
0
4
0
1
0
1
2
L
0
0
1
1
6
Просмотрев последнюю строку начальной таблицы, заключаем, что начальное решение не оптимально, т.к. L – строка этой таблицы содержит отрицательные числа в столбцах, соответствующих свободным переменным. Поэтому переходим к шагу 4.
Шаг 4. Поскольку L – строка начальной таблицы содержит два одинаковых отрицательных числа, то безразлично, какое из них выбирать. Выберем для оп ределенности первое из этих чисел, тогда первый столбец будет разрешающим, а переменная будет введена в список базисных.
Подсчитав отношения: , заклю чаем, что разре шаю щей становится первая строка, элемент становится разрешающим элементом (он выделен в начальной таблице жирным шрифтом и подчеркнут), а переменная выводится из состава базисных переменных.
Составим теперь новую симплекс – таблицу, которая помещена ниже пре ды дущей, начальной таблицы, под общей «шапкой».
Замечание. На практике обычно для экономии места все симплекс – табли цы располагают ниспадающим каскадом, одна под другой, под общей вер хней «шапкой».
Возвращаемся к шагу 3. Новое решение имеет вид: , при этом , т.е. значение целевой функции возросло. Но это решение не оптимально, т.к. в столбце L – строки, соответствую щем свободной переменной , имеется отрицательный элемент. При этом, не все остальные элементы этого столбца отрицательные, или нулевые, поэтому это решение может быть улучшено, и мы переходим к шагу 4.
Разрешающим будет второй столбец. Поскольку вторая строка будет разрешающей, а ее элемент разрешающим (аналогично выделен во второй таблице). Учитывая эти результаты, составим новую, третью симплекс – табли цу и возвратимся к шагу 3.
Последнее решение имеет вид: при этом .
Это решение оптимально, т.к. все числа, стоящие в L–строке в столбцах свободных переменных неотрицательны. Это решение единственно, т.к. они строго положительны.
Итак, получено оптимальное решение задачи линейного программирова ния в виде: .
3.1.3. Двойственность в линейном программировании
Произвольную задачу линейного программирования всегда можно сопос тавить с другой задачей линейного программирования, называемой двойствен ной. При этом первоначальную задачу принято называть исходной. Эти две за дачи оказываются тесно связанными между собой и образуют единую двойст венную пару.
Пусть дана исходная задача линейного программирования, заданная математической моделью в неканоническом виде:
Математическая модель двойственной ей задачи линейного программирования составляется по следующим правилам.
Правила составления модели двойственной задачи
Каждому му неравенству системы ограничений исходной задачи ставится в соответствие переменная .
Составляют целевую функцию, коэффициентами которой будут свобод ные члены системы ограничений исходной задачи, т.е. величины .
Составляют систему ограничений по правилу: коэффициенты новой сис темы ограничений образуют транспонированную матрицу коэффици ентов исходной системы ограничений; при этом знаки неравенств из меняют на противоположные.
Свободными членами новой системы ограничений будут коэффициен ты целевой функции исходной задачи.
Все переменные двойственной задачи не отрицательны, а направление оптимизации новой целевой функции противоположно направлению оптимизации целевой функции исходной задачи.
Реализовав перечисленные в правилах действия, получим математическую модель двойственной задачи в виде:
Если модель исходной задачи имеет канонический вид, то при составлении математичес кой модели двойственной задачи используют все правила, приведенные выше, с добавлением еще одного правила:
Ограничениями двойственной задачи будут неравенства, причем, если в целевой функции составляемой двойственной задачи требуется найти минимум, то ставится знак неравенства «больше или равно», если же – максимум, то знак «меньше или равно».
Замечание. При построении математической модели смешанной двойст венной задачи, т.е. когда модель исходной задачи содержит как условия симмет ричной задачи, так и несимметричной, необходимо выполнять все правила, ука занные выше.
Для оптимальных решений задач линейного программирования, образующих двойственную пару справедливы следующие теоремы двойственности.
Теорема 1. Если одна из двойственных задач имеет опти маль ное реше ние, то другая также имеет оптимальное решение, причем для любых оптималь ных решений и выполняется равенство: .
Если же одна из двойственных задач не имеет решения, ввиду того, что: , или: , то другая задача не имеет допустимых ре шений.
Теорема 2. Для оптимальности допустимых решений и пары двойст венных задач необходимо и достаточно, чтобы они удовлетворяли системе урав нений:
Практическая сущность теоремы 2 состоит в следующем: если при под становке оптимального решения в систему ограничений i-ое ограничение исход ной задачи выполняется как строгое неравенство, то i-ая компонента оптималь ного решения двойственной задачи равна нулю, и, наоборот, если i-ая компонен та оптимального решения двойственной задачи положительна, то i-ое ограниче ние исходной задачи удовлетворяется оптимальным решением как равенство.
Обе сформулированные теоремы позволяют определить опти мальное решение одной из задач двойственной пары по оптимальному решению другой.
ПРИМЕР: Математическая модель задачи линейного программи ро вания имеет вид:
Составьте математическую модель двойственной задачи и по оптимальному решению одной из задач найдите оптимальное решение другой.
Применив приведенные правила, получим математическую модель двойственной задачи в виде:
Если решить исходную задачу графическим методом, то полу чим: и при этом: . На основании первой теоремы двойственности зак лючаем, что: . Поскольку полученные оптимальные решения исходной задачи положительны, по второй теоре ме двойственности систему ограничений двойст венной задачи можно записать в виде равенств или уравнений:
Теперь подставим значения и в систему ограничений исходной зада чи и получим:
На этом основании система ограничений двойственной задачи примет вид:
Решая ее, окончательно находим: и при этом: .
Теперь решим обратную задачу. Пусть дано опти мальное решение двойственной задачи: . По первой теореме двойственности имеем: . Так как , то по второй теореме двойственности заключаем, что второе и третье неравен ства исходной задачи обращаются в равенства, или в уравнения:
Решив эту систему, находим: и при этом: .
Рекомендуемая литература по теме 3.1: [3, 5. 6, 7, 8, 10].
ВОПРОСЫ:
Каково основное отличие линейных моделей экономических задач от других видов таких моделей?
При каких условиях задача линейного программирования может быть решена графическим методом?
Из каких двух крупных этапов состоит алгоритм графического метода решения задач линейного программирования?
Чем отличается канонический вид математической модели от неканонического в случае задач линейного программирования?
В чем состоит основная идея симплекс-метода решения задач линейного программирования?
Какую часть оптимального решения двойственной задачи по известному оптимальному решению исходной задачи позволяет найти первая теорема двойственности?
Какую часть оптимального решения двойственной задачи по известному оптимальному решению исходной задачи позволяет найти вторая теорема двойственности?
страница 1 ... страница 6страница 7страница 8страница 9страница 10 ... страница 12страница 13
скачать
Другие похожие работы: