Letysite.ru

IT Новости с интернет пространства
0 просмотров
Рейтинг статьи
1 звезда2 звезды3 звезды4 звезды5 звезд
Загрузка...

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

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

Составляющие математической модели

Основой для решения экономических задач являются математические модели.

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

Составление математической модели включает:

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

Переменными задачи называются величины Х1, Х2, Хn, которые полностью характеризуют экономический процесс. Обычно их записывают в виде вектора: X=(X1, X2. Xn).

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

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

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

Данная запись означает следующее: найти экстремум целевой функции (1) и соответствующие ему переменные X=(X1, X2. Xn) при условии, что эти переменные удовлетворяют системе ограничений (2) и условиям неотрицательности (3).

Допустимым решением (планом) задачи линейного программирования называется любой n-мерный вектор X=(X1, X2. Xn), удовлетворяющий системе ограничений и условиям неотрицательности.

Множество допустимых решений (планов) задачи образует область допустимых решений (ОДР).

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

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

Задача использования ресурсов (сырья)

Условие: Для изготовления n видов продукции используется m видов ресурсов. Составить математическую модель.

Известны:

  • bi ( i = 1,2,3. m) — запасы каждого i-го вида ресурса;
  • aij ( i = 1,2,3. m; j=1,2,3. n) — затраты каждого i-го вида ресурса на производство единицы объема j-го вида продукции;
  • cj ( j = 1,2,3. n) — прибыль от реализации единицы объема j-го вида продукции.

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

Решение:

Введем вектор переменных X=(X1, X2. Xn), где xj ( j = 1,2. n) — объем производства j-го вида продукции.

Затраты i-го вида ресурса на изготовление данного объема xj продукции равны aijxj, поэтому ограничение на использование ресурсов на производство всех видов продукции имеет вид:
Прибыль от реализации j-го вида продукции равна cjxj , поэтому целевая функция равна:

Ответ — Математическая модель имеет вид:

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

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

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

Она может быть представлена в координатной, векторной и матричной записи.

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

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

  • А — матрица коэффициентов системы уравнений
  • Х — матрица-столбец переменных задачи
  • Ао — матрица-столбец правых частей системы ограничений

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

Приведение общей задачи линейного программирования к канонической форме

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

Это может быть сделано следующим образом:

Возьмем линейное неравенство a1x1+a2x2+. +anxn≤b и прибавим к его левой части некоторую величину xn+1 , такую, что неравенство превратилось в равенство a1x1+a2x2+. +anxn+xn+1=b. При этом данная величина xn+1 является неотрицательной.

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

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

Решение:
Перейдем к задаче на отыскивание максимума целевой функции.
Для этого изменим знаки коэффициентов целевой функции.
Для превращения второго и третьего неравенств системы ограничений в уравнения введем неотрицательные дополнительные переменные x4 x5 (на математической модели эта операция отмечена буквой Д).
Переменная х4 вводится в левую часть второго неравенства со знаком «+», так как неравенство имеет вид «≤».
Переменная x5 вводится в левую часть третьего неравенства со знаком «-«, так как неравенство имеет вид «≥».
В целевую функцию переменные x4 x5 вводятся с коэффициентом. равным нулю.
Записываем задачу в каноническом виде:

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

Описание метода

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

Рассмотрим задачу линейного программирования с двумя переменными и :
(1.1) ;
(1.2)
Здесь , есть произвольные числа. Задача может быть как на нахождение максимума (max), так и на нахождение минимума (min). В системе ограничений могут присутствовать как знаки , так и знаки .

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

Графический метод решения задачи (1) следующий.
Вначале мы проводим оси координат и и выбираем масштаб. Каждое из неравенств системы ограничений (1.2) определяет полуплоскость, ограниченную соответствующей прямой.

Так, первое неравенство
(1.2.1)
определяет полуплоскость, ограниченную прямой . С одной стороны от этой прямой , а с другой стороны . На самой прямой . Чтобы узнать, с какой стороны выполняется неравенство (1.2.1), мы выбираем произвольную точку, не лежащую на прямой. Далее подставляем координаты этой точки в (1.2.1). Если неравенство выполняется, то полуплоскость содержит выбранную точку. Если неравенство не выполняется, то полуплоскость расположена с другой стороны (не содержит выбранную точку). Заштриховываем полуплоскость, для которой выполняется неравенство (1.2.1).

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

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

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

