Экономико-математическое моделирование

Размещено на http://www.allbest.ru/

1. Сформулируйте задачу о загрузке оборудования

ПОСТАНОВКА ЗАДАЧИ.

Допустим, ткацкая фабрика располагает двумя видами станков, из них N1 станков типа 1 и N2 станков типа 2.

Станки могут производить три вида тканей: T1, T2, T3, но с разной производительностью.

Данные aij производительности станков в таблице (первый индекс - тип станка, второй - вид ткани).

Каждый метр ткани вида T1 приносит фабрике доход c1, вида Т2 - доход с2, Т3 - доход с3.

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

Фабрике предписан план согласно которому она должна производить в месяц не менее b1 метров ткани Т1, b2 метров ткани Т2, b3 метров ткани Т3.

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

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

МАТЕМАТИЧЕСКАЯ МОДЕЛЬ.

Введём букву x с двумя индексами (первый - тип станка, второй - вид ткани). Всего будет шесть элементов решения: x11 x12 x13 x21 x22 x23 .

Здесь x11 - количество станков типа 1, занятых изготовлением ткани Т1, x12 - количество станков типа 1, занятых изготовлением ткани Т2 и т.д.

Запишем суммарный доход от производства всех видов тканей. Суммарное количество метров ткани Т1, произведённое всеми станками, будет равно a11x11+a21x21 и принесёт доход c1(a11x11+a21x21).

Целевая функция: L=c1 (a11x11+a21x21)+c2 (a12x12+a22x22)+c3

(a13x13+a23x23) > max.

Система ограничений:

Обеспечим выполнения плана ограничениями по минимальным параметрам:

a11x11+a21x21b1,

a12x12+a22x22b2,

a13x13+a23x23b3,

После этого ограничим выполнение плана по максимальным параметрам:

a11x11+a21x211,

a12x12+a22x222,

a13x13+a23x233,

Теперь запишем ограничения, связанные с наличием оборудования и его полной загрузкой. Суммарное количество станков типа 1, занятых изготовлением всех тканей, должно быть равно N1; типа 2 - N2.

x11+x12+x13=N1,

x21+x22+x23=N2,

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

Симплекс-метод -- алгоритм решения оптимизационной задачи линейного программирования путём перебора вершин выпуклого многогранника в многомерном пространстве. Метод был разработан американским математиком Джорджем Данцигом в 1947 году.

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

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

Теперь поставим эту задачу в эквивалентной усиленной форме. Необходимо максимизировать Z, где:

Здесь x -- переменные из исходного линейного функционала, xs -- новые переменные, дополняющие старые таким образом, что неравенство переходит в равенство, c -- коэффициенты исходного линейного функционала, Z -- переменная, которую необходимо максимизировать.

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

Проще говоря, если мы рассматриваем вершину многогранника, то это число рёбер, по которым мы можем продолжать движение. Тогда мы можем присвоить этому числу переменных значение 0 и назвать их «непростыми».

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

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

Алгоритм.

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

где cB -- коэффициенты вектора c соответствующие простым переменным (переменным xs соответствуют 0), B -- столбцы , соответствующие простым переменным. Матрицу, образованную оставшимися столбцами обозначим D. Почему матрица будет иметь такой вид поясним в описании шагов алгоритма.

Выбираем начальное допустимое значение, как указано выше. На первом шаге B -- единичная матрица, так как простыми переменными являются xs. cB -- нулевой вектор по тем же причинам.

Покажем, что в выражении только непростые переменные имеют ненулевой коэффициент. Заметим, что из выражения Ax+xs=b простые переменные однозначно выражаются через непростые, так как число простых переменных равно числу уравнений. Пусть x' -- простые, а x' '-- непростые переменные на данной итерации. Уравнение Ax+xs=bможно переписать, как Bx '+Dx' '=b. Умножим его на B - 1 слева: x' + B ? 1Dx'' = B ? 1b.

Таким образом, мы выразили простые переменные через непростые, и в выражении B ? 1Ax + B ? 1xs, эквивалентному левой части равенства, все простые переменные имеют единичные коэффициенты. Поэтому, если прибавить к равенству Z ? cTx = 0 равенство , то в полученном равенстве все простые переменные будут иметь нулевой коэффициент -- все простые переменные вида x сократятся, а простые переменные вида xs не войдут в выражение .

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

