Задачи оптимизации (стр. 2 из 3)

Вектор

в каждой точке перпендикулярной прямой , поэтому значение fбудет возрастать при перемещении прямой в направлении градиента (убывать в направлении антиградиента). Для этого параллельно прямой проводим прямые, смещаясь в направлении градиента (антиградиента).

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

Итак, нахождение решения задачи линейного программирования геометрическим методом включает следующие этапы:

1. Строят прямые, уравнения которых получаются в результате замены в ограничениях знаков неравенств на знаки точных равенств.

2. Находят полуплоскости, определяемые каждым из ограничений задачи.

3. Находят многоугольник решений.

4. Строят вектор

.

5. Строят прямую

.

6. Строят параллельные прямые

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

7. Определяют координаты точки максимума (минимума) функции и вычисляют значение целевой функции в этой точке.

Пример 1. Два больших войсковых соединения

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

1. Количество перевозимых частей в соединении

равно 6, а в –9.

2. Каждая станция может принять определенное количество частей:

.

3. На погрузку одной части станции затрачивают различное время (в сутках), которое указано в таблице.

Соединения	Станция погрузки
	3,0 4,5	4,0 6,5	2,5 3,5

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

Решение.

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

число частей i-го соединения (i=1,2) на j-ой станции (j=1, 2, 3).

Мы можем записать:

количество частей соединений на станциях погрузки

соответственно.

- количество частей соединения на местах погрузки.

- количество частей соединения на местах погрузки.

Общая сумма затрат времени (в сутках) на погрузку есть

В этой задаче 6 переменных, но мы можем свести к двум.

Пусть

Тогда

Целевая функция имеет вид

Итак, надо найти

при ограничениях:

которая решается графически

Возьмем прямую

и начнем строить параллельные ей в направлении антиградиента, где .

Последняя вершина многоугольника решений есть точка С, получаемая пересечением прямых (1) и (4). Решая, получим С (1;5).

Итак, оптимальные значения будут следующими:

, а общие затраты времени (суток).

§3 АНАЛИТИЧЕСКИЙ МЕТОД ОПТИМИЗАЦИИ

Пусть дана целевая функция

.

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

Пример 2. Определить оптимальный по времени маршрут выдвижения танкового подразделения из пункта А в пункт F, если допустимая скорость движения танков до дороги , по дороге , за дорогой . Удаление от дороге пункта А равно , пункта F . Расстояние между точками В и Е равно L = 90 км.

Составим математическую модель, то есть найдем функцию цели. Нас интересует время. Время выдвижения из пункта А в пункт F.

ВС = х км; DE = yкм; АС =

CD = L – x – y; DF =

Составим функцию цели, которая зависит от двух переменных

Найдем критические точки

При данных условиях

Найдем значение t при полученных xи y

При вычислении значения t на границе, значения получаются больше, чем 4,24 часа. Следовательно, оптимальное решение будет при

х = 6,9 км, у = 24 км,

.

ЗАКЛЮЧЕНИЕ

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