Если хотя бы одно неравенство не выполняется, то выбираем другую точку. И так далее, пока не будет найдены одна точка, координаты которой удовлетворяют системе (1.2).

Нахождение экстремума целевой функции

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

Теперь мы можем искать экстремум целевой функции
(1.1) .

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

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

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

Читать еще:  Декларативный язык программирования

Рассмотрим случай, когда крайняя прямая, параллельная произвольной прямой вида (3), проходит через одну вершину многоугольника ОДР. Из графика определяем координаты этой вершины. Тогда максимальное (минимальное) значение целевой функции определяется по формуле:
.
Решением задачи является
.

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

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

Фирма выпускает платья двух моделей А и В. При этом используется ткань трех видов. На изготовление одного платья модели А требуется 2 м ткани первого вида, 1 м ткани второго вида, 2 м ткани третьего вида. На изготовление одного платья модели В требуется 3 м ткани первого вида, 1 м ткани второго вида, 2 м ткани третьего вида. Запасы ткани первого вида составляют 21 м, второго вида — 10 м, третьего вида — 16 м. Выпуск одного изделия типа А приносит доход 400 ден. ед., одного изделия типа В — 300 ден. ед.

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

Пусть переменные и означают количество произведенных платьев моделей А и В, соответственно. Тогда количество израсходованной ткани первого вида составит:
(м)
Количество израсходованной ткани второго вида составит:
(м)
Количество израсходованной ткани третьего вида составит:
(м)
Поскольку произведенное количество платьев не может быть отрицательным, то
и .
Доход от произведенных платьев составит:
(ден. ед.)

Тогда экономико-математическая модель задачи имеет вид:

Решаем графическим методом.
Проводим оси координат и .

Строим прямую .
При .
При .
Проводим прямую через точки (0; 7) и (10,5; 0).

Строим прямую .
При .
При .
Проводим прямую через точки (0; 10) и (10; 0).

Строим прямую .
При .
При .
Проводим прямую через точки (0; 8) и (8; 0).

Прямые и являются осями координат.

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

Заштриховываем область, чтобы точка (2; 2) попала в заштрихованную часть. Получаем четырехугольник OABC.

Строим произвольную линию уровня целевой функции, например,
(П1.1) .
При .
При .
Проводим прямую через точки (0; 4) и (3; 0).

Далее замечаем, что поскольку коэффициенты при и целевой функции положительны (400 и 300), то она возрастает при увеличении и . Проводим прямую, параллельную прямой (П1.1), максимально удаленную от нее в сторону возрастания , и проходящую хотя бы через одну точку четырехугольника OABC. Такая прямая проходит через точку C. Из построения определяем ее координаты.
.

.
То есть, для получения наибольшего дохода, необходимо изготовить 8 платьев модели А. Доход при этом составит 3200 ден. ед.

Пример 2

Решить задачу линейного программирования графическим методом.

Решаем графическим методом.
Проводим оси координат и .

Строим прямую .
При .
При .
Проводим прямую через точки (0; 6) и (6; 0).

Строим прямую .
Отсюда .
При .
При .
Проводим прямую через точки (3; 0) и (7; 2).

Строим прямую .
Строим прямую (ось абсцисс).

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

Заштриховываем область по границам построенных прямых, чтобы точка (4; 1) попала в заштрихованную часть. Получаем треугольник ABC.

Строим произвольную линию уровня целевой функции, например,
.
При .
При .
Проводим прямую линию уровня через точки (0; 6) и (4; 0).
Поскольку целевая функция увеличивается при увеличении и , то проводим прямую, параллельную линии уровня и максимально удаленную от нее в сторону возрастания , и проходящую хотя бы через одну точку треугольника АВC. Такая прямая проходит через точку C. Из построения определяем ее координаты.
.

Пример отсутствия решения

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

Решаем задачу графическим методом.
Проводим оси координат и .

Строим прямую .
При .
При .
Проводим прямую через точки (0; 8) и (2,667; 0).

Строим прямую .
При .
При .
Проводим прямую через точки (0; 3) и (6; 0).

Строим прямую .
При .
При .
Проводим прямую через точки (3; 0) и (6; 3).

Прямые и являются осями координат.

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