.

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

При фиксированных значениях непростых переменных система однозначно разрешима относительно простых, поэтому мы можем определить, какая из простых переменных первой достигнет нуля при увеличении входящей. Эту переменную назовем выходящей. Это будет означать, что мы натолкнулись на новую вершину. Теперь входящую и выходящую переменную поменяем местами -- входящая «войдёт» в простую, а выходящая из них «выйдет» в непростые. Теперь перепишем матрицу B и вектор cB в соответствии с новыми наборами простых и непростых переменных, после чего вернёмся ко второму шагу. x''

3. Сформулируйте задачу планирования производства

ПОСТАНОВКА ЗАДАЧИ. Допустим, предприятие производит изделия трёх видов: U1, U2, U3. По каждому виду изделия предприятию спущен план, по которому оно обязано выпустить не мене b1 единиц изделия U1, не мене b2 единиц изделия U2 и не мене b3 единиц изделия U3. План может быть перевыполнен, но в определённых границах; условия спроса ограничивают количества произведённых единиц каждого типа: не более соответственно 1, 2, 3 единиц. На изготовление изделий идёт какое-то сырьё; всего имеется четыре вида сырья: s1, s2, s3, s4, причём запасы ограничены числами 1, 2, 3, 4 единиц каждого вида сырья. Теперь надо узнать какое количество сырья каждого вида идёт на изготовление каждого вида изделий. Обозначим aij количество единиц сырья вида si (I= 1, 2, 3, 4), потребное на изготовление одной единицы изделия Uj (j= 1, 2, 3). Первый индекс у числа aij - вид изделия, второй - вид сырья. Значения aij сведены в таблицу (матрицу).

При реализации одно изделие U1 приносит предприятию прибыль c1, U2 - прибыль c2, U3 - прибыль c3. Требуется так спланировать производство (сколько каких изделий производить), чтобы план был выполнен или перевыполнен (но при отсутствии «затоваривания»), а суммарная прибыль обращалась в максимум.

МАТЕМАТИЧЕСКАЯ МОДЕЛЬ. Элементами решения будут x1, x2, x3 - количества единиц изделий U1, U2, U3, которые мы произведём. Обязательность выполнения планового задания запишется в виде трёх ограничений - неравенств: x1b1, x2b2, x3b3.

Отсутствие изделий продукции (затоваривания) даёт нам ещё три ограничения - неравенства: x11, x22, x33.

Целевая функция: L=c1x1+c2x2+c3x3> max.

Система ограничений:

a11x1+a21x2+a31x31.

a12x1+a22x2+a32x32.

a13x1+a23x2+a33x33.

a14x1+a24x2+a34x34.

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

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

(1):Z = с1*х1+с2*х2

при

(2):a11x1 + a22x2 <= b1,a21x1 + a22x2 <= b2,...,an1x1 + an2x2 <= bn;

(3):х1>=0, х2>=0.

Допустим, что система (2) при условии (3) совместна и её многоугольник решений ограничен. Каждое из неравенств (2) и (3), как отмечалось выше, определяет полуплоскость с граничными прямыми:

ai1x1 + ai2x2 + ai3x3 = bi, (i = 1, 2, …, n), х1=0, х2=0.

Линейная функция (1) при фиксированных значениях Z является уравнением прямой линии:

c1х1 + c2х2 = const.

Построим многоугольник решений системы ограничений (2) и график линейной функции (1) при Z = 0.

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

Найти точку многоугольника решений, в которой прямая c1х1 + c2х2 = const опорная и функция Z при этом достигает минимума.

Значения Z = c1х1 + c2х2 возрастают в направлении вектора N =(c1, c2), поэтому прямую Z = 0 передвигаем параллельно самой себе в направлении вектора N.

Прямая дважды становится опорной по отношению к многоугольнику решений (в точках А и С), причем минимальное значение принимает в точке А. Координаты точки А (х1, х2) находим, решая систему уравнений прямых АВ и АЕ.

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

Случай 1. Прямая с1х1 + с2х2 = const, передвигаясь в направлении вектора N или противоположно ему, постоянно пересекает многоугольник решений и ни в какой точке не является опорной к нему. В этом случае линейная функция не ограничена на многоугольнике решений как сверху, так и снизу.

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

Размещено на Allbest.ru