При проектировании систем необходимо выполнить комплекс из 8-ми работ

а₁,а₂,...,а_8. Для каждой работы определено время выполнения и определены работы, которые должны предшествовать ей (т.е. работы, на которые она опирается).

работы	опир-ся на работу	вр выполнения работы (дн)
а1 а2 а3 а4 а5 а6 а7 а8	- - - а1 , а2 а1 , а2 , а3 а1 , а2 , а3 а6 а4 , а5 , а7	20 10 8 20 10 5 5 10

Т=40 дней –время, выделенное для всего проекта.

Основные этапы решения оптимизационных задач.

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

1. Постановка задачи оптимизации на этом этапе приводится словесная формулировка задачи. Задача формируется в содержательных терминах той области, в которой эта задача решается. От правильной формулировки зависит правильность решения.

2. Формализация задачи.

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

3. Анализ задачи и выбор метода оптимизации на этом этапе, поскольку задача уже записана в математической форме, её конкретное содержание неважно. Разные по содержанию задачи могут приводиться к одной и той же математической постановке. При анализе внимание обращается на структуру задачи, определяется, к какому классу оптимизационных задач относится задача. Затем в соответствии с классом задачи, надо выбрать метод оптимизации. Может оказаться, что для задачи не существует метода решения, тогда надо разработать свой метод решения.

4. Разработка алгоритма и программа решения задачи на ЭВМ.

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

5. Решение задачи на ЭВМ.

На этом этапе производятся вычисления и получаем результат в удобной для нас форме.

6. Анализ результата и выдача рекомендаций.

Анализ должен быть проведен в двух аспектах:

1. Математический анализ, то есть проверка соответствия полученного решения математической постановки задач, если анализ не удовлетворительный, то возвращаемся на второй этап.

2. Проверка соответствия исходного решения задачи.

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

Лекция 3. Постановка задачи линейного программирования. Нет

Лекция 4. СВОЙСТВА РЕШЕНИЯ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАМИРОВАНИЯ.

Эти свойства связаны со свойствами выпуклых множеств.

Определение 1. Множество D называется выпуклым, если для любых двух точек Х1= (Х1, Х2,…,Хn ) и Х2= (Х1, Х2,…,Хn ) ,

которые принадлежат множеству D, и произвольного числа 

из 0,1 имеет место соотношение :

Х=Х1+(1-)Х2 , где Х – n-мерная точка, D.

Множество называется выпуклым, если вместе с двумя точками Х1 и Х2,  D, все точки отрезка (Х1,Х2) также принадлежат D.

Х2

Х1

• не является выпуклым,

т.к. существует точка, ко-

торая D.

является выпуклым.

Определение 2. Крайней точкой выпуклого множества называется точка, принадлежащая этому множеству, но которая не может быть представлена в виде линейной комбинации двух точек, т.е. ХХ1+(1-)Х2, т.е. не найдутся такие Х1 и Х2, которые образовали бы отрезок, на котором располагалась бы эта точка.

Крайние точки

Свойства:

1. Если D- выпуклое ограниченное множество, имеющее конечное число крайних точек, то любая его точка может быть представлена в виде выпуклой комбинации крайних точек:

Х= 11 +22 +…+, где n

• i =1. i =1

Определение.

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

Определение.

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

Симплексом называется n-мерный выпуклый многогранник, имеющий одну n+1 вершину.

Теорема. (Свойство выпуклости допустимых решений задачи нелинейного программирования)

Всякое множество, задаваемое системой линейных неравенств

11Х1+12Х2+…+1nХn  b1;

21Х1+22Х2+…+2nХn  b2; (2)

……………………………..

m1Х1+m2Х2+…+mnХn  bm;

Х1,Х2,…,Хn  0 ;

является выпуклым.