Построение математических моделей

↑

▷ Содержание

⇐ ПредыдущаяСтр 12 из 188Следующая ⇒

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

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

— запасы -го вида ресурса;

— затраты -го вида ресурса на производство единицы -го вида продукции;

— прибыль от реализации единицы -го вида продукции. Данные задачи можно представить в виде таблицы.

Обозначим через планируемый выпуск -го вида продукции; — план выпуска продукции. Тогда прибыль от реализации всей выпускаемой продукции составит

Составим ограничения по ресурсам. Найдем расход ресурса первого вида при данном плане выпуска:

Ресурса первого вида имеется в наличии условных единиц, т.е. получаем ограничение

Аналогично составляем ограничения по всем остальным видам ресурсов.

Кроме того, , так как количество продукции не может быть отрицательным числом.

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

при ограничениях

Задача о диете

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

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

Введем обозначения:

— содержание -го питательного вещества в единице -го продукта;

— минимальное содержание -го питательного вещества в суточной диете;

— цена единицы — го продукта.

Данные задачи можно представить в виде таблицы.

Пусть единиц -го продукта включается в суточную диету, тогда

—суточная диета. Цена диеты:

Содержание первого питательного вещества в диете составит

и это количество должно быть не менее чем единиц:

Аналогично составляем ограничения по всем видам питательных веществ.

Кроме того, , так как количество продуктов не может быть отрицательным числом.

Математическая модель задачи: найти минимум функции

при ограничениях:

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

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

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

Составим математическую модель данной задачи. Введем обозначения: — номер вида заготовки, ; — номер варианта раскроя прутка, ;

— количество заготовок -го вида, получаемых из одного прутка, разрезаемого по -му варианту;

— требуемое число заготовок -го вида;

— длина концевого отрезка, оставшегося от одного прутка при разрезании прутка по -му варианту.

Данные задачи можно представить в виде таблицы.

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

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

Следовательно, общая длина концевых отрезков при разрезании прутков по всем вариантам составляет

Составим ограничения по заготовкам.

Из одного прутка, разрезаемого по первому варианту, получают шт. заготовок первого вида, а из прутков — шт.; по второму вариант) из одного прутка получают шт., а из прутков — шт. и т.д., по -му варианту — шт. Отсюда получаем первое ограничение

Аналогично получаем ограничения по всем заготовкам.

Кроме того, так как число прутков не может быть отрицательным.

Математическая модель задачи: найти наименьшее значение функции

при ограничениях:

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

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

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

при ограничениях:

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

1. Область допустимых решений — пустое множество. В этом случае задача линейного программирования не имеет оптимального решения из-за несовместности системы ограничений.

2. Область допустимых решений — единственная точка. Тогда задача линейного программирования имеет единственное и оптимальное решение.

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

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

Пусть — некоторое число. Прямая является линией уровня целевой функции. В каждой точке этой прямой целевая функция принимает одно и то же значение, равное . Вектор — градиент целевой функции

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

· Область допустимых решений — выпуклая неограниченная область.

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

Алгоритм графического метода:

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

2. Построить вектор-градиент целевой функции .

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

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

5. Найти координаты точек экстремума и значение целевой функции в этих точках.

Возможно эта страница вам будет полезна:

Пример задачи №5

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

Решение:

1) Строим область допустимых решений (ОДР). Она представляет собой выпуклый четырехугольник (рис. 2.1).

2) Строим вектор (3; 4) и перпендикулярно ему линии уровня, проходящие через область.

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

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

Решим систему, составленную из уравнений этих прямых

Получим

Точка лежит на пересечении второй и четвертой прямых. Решим систему, составленную из уравнений этих прямых

Получим

Пример задачи №6

Найти наибольшее значение функции

при ограничениях:

Решение:

1) Строим область допустимых решений. Получим пятиугольник (рис.22).

2) Строим вектор (2; 4) и перпендикулярно ему линию уровня .

3) В данном случае линии уровня параллельны прямой, проходящей через точки и .

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

Получим

Точка лежит на пересечении первой и второй прямых. Решая систему, составленную из уравнений этих прямых, получим

Так как целевая функция принимает наибольшее значение в любой точке отрезка , то

Пример задачи №7

Найти наибольшее значение функции

при ограничениях:

Решение:

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

ОДР представляет собой выпуклую неограниченную область (рис. 2.3).

2) Строим вектор (2; 5) и линию уровня , перпендикулярную к вектору .

3) Так как в направлении вектора с можно провести сколь угодно удаленную линию уровня, проходящую через ОДР, следовательно, функция в этой области не достигает своего наибольшего значения

Пример задачи №8

Найти наибольшее значение функции при ограничениях:

Решение:

Выразим базисные переменные через свободные:

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

Получим:

Так как

то получим систему неравенств

Исходная задача сведена к новой, которую можно решить графически.

Решая эту задачу графически, получим

Найдем оптимальное решение исходной задачи, для этого найдем значения базисных переменных при

Тогда

Возможно эта страница вам будет полезна:

Симплексный метод решения

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

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

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

Алгоритм симплексного метода

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

2. Найти неотрицательное базисное решение системы ограничений.

3. Рассчитать оценки свободных переменных по формуле

где — коэффициенты при свободной переменной ,

— коэффициенты при базисных переменных в целевой функции,

— коэффициент при свободной переменной в целевой функции.

· Проверить найденное опорное решение на оптимальность:

