Книги по разным темам Pages:     | 1 | 2 | 3 | 4 |

Шаг 3: Найдем предельное значение переменной, за счет которой можно улучшить значение целевой функции. Увеличение значения этой переменной допустимо до тех пор, пока одна из m переменных, вошедших в пробное решение, не обратится в 0. Исключим из выражения для целевой функции только что упомянутую переменную и введем в пробное решение ту переменную, за счет которой результат может быть улучшен.

Шаг 4: Решим систему m уравнений относительно переменных, вошедших в новое пробное решение. Исключим эти переменные из выражения для целевой функции. Вернемся к шагу 2.

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

Рассмотрим следующую задачу.

Фирма Мультиконвейер имеет возможность реализовать от одного до четырех различных типов технологических процессов. Технологические процессы первого и второго типов ориентированы на получение продукции А, а технологические процессы третьего и четвертого типов - на получение продукции B. Расходы, связанные с каждым из технологических процессов, приведены в табл.1.1.

Таблица 1. На единицу продукции А На единицу продукции В Имеется технологич. технологич. технологич. техноло- в наличии процесс 1 процесс 2 процесс 3 гич.процес (всего) с Трудозат- раты, 1 1 1 1 человеко- - недель Количест- во мате- 7 5 3 2 риала Y, кг Количест- во мате- 3 5 10 15 риала Z, кг Доход с единицы 4 5 9 продукции, усл.ед.

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

Пусть x1, x2, x3, x4 - объем продукции, производимой с помощью соответственно 1, 2, 3, 4 технологических процессов.

Целевая функция 4x1 + 5x2 + 9x3 + 11x4 max Ограничения:

x1 + x2 + x3 + x4 7x1 + 5x2 + 3x3 + 2x4 3x1 + 5x2 + 10x3 + 15x4 х1 0, х2 0, х3 0, х4 Обозначим через Xо значение целевой функции и введем в рассмотрение свободные переменные X 5, X6, X 7.

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

Xо - 4X1 - 5X2 - 9X 3 - 11X 4 = 0 строка X1 + X2 + X 3 + X 4 + X 5 = 15 7X1 + 5X2 + 3X 3 + 2X 4 + X 6 = 120 (1) 3X1 + 5X2 +10X 3 +15X 4 + X 7 = 100 Итерация Задача шага 1 заключается в том, чтобы выбрать первоначальное допустимое решение системы уравнений (1). Существует множество таких решений, однако удобнее всего начать с X0 = 0, X5 =15, X6 = 120, X7 = 100 при нулевых значениях остальных переменных. То есть строится первое пробное решение с помощью только свободных переменных. Это решение называют исходным базисным решением (или исходным опорным планом), а переменные Х0, Х5, Х6, Х7 - базисные переменные (базис), остальные переменные - небазисные. Значение базисных переменных записывается в симплекс-таблицу (табл.

1.2).

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

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

Таким образом:

каждый коэффициент в строке 0 определяет положительное (если перед ним стоит л-) или отрицательное (если л+) приращение Х0 при увеличении на единицу соответствующей небазисной переменной.

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

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

В соответствии с критерием 1 в базис следует ввести переменную Х4.

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

Например: в строке 1 Х5 должно быть меньше на 1, чтобы удовлетворялось ограничение:

в строке 2 X6 должно быть меньше на 2, в строке 3 X7 должно быть меньше на 15.

Сколь велико должно быть значение Х4, чтобы значение одной из выбранных вначале базисных переменных достигло своей нижней границы, т.е.

нуля Легко проверить, что такой предел для Х4 равняется, при этом Х= 0. Следовательно, в базис нужно включить Х4, исключив из него Х7.

Отсюда сформулируем следующее правило:

Симплекс-критерий 2 (выбор разрешающей строки):

а) рассмотрим отношения чисел, стоящих в правых частях (1), к соответствующим коэффициентам при новой базисной переменной Хj;

б) выберем отношение с наименьшим значением - в очередном пробном решении Xj приравнивается именно к этому значению.