Заштриховываем область, чтобы точка (3; 3) попала в заштрихованную часть. Получаем неограниченную область, ограниченную ломаной ABCDE.

Строим произвольную линию уровня целевой функции, например,
(П3.1) .
При .
При .
Проводим прямую через точки (0; 7) и (7; 0).
Поскольку коэффициенты при и положительны, то возрастает при увеличении и .

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

Ищем минимум. Проводим прямую, параллельную прямой (П3.1) и максимально удаленную от нее в сторону убывания , и проходящую хотя бы через одну точку области ABCDE. Такая прямая проходит через точку C. Из построения определяем ее координаты.
.
Минимальное значение целевой функции:

Максимального значения не существует.
Минимальное значение
.

Автор: Олег Одинцов . Опубликовано: 08-08-2016

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

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

Размещено на http://www.stud.wiki/

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

Условие задачи №1

Задача о выборе оптимальных технологий

Продукция в цехе может производиться n различными способами Tj (n=3). Для производства продукции могут использоваться ресурсы: рабочая сила, сырьё (сталь, древесина, цветные металлы), электроэнергия. Обозначения:

xj — время использования технологического способа Tj при производстве продукции (j=1,2,3);

aij — расход ресурса Ri за единицу времени по технологии Tj;

A — годовое плановое задание по выработке продукции (ден. ед.);

cj — производительность технологии Tj (в денежных единицах за единицу времени работы по данной технологии);

lj — затраты на изготовление продукции в единицу времени по технологии Tj (денежных единицах).

Налагаются ограничения по объемам bi ресурсов (вида ) и по плановому выпуску A продукции (вида ).

Возможны три критерия f1, f2, f3 оптимальности плана X=(x1,…,xn) применения каждого технологического способа:

а) f1 — наибольший объем выпускаемой продукции по всем технологиям (ден. ед.);

б) f2 — наименьшие затраты на выполнение планового задания (ден. ед.);

в) f3 — наибольшая конечная прибыль от выпуска продукции с учетом затрат на изготовление продукции (ден. ед.).

В табл. 1 представлены объемы bi ресурсов Ri, их расход aij в единицу времени для каждой технологии, плановое задание A, производительности cj технологий Tj и затраты lj.

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

2. Дать математические постановки задач.

3. Привести полученные три математические модели к каноническому виду. Указать экономический смысл дополнительных (балансовых) переменных.

Рабочая сила, чел-ч

Электроэнергия, кВт ч

Производительность технологического способа, ден. ед.

Затраты в ед. времени работы по технологическому способу, ден. ед.

а) Пусть требуется реализовать первый критерий f1 оптимальности плана X=(x1,…,xn), т.е. объем выпускаемой продукции по всем технологиям должен быть наибольшими. Поскольку x1, x2, x3 время использования технологического способа T1, T2, T3, соответственно, то объем использования каждого ресурса в соответствии с таблицей будет равен:

При этом потребление каждого ресурса не должно превышать их объемов, т.е. 684, 690, 558, соответственно. Таким образом, связь между потреблением ресурсов и их объемами выражается следующей системой неравенств:

Читать еще:  Уроки программирования на языке паскаль

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

Добавляя сюда условия неотрицательности

Сформулируем математическую модель задачи по критерию №1:

Найти такой план использования технологических способов X=(x1, x2, x3), который удовлетворяет системе (1) и условиям (3), при которых целевая функция (2) принимает максимальное значение.

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

Новые переменные имеют следующий смысл: x4 — количество неиспользуемой рабочей силы, x5 — количество неиспользуемого сырья, x6 — количество неиспользуемой электроэнергии.

б) Пусть требуется реализовать второй критерий f2 оптимальности плана X=(x1,…,xn), т.е. затраты на выполнение планового задания должны быть наименьшими. В отличие от выше рассмотренной задачи, здесь добавляется дополнительное условие, т.е. кроме ограничений по объемам ресурсов налагаются условия по плановому выпуску продукции. Учитывая производительность каждого технологического способа и годовое плановое задание по выработке продукции, по данным табл. 1 получим ограничение 51x1 + 38x2 + 42x3 ? 5370. Таким образом, система ограничений будет иметь вид

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

Сформулируем математическую модель задачи по критерию №2:

Найти такой план использования технологических способов X=(x1, x2, x3), удовлетворяющий системе (5) и условиям (6), при которых целевая функция (7) принимает минимальное значение.

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

