Понятие выпуклого прогр-я, геом. прогр-я, сепарабильного прогр-я

↑

▷ Содержание

⇐ ПредыдущаяСтр 6 из 7Следующая ⇒

для решения задач инженерного характера, когда ц.ф. и ограничени япредставлены в в иде положит. полиномов:

(x) = (

min (x)

(x)<=1, k=

aj – веществен. число

cj>0 положит. Число

Метод сепарабильного прогр-я

ф-ция f() явл. пепарабильной, если ее можно представить в виде:

Решение ЗЛП. Симплек метод реш ЗЛП

Ограничения ЗЛП образуют некоторую общую часть N- мерного пространства, кот наз-ся многогранником решений. Если линейн ф-ция f(x) достиг своей мин значения, то она достигается в угловой точки многогранника решений.

Любое решение , - наз-ся допуст решением. Допустимое решение r m, наз-ся базисным решением. Баз. решение кот достигает min целев. ф-ии f(x) наз-ся оптимальн решением, кот требуется найти. для решения прим-ся граф. и симплексный метод. n=2, m=3 n-m=1

Симплек метод реш ЗЛП

Универсальным методом реш ЗЛП явл=ся симплекс метод, кот непосредственно примен-ся. Баз решение опред. координаты вершин многогранника реш=ий и из них необход найти ту вершину, кот доставляет min целев ф-ии f(x).

При больших числах ограничения n и числа неизвестных m найти оптимальное решение трудно. Max яисло переборов будет , поэтому необходимо иметь схему, позволяющую исходя из известного баз реш-я найти оптимальное решение. Такой схемой яв-ся симплек метод.

2 этапа:

1. нахождение первоначальн баз реш

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

Переменные:

-базисные r

- небазисные, применяются равными 0.

Каждый шаг приближает к min

Обычно ЗЛП решается в ручную с помощью симплекс таб.

Иногда вместо исходной ЗЛП выгоднее решать другую задачу, называемую двойственной, когда число ограничений гораздо больше число значений.

Познавательные статьи:



Где возникла философия и почему?

Относительная высота сжатой зоны бетона

Сущность проекции Гаусса-Крюгера и использование ее в геодезии

Тарифы на перевозку пассажиров