Пусть наименьшее из всех отношений правых частей (1) к соответствующим коэффициентам при Xj, соответствует переменной Xk, входившей в предыдущее решение; тогда в очередном пробном решении следует положить Xk = 0.

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

1X0 - 4X1 - 5X2 - 9X3 - 11X4 = 0 (0) X1 + X2 + X3 + X4 + X5 = 15 (1) 7X1 + 5X2 + 3X3 + 2X4 + X6 = 120 (2) 1 1 2 1 X1 + X2 + X3 + X4 + X7 = (3) 5 3 3 15 строка 3 11 + строка строка 3 (-1) + строка строка 3 (-2) + строка 2; получим:

9 4 5 11 X0 - X1 - X2 - X3 + X7 = (0) 5 3 3 15 4 2 1 1 X1 + X2 + X3 + X5 - X7 = (1) 5 3 3 15 33 13 5 2 X1 + X2 + X3 + X6 - X7 = (2) 5 3 3 15 1 1 2 1 X1 + X2 + X3 + X4 + X7 = (3) 5 3 3 15 Итерация Завершив первую итерацию, следует вернуться к шагу 2, с тем, чтобы определить, является ли полученное решение оптимальным.

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

строка1 + строка строка1(- )+ строка строка1( - )+строка Результаты вычислений представлены в таблице 1.2.

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

Итерация Решение может быть улучшено за счет Х3.

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

Исключим X3 из строк 1, 1, 2.

Строка 3 + строка 0.

Строка 3 (- ) + строка 1.

Строка 3 + строка 2.

Итерация В строке 0 системы уравнений все коэффициенты положительны, и, следовательно, полученное решение является оптимальным X0 = 695/7, Х1 = 50/7, Х6 = 325/7, Х3 = 55/7.

Табличное представление (Симплекс - таблица) Таблица 1.Ите Б Проб- Стро- ра- а ные ки ция з значе- Х1 Х2 Х3 Х4 Х5 Х6 Х и ния с X0 0 - 4 - 5 - 9 -11 X5 15 1 1 1 1 1 X6 120 7 5 3 2 1 X7 100 3 5 10 15 1 Х0 220 -9/5 -4/3 -5/3 11/5 X5 25 4/5 2/3 1/3 1 -1/15 X6 320/3 33/5 13/3 5/3 1 -2/15 X4 20/3 1/5 1/3 2/3 1 1/15 X0 1105/1 1/6 - 9/4 7/12 X1 2 1 5/6 11/12 5/4 -1/12 X6 125/12 -7/6 5/12 -33/4 1 5/12 X4 455/12 1/6 - 1 1/12 55/12 13/ 7/ X0 695/7 3/7 11/7 13/7 5/7 X1 50/7 1 5/7 -5/7 10/7 -1/7 X6 325/7 -6/7 13/7 -61/7 1 4/7 X3 55/7 2/7 1 12/7 -3/7 1/7 Геометрически решение симплекс-методом заключается в последовательном восхождении вдоль ребер многогранника, соответствующего области допустимых решений, от одной его вершины к соседней.

После преобразования строки 0 в целевую функцию имеем 695 3 11 13 Х0 = - Х2 - Х4 - Х5 - Х7 7 7 7 При любом отличном от нуля значении хотя бы одной из небазисных переменных Х2, Х4, Х5, Х7 - целевая функция принимает значение меньше 695/7.

З А Д А Ч И 1. Завод по производству электронного оборудования выпускает персональные компьютеры и системы подготовки текстов. В настоящее время освоены четыре модели:

а) Юпитер - объем памяти 512 Кбайт, одинарный дисковод;

б) Венера - объем памяти 512 Кбайт, двойной дисковод;

в) Марс - объем памяти 640 Кбайт, двойной дисковод;

г) Сатурн - объем памяти 640 Кбайт, жесткий диск.

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

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

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

Мощность, Юпитер Венера Марс Сатурн ч / мес.

