|
Задачами
линейного программирования (ЛП) называются задачи, в которых линейны как
целевая функция, так и ограничения в виде равенств и неравенств, и для которых
методы математического анализа оказывается непригодными.
Задача
ЛП в стандартной форме имеет следующий вид:
W
= с1*х1 + с2*х2 + … + сn*хn
→ min
(max)
где
х1, х2 и хп - переменные величины;
с1,
с2 и сп - коэффициенты.
Условия
функционирования объекта (ограничения) в задачах линейного программирования
должны относиться к одному из следующих типов:
d1*х1
+ d2*х2
+ … + dn*хn
= d0
е1*х1
+ е2*х2 + … + еn*хn
≥ еo
f1*
х1 + f2*
х2 + … + fn*
хn
≤ f0
где
dп,
еп, - коэффициенты;
do,
еo,
fo
- постоянные величины.
В
предлагаемых методических указаниях решение задач начинается с составления
математической модели процесса, описанного в задаче, и анализа модели с целью
выбора наиболее эффективного способа оптимизации. Для решения оптимальных задач
использован пакет программ статического программирования "Statgraphic".
Процесс
динамического программирования проводится от конца к началу. Первым планируется
последний этап. При этом предполагаются различные варианты завершения
предыдущего этапа, и для всех этих вариантов находят такое решение, при котором
эффект на последнем этапе будет наибольшим. Такое решение будет условно
оптимальным. Аналогично находятся услoвно
оптимальное решение на последующих этапах.
Таким
образом, задача поиска условного максимума функции многих переменных сводится к
нескольким задачам поиска максимума функции двух переменных. Далее процесс
происходит в обратном порядке (от начала к концу). В результате чего, находятся
оптимальные уравнения на каждом шаге и, таким образом, оптимизируется весь
процесс.
ОПТИМИЗАЦИЯ
ДОРОЖНОЙ СЕТИ
Исходные данные
Необходимо
найти кратчайшее расстояние между двумя пунктами А и K,
для перевозки грузов с минимальными затратами. Между этими пунктами находится
10 пунктов: 3 внутри, 5 внизу, 2 наверху.
|