а) если все оценки , то найденное решение оптимально и задача решена;

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

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

Замечание 1. Критерием оптимальности для ЗЛП на минимум является неположительность оценок, т.е. все

Замечание 2. В ЗЛП максимум и минимум целевой функции понимаются как глобальные.

Пример задачи №9

Найти наибольшее значение функции

при ограничениях:

Решение:

Задача имеет канонический вид. Найдем исходное опорное решение.

Проверим это решение на оптимальность.

Найденное решение не оптимально, так как . Введем в базис свободную переменную с отрицательной оценкой .

Так как среди оценок нет отрицательных чисел, то второе опорное решение оптимально.

Пример задачи №10

Найти наибольшее значение функции

при ограничениях:

Решение:

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

Найдем исходное опорное решение.

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

Отбросим балансовые переменные, получим оптимальное решение исходной задачи:

Возможно эта страница вам будет полезна:

Метод искусственного базиса

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

Алгоритм метода искусственного базиса

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

2. Построить -задачу. Для этого в каждое уравнение системы ограничений, не имеющее переменной, исключенной из других уравнений, необходимо ввести искусственную переменную с коэффициентом 1, не меняя знак равенства. Искусственные переменные также вводятся и в целевую функцию с коэффициентом — (или + , если решается задача на минимум), где — сколь угодно большое число.

3. Выписать исходное опорное решение.

4. Рассчитать оценки свободных переменных по формуле

где

— коэффициенты при свободной переменной

— коэффициенты при базисных переменных в целевой функции,

— коэффициент при свободной переменной в целевой функции; и записать оценки в двух строках и : строка содержит коэффициенты при множителе в оценке ; строка содержит другую часть оценки.

· Решить -задачу симплексным методом. Критерий оптимальности проверяется по строке так же, как и в симплексном методе. Учесть следующие возможные случаи:

а) если в оптимальном решении -задачи все искусственные переменные равны 0, то соответствующее решение исходной задачи является оптимальным и экстремумы целевых функций равны;

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

в) если -задача не имеет оптимального решения, то исходная задача также не имеет оптимального решения.

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

· Когда все искусственные переменные будут выведены из базиса, а оценочная строка будет заполнена нулями, завершить решение задачи обычным симплексным методом, считая строкой оценок строку .

Пример задачи №11

Найти наибольшее значение функции

при ограничениях:

Решение:

Задача дана в каноническом виде. Составим -задачу, для этого введем в первое уравнение искусственную базисную переменную во второе уравнение . -задача примет вид

Решим -задачу симплексным методом.

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

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

Теория двойственности

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

В зависимости от вида исходной задачи различают симметричные, несимметричные и смешанные пары двойственных задач.

Пара двойственных задач называется симметричной, если одна из задач задана в симметричном виде.

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

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

Правило составления двойственных задач. Симметричная пара

· Каждому ограничению исходной задачи ставится в соответствие двойственная переменная где .

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

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

Итак, двойственная задача состоит в нахождении наименьшего значения функции

при ограничениях:

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

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

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

при ограничениях:

Двойственная задача состоит в нахождении наименьшего значения функции:

при ограничениях:

Пусть исходная задача имеет вид:

при ограничениях:

Тогда двойственная задача имеет вид:

при ограничениях:

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

При построении двойственной задачи в смешанной паре придерживаются следующего правила. Если двойственная переменная поставлена в соответствие ограничению-неравенству, то она неотрицательна, если уравнению — то произвольна по знаку. Если исходная переменная неотрицательна, ей ставится в соответствие ограничение-неравенство; если переменная произвольна по знаку — соответствующее ей ограничение — уравнение. Далее используют то же правило, что и для симметричной пары.

Пусть исходная задача имеет вид:

при ограничениях:

Тогда двойственная задача имеет вид:

при ограничениях:

Возможно эта страница вам будет полезна:

Пример задачи №12

Составить двойственную задачу к следующей: найти наибольшее значение функции

при ограничениях:

свободны по знаку.

Двойственная задача: найти наименьшее значение функции

при ограничениях:

свободны по знаку, .

Нахождение решения двойственных задач

Первый способ нахождения решения двойственной задачи в симметричной паре основан на применении основных теорем двойственности.

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

Если целевая функция одной из задач не ограничена на ОДР, то система ограничений двойственной задачи не совместна, и наоборот.

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

Пример задачи №13

Дана задача линейного программирования в неканоническом виде

Данная задача имеет оптимальное решение

Составим двойственную задачу:

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

Применим вторую теорему двойственности: так как в оптимальном решении исходной задачи

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

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

Получим систему трех уравнений с тремя неизвестными:

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

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

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

Запишем системы ограничений симметричной пары двойственных задач:

Приведем их к каноническому виду:

где — основные, — балансовые: — балансовые, — основные. Если исходная задача решена симплексным методом, то

где — симплексные оценки переменных исходной задачи. Если двойственная задача решена симплексным методом, то

где — симплексные оценки переменных двойственной задачи.

Пример задачи №14

Найти наименьшее значение функции

при ограничениях:

Решение:

Составим двойственную задачу:

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

Целевая функция остается без изменения.

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

Тогда по <

⇐ Предыдущая78910111213141516Следующая ⇒

Поделиться:

Познавательные статьи:



Коммуникативные барьеры и пути их преодоления

Рынок недвижимости. Сущность недвижимости

Решение задач с использованием генеалогического метода

История происхождения и развития детской игры