Раздел 9. Введение в математические методы оптимизации.

Оптимизация производства.

 

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

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

 

Пример 2. Необходимо приготовить раствор, содержащий вещество А и В. Даны два стандартных готовых раствора с концентрациями веществ в этих растворах . Стоимость единицы раствора С1 и С2 соответственно. Надо, чтобы в растворе было вещества А не менее α, а В не менее β при условии минимальной стоимости.

Формализуем последний пример в следующем виде:

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

 

Пример 3. Фирма производит два продукта А и В. Рынок сбыта неограничен. Для выпуска продукции А и В необходимо использовать два станка. Время операции (в часах) на каждом станке для выпуска изделий А и В приведено в таблице.

	Станок 1	Станок 2
А	0,5	0,4
В	0,25	0,3

 

Время работы станков в неделю не может превышать 40 и 36 часов соответственно. Прибыль от продажи единицы продукции составляет 5 и 3 рубля соответственно. Необходимо определить, сколько каждого продукта необходимо выпускать, чтобы общая прибыль была максимальна. Формализуем данную задачу.

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

Первая прямая L1 получена из ограничения неравенства , прямая L2 – из .

Тогда область ниже этих прямых будет соответствовать ограничениям-неравенствам

 

 

Перемещаем опорную линию Z параллельно самой себе в направлении, перпендикулярном опорной линии по допустимой области. Перемещение соответствует росту прибыли от нуля (начальное положение опорной линии с нулевой прибылью) до максимально возможной, что соответствует положению линии прибыли на границе допустимой области (линия Z1). Найдем координаты точки на плоскости, соответствующей максимальной прибыли. Координаты и будут равны оптимальному выпуску продукции.

 

 

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

 

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

Если переменных больше двух, то графическое решение затруднительно и целесообразно искать его только на ЭВМ.

 

Транспортная задача.

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

Исходя из возможностей поставщиков:

Исходя из потребностей потребителей:

Это и есть формализованная транспортная задача. Ее оформление и решение обычно идет в серии таблиц, называемых транспортными.

Рассмотрим ход решения на конкретном примере. Пусть поставщиков три, потребителей четыре. Задача сбалансированная. Исходные данные приведены в таблице. В ячейках таблицы приведены стоимости перевозок с соответствующего склада к конкретному поставщику. Обозначим поставщиков через А1, А2, А3. Потребителей – В1, В2, В3, В4.

	В1	В2	В3	В4	Запасы
А1
А2
А3
Заявки

Проверяем задачу на сбалансированность: 150+120+80+50=400, 100+130+170=400. Задача сбалансированная.

Решение идет в несколько этапов.

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

 

	В1	В2	В3	В4	Запасы
А1
А2	130 1
А3
Заявки

 

Далее из рассмотрения исключаем строку, если запас у этого поставщика израсходован, или столбец, если запрос удовлетворен. В нашем случае поставщик А2 перевезет весь свой запас в пункт В1 по стоимости за 1 руб. Однако, заявка В1 полностью не выполнена. Далее в последней таблице вновь ищем минимальную стоимость. Это С₁₁=3 руб. Отправляем из А1 в В1 недостающие 20 единиц товара. Потребности В1 будут полностью удовлетворены. Промежуточная таблица примет вид:

 

	В1	В2	В3	В4	Запасы
А1	20 3
А2	130 1
А3	0 5
Заявки

 

Вновь ищем минимальный элемент. Это С₁₂, поэтому всю перевозку направим из А1 в В2. Это будет 80 единиц. Вписываем это в таблицу.

 

	В1	В2	В3	В4	Запасы
А1	20 3	805
А2	130 1
А3	0 5
Заявки

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

 

	В1	В2	В3	В4	Запасы
А1	20 3	805	0 7	011
А2	130 1	04	06	03
А3	0 5	408	8012	507
Заявки

 

2. Второй этап: расчет полной стоимости перевозок и проверка плана на оптимальность (минимум стоимости).

Полная стоимость перевозок:

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

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

Тогда для тех клеток, в которых перевозки присутствуют, можно записать:

.

Составим систему уравнений для ненулевых клеток:

 

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

 

Вычисляем псевдостоимости и сравниваем их с реальными.

 

Так как есть псевдостоимости большие, чем стоимости, то предложенный опорный план не оптимален. Наибольшая разность, равная 2, в клетке (1,3). Следовательно, в план надо ввести перевозку из А1 в В3. В таблице опорного плана начинаем переставлять перевозки, начиная с этой клетки, не нарушая баланс задачи. Необходимо помнить, что перестановки перевозок должны идти только по замкнутому циклу, чтобы баланс задачи не нарушился.

 

Было:

	В1	В2	В3	В4	Запасы
А1	20 3	805	0 7	011
А2	130 1	04	06	03
А3	0 5	408	8012	507
Заявки

 

Стало:

	В1	В2	В3	В4	Запасы
А1	20 3	05	80 7	011
А2	130 1	04	06	03
А3	0 5	1208	012	507
Заявки

 

Рассчитываем стоимость перевозок.

 

 

Стоимость стала меньше. Вновь проверяем план на оптимальность.

 

Отсюда,

Число уравнений 5, число переменных равно 5. Можно произвольно назначить значения двум переменным. Пусть . Решаем систему уравнений обычным образом. В результате получим:

 

Вычисляем вновь псевдостоимости свободных клеток.

 

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

 

Было:

	В1	В2	В3	В4	Запасы
А1	20 3	05	80 7	011
А2	130 1	04	06	03
А3	0 5	1208	012	507
Заявки

 

Стало:

	В1	В2	В3	В4	Запасы
А1	0 3	205	80 7	011
А2	130 1	04	06	03
А3	20 5	1008	012	507
Заявки

 

Определяем стоимость перевозок:

 

 

Проверяем на оптимальность. Определяем псевдостоимости и сравниваем их с реальными стоимостями:

 

Отсюда,

 

Решение системы методом исключения и назначения произвольно значений свободным переменным дает:

 

Находим псевдостоимости:

 

Найденный план оптимален, так как все псевдостоимости меньше или равны реальным стоимостям. Минимальная стоимость перевозок равна 2040 руб.