Типовые оптимизационные задачи

Материал подготовлен

ст. преп. кафедры

вычислительной техники Юн С. Г.

Типовые оптимизационные задачи

1.  Задача о диете (пищевом рационе)

Постановка задачи:

Имеется N видов продуктов питания pi . Известна стоимость единицы каждого продукта ci. Из этих продуктов необходимо составить пищевой рацион, который должен содержать белков не менее B единиц, углеводов не менее U единиц, жиров не менее G единиц. Для каждой единицы i-го продукта известно содержание единиц белков-bi , углеводов - ui и жиров - gi. Требуется так составить пищевой рацион, чтобы обеспечить заданные условия при минимальной стоимости рациона.

Модель:

Пусть xi – количества продуктов i-го вида. Тогда

.

Это задача ЛП с размерностью 3хN.

2.  Задача о ранце

Постановка задачи:

Имеется N видов предметов, которые турист хочет взять с собою в поход. Известны вес bi каждого предмета и его эффективность ei для туристов. Составить список предметов, помещаемых в рюкзак, учитывая, что предельный вес рюкзака не более заданной величины B. Необходимо, чтобы суммарный эффект был максимальным.

Эту задачу можно рассмотреть в двух вариантах:

1.  решение в виде брать предмет или не брать;

2.  сколько взять предметов каждого вида.

Пусть xi – количество предметов каждого вида.

Модель:

а) для первого варианта:

, xi={0,1}.

Это булевская задача с размерностью 1хN.

Можно свести к задаче ЦЛП: , xi- целые. Тогда размерность задачи (N+1)хN.

б) для второго варианта:

,, целое.

Это задача ЦЛП с размерностью 1хN.

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

Постановка задачи:

Транспортная задача (ТЗ) – особый класс задач ЛП. Специфика математической модели ТЗ позволяет наряду с общими методами решения задач ЛП применять специальные методы, позволяющие сократить вычисления. Постановка ТЗ принадлежит Хичкоку.

Имеется m – пунктов производства (складов) некоторого одного продукта, ai - объем производства в i-м пункте производства, .

n пунктов потребления, bj - объем потребления (поданные заявки на поставку продукта) в j-м пункте потребления, .

Пункты производства связаны с пунктами потребления сетью дорог с определенными тарифами на перевозки. Стоимость перевозки одной единицы товара с производства i в пункт j равна Cij. Необходимо найти оптимальный план перевозок продукции, при котором транспортные издержки минимальны, продукция полностью вывозится из пунктов производства и полностью удовлетворяет потребность.

Модель:

xij – количество продукта, вывозимого из i-го пункта производства в j-й пункт потребления.

,

Размерность задачи (m+n) x mn

Методы решения:

1. симплекс метод

2. специальные методы: для нахождения опорного плана: метод северо-западного угла, метод минимального элемента; для нахождения оптимального плана - метод потенциалов.

3. обобщенный венгерский метод и др.

ТЗ может рассматриваться в 2-х вариантах: открытая ТЗ и закрытая ТЗ.

ТЗ закрытая, если выполняется условие баланса производство равно потреблению:

Открытая ТЗ может быть в 2-х вариантах:

1)

Вводим фиктивный пункт потребления n+1, объем потребления которого равен:

2)

Вводим фиктивный пункт производства m+1, объем производства которого равен:

4.  Задача о назначении

Постановка задачи:

Имеется p исполнителей и p работ. Известна эффективность применения каждого исполнителя на каждой работе Cij. Необходимо расставить исполнителей по работам, чтобы суммарный эффект от работы был максимальным. Каждый работник может выполнять только одну работу, и каждая работа может выполняться только одним исполнителем.

Модель:

xij – факт применения i-го работника на j-й работе.

. 1- назначается на работу, 0- нет.

Это задача булевского программирования с размерностью 2p x p2.

Сводится к задаче ЦЛП с размерностью (2p+p2) x p2. Для этого вводим дополнительные ограничения:

от переходим к

В таком виде задача решается следующими методами:

1.  методы ЛП (например симплекс-метод) в силу специфики модели;

2.  методы ЦЛП (неэффективны) – метод Гомори, ветвей и границ для ЦЛП;

3.  как частный случай транспортной задачи (объемы поставок и потребления равны 1);

4.  венгерский метод.

В случае, если количество работ и исполнителей не равны, то вводятся фиктивные исполнители или работы.

5.  Задача о коммивояжере

Постановка задачи:

Есть n городов. Затраты (стоимостные, временные, расстояния) на переезд между i-м и j-м городом заданы в виде матрицы Cij , ,. Коммивояжер, выехав из исходного города должен объехать все города, посетив каждый однажды, и вернуться в исходный. Определить в каком порядке нужно объезжать города, чтобы суммарные затраты были минимальными.

Модель:

Пусть

Задача ЦЛП. Размерность (2n+n2) x n2

Результат решения задачи может быть представлен в виде матрицы вида: или в виде маршрута: 1-2-3-5-4-1.

Эта модель не учитывает условие, не допускающее появление неполных замкнутых циклов (см. рис.)

Методы решения:

1.  метод ветвей и границ для з-чи о коммивояжере – в этом методе уже заложено условие связанности циклов.

2.  венгерский метод с модификацией, отвергающей решения с неполными замкнутыми циклами

6. Задача о раскрое материалов.

На раскрой поступает s различных материалов, требуется изготовить n различных видов изделий, причем продукция выпускается комплектами и в комплект входит bk изделий k-го вида. Каждая единица j-го материала может быть раскроена p различными способами так, что при использовании i-го способа получается aijk единиц изделий k-го вида. Известно, что материала j-го вида имеется cj единиц. Найти план раскроя, обеспечивающий максимальное число комплектов при заданных ограничениях на материал.

Модель. Пусть xij – число заготовок j-го материала, раскроенных i-м способом.

, , целые

Задача НЛП. Размерность задачи: s x p*s

Эту задачу можно привести к линейному виду. Введем еще одну переменную y – количество комплектов. Тогда получим модель:

, , целые

Задача ЦЛП. Размерность задачи (s+n) x (p*s+1)