Математическое программирование: Линейное программирование. Постановка задач, методы решения

Построим математическую модель задачи.

Переменные задачи

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

 – суточный объем производства радиоприемников первой модели, [шт/сутки];

 – суточный объем производства радиоприемников второй модели, [шт/сутки];

Целевая функция

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

            их объемы производства, т.е. и радиоприемников в сутки;

            прибыль от их реализации  – согласно условию, соответственно 40$ и 20$.

Таким образом, доход от продажи суточного объема производства радиоприемников первой модели равен $ в сутки, а от продажи радиоприемников второй модели – $  в сутки. Поэтому запишем ЦФ в виде суммы дохода от продажи радиоприемников первой и второй модели:

[$/сутки]

Ограничения

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

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

                  суточный объем первой технологической линии (производство радиоприемников первой модели) не может превышать 60 шт в сутки, второй (производство радиоприемников второй модели) – 80 шт;

                  объемы производства радиоприемников не могут быть отрицательными.

Таким образом, все ограничения задачи делятся на 3 группы, обусловленные:

1) расходом элементов электронных схем;

2) суточным объемом технологических линий;

3) неотрицательностью объемов производства.

Запишем эти ограничения в математической форме:

1)                 Т.к. из условия на радиоприемники первой и второй модели необходимо 15 и 10 элементов соответственно, то данное ограничение имеет вид:

[шт/сутки]

2)                 Ограничения по суточному объему первой и второй технологических линий имеют вид:

[шт/сутки]

3)                 Неотрицательность объемов производства задается как

.

Таким образом, математическая модель этой задачи имеет вид

Построим прямые ограничений, для чего вычислим координаты точек пересечения этих прямых с осями координат (рис.3.1).

прямая (1) – точки (0;95) и (63,(3);0), прямая (2) проходит через точку параллельно оси , прямая (3) проходит через точку параллельно оси .

Рис. 3.1.2. Графическое решение задачи о производстве радиоприемников.

Определим ОДР. Например, подставим точку (0;0) в исходное ограничение (1), получим , что является истинным неравенством, поэтому стрелкой обозначим полуплоскость, содержащую точку (0;0), т.е. расположенную левее и ниже прямой (1). Аналогично определим допустимые полуплоскости для остальных ограничений и укажем их стрелками у соответствующих прямых ограничений (см. рис.3.1.2). Общей областью, разрешенной всеми ограничениями, т.е. ОДР, является многоугольник ABCDE.

Целевую прямую можно построить по уравнению

Точки пересечения с осями – (0;75) и (37,5;0)

Строим вектор из точки (0;0) в точку (40;20). Точка D – это последняя вершина многоугольника допустимых решений ABCDE, через которую проходит целевая прямая, двигаясь по направлению вектора . Поэтому D – это точка максимума ЦФ. Определим координаты точки D из системы уравнений прямых ограничений (1) и (2)

Получили точку D(60;5) [шт/сутки].

Максимальное значение ЦФ равно [$/сутки].

Таким образом, наилучшим режимом работы предприятия является ежесуточное производство радиоприемников первой модели в количестве 60 штук и радиоприемников второй модели в количестве 5 штук. Доход от продажи составит  2500$ в сутки.

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

3.2. Симплексный метод решения ЗЛП

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

Метод был разработан американским математиком Джорджем Данцигом (George Dantzig) в 1947 году.

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

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

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

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

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

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

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

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

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

Алгоритм перехода к следующей таблице такой:

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

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

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

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

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

•              строка разрешающего элемента делится на этот элемент и полученная строка записывается в новую таблицу на то же место.

•              в новой таблице все элементы ключевого столбца = 0, кроме разрезающего, он всегда равен 1.

•              столбец, у которого в разрешающей строке имеется 0, в новой таблице будет таким же.

•              строка, у которой в разрешающем столбце имеется 0, в новой таблице будет такой же.

•              в остальные клетки новой таблицы записывается результат преобразования элементов старой таблицы.

В результате получают новую симплекс-таблицу, отвечающую новому базисному решению.

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

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

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

Применение симплекс-метода для задачи линейного программирования предполагает предварительное приведение ее формальной постановки к канонической форме. Для этого вводят свободные переменные x3, x4 и x5 и с помощью них систему неравенств переводят в систему уравнений. Эти переменные представляют собой разность между левой и правой частями неравенств. 

Таким образом, получаем:

Свободные переменные x3, x4 и x5 должны быть неотрицательными.

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

Далее составим симплекс-таблицу 1.