Узловой сборки 5 8 20 25 Сборочный 2 3 8 14 0,1 0,2 2 4 Испытательный Максимальное прогнозное значение спроса 100 45 25 за месяц Доход, усл.ед. 15 30 120 2. Менеджер по ценным бумагам намерен разместить 100000 усл.ед. капитала таким образом, чтобы получать максимальные годовые проценты с дохода. Его выбор ограничен четырьмя возможными объектами инвестиций: А, В, С, и D. Объект А позволяет получать 6% годовых, объект В - 8% годовых, объект С - 10%, а объект D - 9% годовых. Для всех четырех объектов степень риска и условия размещения капитала различны. Чтобы не подвергать риску имеющийся капитал, менеджер принял решение, что не менее половины инвестиций необходимо вложить в объекты А и В. Чтобы обеспечить ликвидность, не менее 25% общей суммы капитала нужно поместить в объект D. Учитывая возможные изме-нения в политике правительства, предусматривается, что в объект С следует вкладывать не более 20% инвестиций, тогда как особенности налоговой политики требуют, чтобы в объект А было вложено не менее 30% капитала.

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

3. Предприятие может выпускать четыре вида продукции - П-1, П-2, П-3, П-4 без ограничения на количественный выпуск этой продукции. Для изготовления этой продукции предприятие располагает в течение месяца следующими ресурсами: трудовыми ресурсами в количестве 16 чел.-нед.; полуфабрикатами массой 110 кг; станочным оборудованием в объеме 100 станко-смен. Для изготовления 1 шт. продукции П-1, П-2, П-3, П-4 требуется 1 чел.-нед. для каждого вида продукции, соответственно полуфабрикатов 6; 5; 4; 3 кг и станочного оборудования 4; 6; 10; 13 станко-смен. Цена 1 шт. каждого вида продукции равна соответственно 60; 70; 120 и 130 руб. Требуется составить такой план выпуска, чтобы получаемый доход был максимальным. Условия приведенной задачи сведены в таблице.

Таблица 1. Продукция Ресурс _ Объем ресурса П-1 П-2 П-3 П-Трудовые ресурсы, чел.-нед. 1 1 1 1 Полуфабрикаты, кг 6 5 4 3 Станочное оборудование, станко-смены 4 6 10 13 Цена 1 шт.. 60 70 120 План выпуска Х1 Х2 Х3 Х2. Динамическое программирование - метод решения многошаговых оптимизационных задач 2.1 Постановка задачи динамического программирования В управлении экономическими системами часто приходится иметь дело с динамическими процессами, т.е. объект управления находится в состоянии непрерывного движения под воздействием различных внешних и внутренних факторов. Решение подобных задач в общем виде определяется системой дифференциальных уравнений, что довольно сложно.

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

Критерий качества управления (целевая функция) многошагового процесса представляет собой полные потери за все n шагов процесса n - J n (U) = Q(Xk,Uk ), k = где Xk - состояние объекта управления на k-м шаге, Uk - управляющее воздействие на k- шаге, Q - функция потерь, n - количество шагов.

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

1) управляемые переменные и соответствующие ограничения группируются по шагам, и многошаговый процесс принятия решений исследуется в определенной последовательности;

2) любую многошаговую задачу можно решать двумя способами:

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

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

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

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

Поэтому процесс динамического программирования разворачивается с конца к началу: прежде всего планируется последний n - шаг.

Планируя последний шаг, нужно сделать разные предположения о том, чем закончился предпоследний (n-1) - шаг, и для каждого из этих предположений найти условное оптимальное управление на n-шаге. Затем можно оптими- зировать управление на предпоследнем шаге (n-1). Сделаем предположения о том, чем закончился предыдущий (n-2) шаг, и для каждого из этих предположений найдем такое управление на (n-1) шаге, при котором выигрыш за последние два шага максимален! Так мы найдем для каждого исхода (n-2) шага условное оптимальное управление на (n-1) шаге и условный оптимальный выигрыш за последние два шага и т.д., пока не дойдем до первого шага.

Теперь можно построить оптимальное управление u и найти оптимальный выигрыш Qn.

Pages:     | 1 | 2 | 3 | 4 |    Книги по разным темам