Новые переменные имеют следующий смысл: x4 — количество неиспользуемой рабочей силы, x5 — количество неиспользуемого сырья, x6 — количество неиспользуемой электроэнергии, x7 — количество продукции, выработанной сверх плана.

в) Пусть требуется реализовать третий критерий f3 оптимальности плана X=(x1,…,xn), т.е. конечная прибыль от выпуска продукции с учетом затрат на изготовление продукции должна быть наибольшей. В отличие от случая а), целевая функция будет иметь вид

математический линейный программирование

Сформулируем математическую модель задачи по критерию №3:

Найти такой план использования технологических способов X=(x1, x2, x3), удовлетворяющий системе (1) и условиям (3), при которых целевая функция (9) принимает максимальное значение.

В каноническом виде задача формулируется следующим образом: найти максимум целевой функции (9) при ограничениях

Новые переменные имеют следующий смысл: x4 — количество неиспользуемой рабочей силы, x5 — количество неиспользуемого сырья, x6 — количество неиспользуемой электроэнергии.

2. Графическое решение задачи линейного программирования

Условие задачи №2

Задача о выборе оптимальных технологий

Предприятие выпускает продукцию вида P1 и P2, на изготовление которой используется сырье S1, S2, S3. Известны:

bi — запасы сырья; aij — нормы расхода сырья Si (i=1,2,3) на производство единицы продукции (j=1,2); cj — себестоимость единицы продукции Pj; pj — оптовая цена единицы Pj.

Определить оптимальный план X=(x1,x2) производства продукции P1 и P2, при котором при имеющемся количестве сырья можно получить наибольшую прибыль.

1. Записать числовые данные таблицу и составить математическую модель задачи.

2. Решить задачу графическим методом.

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

4. Определить аналитически и графически, можно ли произвести 3 ед. продукции P1 и 2 ед. продукции P2.

Презентация по дисциплине «Математическое моделирование» на тему «Линейное программирование»

Как организовать дистанционное обучение во время карантина?

Помогает проект «Инфоурок»

Описание презентации по отдельным слайдам:

Линейное программирование Термин «линейное программирование» характеризует определение программы работы конкретного экономического объекта на основе выявления линейных связей между его элементами

Задачи линейного программирования Нахождение оптимального плана выпуска продукции (оптимальное распределение ресурсов) Оптимизация межотраслевых потоков (планирование производства различных видов продукции по отраслям) Определение оптимального рациона (оптимизация состава химической смеси) Транспортная задача (оптимальное распределение потоков товарных поставок по транспортной сети) Задача о размещении производства (планирование с учетом затрат на производство и транспортировку продукции) Задача о назначениях (оптимальное распределение различных видов транспортных средств) И др.

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

Линейное программирование Решение экстремальных задач можно разбить на 3 этапа: Построение экономико-математической модели Нахождение оптимального решения одним из математических методов Практическое внедрение

Линейное программирование Любая задача линейного программирования включает следующие 3 элемента: Переменные; Целевая функция (функция подлежащая минимизации или максимизации); Ограничения, которым переменные должны удовлетворять

Основная задача линейного программирования Дана линейная форма (целевая функция) Z = C1X1 + C2X2 + . . . + CnXn и задана система линейных неравенств (ограничений) a11x1 + a12x2 + . . . + a1nxn ≤ b1 a21x1 + a22x2 + . . . + a2nxn ≤ b2 . . . . . . . . . . . . . . . . . . . . . . . . am1x1 + am2x2 + . . . + amnxn ≤ bm причем Xj ≥ 0 (j = 1,n) Найти максимальное (минимальное) значение функции Z при выполнении условий

Основная задача линейного программирования Этапы графического метода решения ЗЛП: 1. Построение области допустимых решений. Ограничения ЗЛП в виде неравенств задают выпуклую многогранную область, которая носит название «область допустимых решений». В силу условия неотрицательности переменных x1 и x2 область располагается в первой четверти координатной плоскости (x1 ≥ 0, x2 ≥ 0). Область допустимых решений может иметь вид выпуклого многогранника или выпуклого многогранного неограниченного множества (рис.1). а) выпуклый многогранник; б) выпуклое многогранное неограниченное множество

Основная задача линейного программирования Графический метод решения В С А D 0 c Z=0

