←предыдущая следующая→
1 2 3
1. Математическая модель экономических задач. Поста-новка ЗЛП.
Задача об использовании мощностей (задача о загрузке оборудования)
Предприятию задан план производства продукции по времени и номенклатуре: требуется за время Т выпустить n1, n2, nk единиц продукции P1,P2,Pk. Продукция производит-ся на станках S1,S2,Sn. Для каждого станка известна произ-водительность aij, т.е. число продукции Pj, которое можно произвести на станке Si, и затраты bij на изготовление продукции Тj на станке Si единицу времени. Необходимо составить такой план работы станков, т.е. распределить выпуск продукции между станками, чтобы затраты на производство всей продукции были min.
Экономико-математическая модель задачи:
Обозначим xij – время в течение которого станок Si будет занят изготовлением продукции Pj. Т.к. время работы каждого станка ограничено и не превышает Т, то справед-ливо неравенство:
x11+x12+…+x1k≤T
x21+x22+…+x2k≤T (1)
……………………
xm1+xm2+…+xmk≤T
Для реализации плана выпуска продукции по номенклатуре необходимо, чтобы выполнялись следующие равенства:
a11x11+ a21x21+…+ am1xm1=n1
a12x12+ a22x22+…+ am2xm2=n2 (2)
……………………………...
a1kx1k+ a2kx2k+…+ amkxmk=nk
Кроме того, xij≥0, (i=1,2,…,m; j=1,2,…,k) (3)
Затраты на производство всей продукции выразиться функцией:
F= b11x11+ b12x12+…+ bmkxmk (4)
Экономико-математическая модель задач об использовании мощностей.
Найти такое решение x=( x11,x12…,xmk) удовлетворяющим системам (1), (2) и условию (3), при котором функция (4) принимает min значение.
Постановка ЗЛП.
Общая ЗЛП имеет вид:
a11x1+ a12x2+…+ a1nxn≤b1
a21x1+ a22x2+…+ a2nxn≤b2
…………………………..
am1x1+ am2x2+…+ amnxn≤bm
x1≥0; x2≥0;… xn≥0
f= C1X1+C2X2+…+ CnXn→min(max)
Система неравенств называется системой ограничений, ее матрица имеет ранг r≤n, f – целевая функция. Неотрица-тельное решение (x10, x20,…, xn0) системы неравенств называется допустимым решением – планом ЗЛП. Допус-тимое решение называется оптимальным, если оно обраща-ет целевую функцию в min или max (оптимум).
2.Геометрический метод решения ЗЛП.
Множество допустимых решений (многогранник решений) ЗЛП представляет собой выпуклый многогранник (или выпуклую многогранную область). Выпуклая область – это такая область, у которой любая точка отрезка, концы которого лежат на границе области принадлежат этой области. Оптимальное решение задачи находится, по крайней мере, в одной из угловых точек многогранника решений. Рассмотрим задачу стандартной формы с двумя переменными (n=2). В такой форме можно привести к классическую задачу (с ограничениями, в виде уравнений, когда число переменных n больше числа уравнений m на 2, т.е. n-m=2). Пусть геометрическим изображением системы ограничений является многоугольник ABCDE (рис.1). Необходимо среди точек этого многоугольника найти такую точку, в которой линейная функция f= C1X1+C2X2 принимает max или min значение.
Рассмотрим линию уровня линейной функции f, т.е. линию вдоль которой это функция принимает одно и то же фикси-рованное значение, т.е. f=a, или C1X1+C2X2=a (1)
На многоугольнике решений следует найти точку через которую проходит линия уровня функции f с наиб. или наим. уровнем. Уравнение линии уровня функции (1) есть уравнение прямой линии. При различных уравнениях a, линия уровня параллельна, т.к. их угловые коэффициенты определяются только соотношением между коэффициента-ми C1 и C2 и следовательно равны. Т.о. линия уровня функции f – это своеобразные параллели, расположенные под каким-то углом к осям координат. Важное свойство линии уровня состоит в том, что при параллельном смеще-нии в сторону градиента, уровень только возрастает, а при смещении в другую сторону только убывает. Это и есть свойство градиента. Одну линий уровня можно взять, проходящей через начало координат (если линейная функ-ция имеет вид f= C1X1+C2X2, т.е. без свободного члена.), то это соответствует нулевому уровню.
Этапы решения задач.
1. Сначала на координатной плоскости X1O X2 строится допустимая многоугольная область, соответствующая ограничениям. Далее строится вектор градиент, координаты которого являются частными производными функции f. Вектор показывает направление возрастания линейной функции f, в какой-нибудь точке X0, принадлежащей допустимой области.
2. Прямая f= C1X1+C2X2 перпендикулярно вектору-градиенту передвигается в направлении этого вектора, в случае максимизации f, до тех пор, пока не покинет много-угольной области. Предельная точка (или точки) области при этом движении и являются точкой max f.
3. Для нахождения координат точки max достаточно из соответствующих ограничений, и дающих пересечения точки max. Значение f, найденное в получаемой точке являются max. В случае минимизации f, прямую f= C1X1+C2X2, надо двигать в направлении, противоположно-му вектору-градиенту. Ясно, что, если прямая f= C1X1+C2X2 не покидает допустимой области, то соответствующий max или min f не существует.
4. Вопрос 4. Взаимодвойственные задачи ЛП. Основные теории двойственности. С каждой задачей ЛП связана некоторая другая задача ЛП, называемая двойственной по отношению к данной (исходной). Различают симметричную и несимметричную формы взаимодвойственных задач. Рассмотрим симметричную форму: Пусть дана зад ЛП станд. Формы:
a11x1+a12x2+...+a1n xn>=b1
a21x1+a22x2+...+a2nxn>=b2
...-....-....-....-...-....-....-....-
am1x1+am2x2+...+amnxn>=bm
x1>=0; x2>=0;...., 1n>=0
f = c1x1+c2x2+...+cnxn
Составим др. зад., связанную с данной кот. Назовем двойственной:
A11y1+a12y2+...+am1ym Сij. б)составим цикл пересчета для этой клетки расставим знаки + и – в вершинах цикла путем их чередования, приписывая пустой клетке +. в)находим число пересчетов по циклу. Число х=хmin{хij}, где хij – числа, заполненных клетках со знаком -. г)составим новую таблицу, прибавляя х в положительные клетки и отнимая х из отрицательных клеток.
6.см п.3 а-д. Через оптимальное число шагов обязательно приходим к ответу, ибо ТЗ всегда имеет решение.
7. Постановка задачи целочисленного программирова-ния (ЗЦЛП). Метод Гомори.
Мат. модель ЗЦЛП имеет вид:
(1)
(2)
(3)
, где Z – множество целых чисел (4)
Разложенные задачи полностью целочисленные, в которых условие целочисленности распространяются на все пере-менные и частично целочисленны, в целочисленности налагается только на часть переменных.
Если в (2) среди и есть дробные числа, то каждое уравнение или неравенство с дробными коэффициентами может привести к общему знаменателю и затем обе части умножить на этот общий знаменатель, поэтому не нарушив общности рассуждений, можно предполагать, что коэффи-циенты целочислены.
Решение целочисленных и непрерывных задач оптимизации имеет принципиальные различия, суть которого заключает-ся в следующем: непрерывные задачи обычно решаются симплекс-методом с построением симплекс-таблиц.
Известно, что для ЗЛП экстремум достигается в крайней точке выпуклого множества или в точке, в которой является выпуклой линейной комбинацией крайних точек. Для ЗЦЛП точкой оптимума может быть любая точка области допустимых решений, поэтому невозможно заменить дискретную задачу непрерывным аналогом, и найдя соот-ветствующее решение и округлить его значение до бли-жайших целых значений.
Пусть целая часть числа x – [x], огромная – {x}, тогда Если даже оптимальный непре-рывной задачи, округлённой до целых значений компонент окажется допустимым, то целевая функция может вести себя так, что её значение будет на нём значительно хуже, чем на оптимальном плане целочисленной задачи.
Перечисленные проблемы предопределяли необходимость разработки специальных методов решения ЗЦЛП, ибо методы последовательного улучшения приводит к целочис-ленному решению лишь для немногих задач. Методы ЦЛП можно разделить на 3 основные группы:
1. Метод отсечения.
2. Комбинаторные.
3. Приближённые
Сущность 1 состоит в том, что сначала задача решается без условия целочисленности. Если полученный план будет целочисленным, то задача решена. Решение обладает следующими свойствами:
1) Оно должно быть линейным.
2) Должно отсекать найденный оптимальный нецелочисленный план.
3) Не должно отсекать ни одного целочисленно-го плана.
Дополнительные ограничения, обладающие указанными свойствами, называются правильным отсечением. Затем полученные оптимизационные задачи решаются с учётом нового ограничения. После этого в случае необходимости добавляется новое ограничение.
Геометрическое добавление каждого линейного ограниче-ния отвечает проведению плоскости (гиперплоскости), которая отсекает от многоугольника (многогранника) некоторую его часть вместе с оптимальной точкой с неце-левыми координатами, но не затрагивая ни одной из цело-численных точек этого многоугольника.
Метод Гомори.
Основная идея метода отсекающих плоскостей состоит в том, что на каждом шаге рассматривается задача с ослаб-ленными ограничениями без требования целочисленности, для которой по
←предыдущая следующая→
1 2 3