LPZad
.docТиповые оптимизационные задачи
линейного программирования
1. Задача о диете (пищевом рационе). Имеется N видов продуктов питания pi . Известна стоимость единицы каждого продукта ci. Из этих продуктов необходимо составить пищевой рацион, который должен содержать белков не менее B единиц, углеводов не менее U единиц, жиров не менее G единиц. Для каждой единицы i-го продукта известно содержание единиц белков-bi , углеводов- ui и жиров- gi. Требуется так составить пищевой рацион, чтобы обеспечить заданные условия при минимальной стоимости рациона.
Модель. Пусть xi – количества продуктов i-го вида. Тогда
. Задача ЛП с размерностью 3хN.
2. Задача о ранце. Имеется N видов предметов, которые турист хочет взять с собою в поход. Известны вес bi каждого предмета и его эффективность ei для туристов. Составить список предметов, помещаемых в рюкзак, учитывая, что предельный вес рюкзака не более заданной величины B. Необходимо, чтобы суммарный эффект был максимальным.
Эту задачу можно рассмотреть в двух вариантах:
-
решение в виде брать предмет или не брать;
-
сколько взять предметов каждого вида.
Пусть 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- нет.
Это задача булевского программирования с размерностью (p+q) x pq.
Сводится к задаче ЦЛП с размерностью (p+q+pq) x pq. Для этого вводим дополнительные ограничения:
от переходим к
В таком виде задача решается следующими методами:
-
методы ЛП (например симплекс-метод) в силу специфики модели;
-
методы ЦЛП (неэффективны) – метод Гомори, ветвей и границ для ЦЛП;
-
как частный случай транспортной задачи (объемы поставок и потребления равны 1);
-
венгерский метод.
В случае, если количество работ и исполнителей не равны, то вводятся фиктивные исполнители или работы.
5. Задача о коммивояжере.
Есть n городов. Затраты (стоимостные, временные, расстояния) на переезд между i-м и j-м городом заданы в виде матрицы Cij , ,. Коммивояжер, выехав из исходного города должен объехать все города, посетив каждый однажды, и вернуться в исходный. Определить в каком порядке нужно объезжать города, чтобы суммарные затраты были минимальными.
Модель.
Пусть
Задача ЦЛП. Размерность (2n+n2) x n2
Результат решения задачи может быть представлен в виде матрицы вида: или в виде маршрута: 1-2-3-5-4-1.
Эта модель не учитывает условие, не допускающее появление неполных замкнутых циклов (см. рис.)
Методы решения:
-
метод ветвей и границ для з-чи о коммивояжере – в этом методе уже заложено условие связанности циклов.
-
венгерский метод с модификацией, отвергающей решения с неполными замкнутыми циклами
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)
Подготовил
Сергей Чекрыжов