Основная задача линейного программирования 2. Исследование поведения целевой функции на области допустимых решений при помощи линий уровня. Линия уровня С — линия, на которой значение целевой функции равно С (то есть график F(x) = C). Рисуем линии уровня при разных значения С и определяем направление движения по линиям уровня (переход от одной линии уровня к другой) при увеличении значения С. Таким образом, с помощью линий уровня можно определить направление возрастания (убывания) значения целевой функции. 3. Нахождение решения. Продвигаем линии уровня в направлении возрастания значения целевой функции, если в задаче требуется найти ее максимум (в направлении убывания, если требуется найти минимум), до достижения последнего касания с областью допустимых решений. Эта линия уровня является «экстремальной».

Основная задача линейного программирования Пример. Найти графическое оптимальное решение системы неравенств 2×1 + x2 ≥ 2 x1 + 3×2 ≥ 3 x1 — x2 ≥ -1 3×1 — x2 ≤ 6 x1 + x2 ≤ 5 x1 ≥ 0 x2 ≥ 0 а) максимизирующее функцию Z = x1 + 2×2 б) минимизирующее функцию Z = x1 + 2×2

Основная задача линейного программирования X1 X2 1 2 3 4 5 C(1;2) А В С D Е

Основная задача линейного программирования 2×1 + x2 = 2 x1 + 3×2 = 3 x1 — x2 = -1 x1 + x2 = 5 D (0,6; 0,8) А (2; 3) Zmin = 0,6 + 2*0,8 = 2,2 Zmax = 2 + 2*3 = 8

Основная задача линейного программирования Задача Z = 3x + 2y max 2x – 3y ≤ 12 -x +2y ≤ 6 x ≤ 6 2x + 5y ≤ 10 x≥0 y ≥0

Выберите книгу со скидкой:

ЕГЭ. География. Новый полный справочник для подготовки к ЕГЭ

350 руб. 163.00 руб.

350 руб. 171.00 руб.

ЕГЭ-2019. География. Теория и практика

350 руб. 213.00 руб.

ОГЭ. География. Большой сборник тематических заданий для подготовки к основному государственному экзамену

350 руб. 197.00 руб.

География. 10-11 классы. Атлас. (Традиционный комплект) (РГО)

350 руб. 106.00 руб.

География. 7 класс. Атлас. (Традиционный комплект)(РГО)

350 руб. 106.00 руб.

География. 5 класс. Атлас. (Традиционный комплект).

350 руб. 106.00 руб.

География. 10-11 классы. Контурные карты. (Традиционный комплект) (РГО)

350 руб. 59.00 руб.

География. 6 класс. Атлас. (Традиционный комплект)(РГО)

350 руб. 106.00 руб.

География. Материки, океаны, народы и страны. 7класс. Атлас

350 руб. 184.00 руб.

География. 9 класс. Контурные карты. (Традиционный комплект) (РГО)

350 руб. 59.00 руб.

География. Начальный курс географии. 6класс. Контурные карты

350 руб. 101.00 руб.

БОЛЕЕ 58 000 КНИГ И ШИРОКИЙ ВЫБОР КАНЦТОВАРОВ! ИНФОЛАВКА

Инфолавка — книжный магазин для педагогов и родителей от проекта «Инфоурок»

Моделирование задач линейного программирования в среде МС EXCEL

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

Читать еще:  Программа языки программирования

Порядок установки для Офиса 2003:

— выбрать режим «Сервис»,

— установить «Поиск решений».

Порядок установки для Офиса 2007:

— войти в «Параметры EXCEL»,

— выбрать «Поиск решения»,

— отметить галочкой «Поиск решения»,

— в «Данных» должен появиться режим «Поиск решения».

Модель задачи в среде EXCEL реализуется в виде таблиц. В качестве примера рассмотрим задачу выпуска продукции (приведенную в разделе 4.2.). Необходимо определить план выпуска двух видов продукции для получения максимальной прибыли. Трудозатраты на производство продукции А – 20ч., продукции В – 10ч. Недельный лимит трудозатрат – 400 ч. Максимальный объем выпуска продукции А — 15 ед., продукции В — 30 ед. в неделю. Прибыль от реализации 1ед. продукции А – 50у.е.; В — 40у.е.

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

Числовые данные постановки заносятся в таблицу EXCEL. Ячейки х1 и х2 остаются свободными и указываются в экранной форме «Поиск решения» в качестве переменных. В остальные ячейки (выделены цветом) необходимо занести формулы, отображающие связи и отношения между числами модели.

Заполняем окна экранной формы:

· — «Установить целевую ячейку: » – вносим адрес целевой ячейки.

· — «Равной:» – устанавливаем максимальное значение целевой функции.

· — «Изменяя ячейки:» – указываем адреса переменных х1 и х2 .

· — «Ограничения:» – вносим ограничения модели.

Окно «Поиск решения» с занесенной информацией выглядит следующим образом (рис. 14).

Рис. 14 Экранная выдача режима «Поиск решения»

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

ТЕМА 5

5.1. Объекты имитационного моделирования.

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

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

В тех случаях, когда построение аналитической модели по той или иной причине трудно осуществимо, применяется метод моделирования, известный под названием метода статистических испытаний или, иначе, метода Монте-Карло. С помощью этого метода строятся так называемые имитационные модели.

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

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

Суть имитационного подхода раскрывается в самом названии. Мы имитируем процесс функционирования системы во времени.

Отличительной чертой любой имитационной модели является структурное сходство с самой системой.

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

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

Стохастичность — неизбежное свойство реальных сложных систем.

5.2. Оптимизация решения задач моделирования

Имитационная модель дает случайное значение результата моделирования (значения параметра, который необходимо оптимизировать). Оно называется реализацией модели. Но случайный результат не дает решение задачи. В этом случае применяется многократная реализация модели. В результате мы получаем множество случайных результатов (при заданном наборе исходных данных). Далее применяется аппарат математической статистики для обработки результатов моделирования. Можно получить усредненный результат, математическое ожидание его, рассчитать точность результата и т.п.

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

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

5.3. Метод Монте-Карло

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

Например. Построим модель процесса стрельбы спортсмена по мишени. Пусть известно из опыта, что вероятность Р попадания его в цель составляет 0,8. Тогда, используя датчик (или таблицу) случайных чисел на отрезке 0-1, выбираем случайное число R. Если выпадет число больше 0,8, то спортсмен попал в мишень (состоялось событие А). Если меньше 0,8, то произошел промах (состоялось событие Ā).

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

Основным элементом, из совокупности которых складывается имитационная модель, является одна случайная реализация моделируемого явления, например: один «обстрел» цели», один «день работы» транспорта и т.п. Реализация представляет собой как бы один случай осуществления моделируемого случайного процесса со всеми присущими ему случайностями.

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

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

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

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

Для построения моделей методом Монте-Карло необходимо знать вероятностные характеристики случайных факторов, необходимо иметь статистику процессов.

Методом Монте-Карло может быть решена любая вероятностная задача. Но метод используется только тогда, когда процедура розыгрыша проще, а не сложнее аналитического расчета.

Приведем пример, когда метод Монте-Карло возможен, но не рационален. Пусть спортсмен производит несколько независимых выстрелов по мишени. Каждый выстрел попадает в мишень (событие А) с одинаковой вероятностью Р(А). Требуется найти вероятность хотя бы одного попадания.

Модель процесса попадания в мишень хотя бы одним выстрелом можно представить в аналитическом виде

Рассмотрим частный случай, когда Р(А)=0,5, а количество выстрелов равно 3. Тогда

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

А вот пример задачи, которую аналитически решать крайне сложно — задача о «случайном блуждании». Прохожий решил прогуляться, стоя на углу пересечения улиц. Пусть вероятность того, что, достигнув очередного перекрестка, он пойдет на север, юг, восток и запад, одинакова. Спрашивается, какова вероятность того, что пройдя 10 кварталов, прохожий окажется не далее 2 кварталов от места, где он начал прогулку?

Количество исходов на каждом перекрестке равно 4. Тогда общее количество исходов равно 4 10 . Эту задачу модно решить только имитацией – розыгрышем. Другими методами ее решить практически невозможно.

Метод имитационного моделирования может рассматриваться как своеобразный экспериментальный метод. Отличие от обычного эксперимента заключается в том, что в качестве объекта экспериментирования выступает имитационная модель, реализованная в виде программы на ЭВМ или в виде некоторого игрового эксперимента.

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

Ссылка на основную публикацию
Adblock
detector