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

ПЗ: Дана линейная функция L(x1,x2,...,xn) n переменных. Необходимо найти точку оптимума этой функции: L(x) ---> opt ,

при ограничениях: Ax-b>= 0 или , i=1...m.

где x = (x1,x2,...,xn).

1) при ограничении вида

2)

3)

4)

1) при ограничении вида

18. Общая и стандартная постановки злп. Переход от общей постановки задачи к стандартной.

Общая: Дана линейная функция L(x1,x2,...,xn) n переменных. Необходимо найти точку оптимума этой функции: L(x) ---> opt ,

при ограничениях: Ax-b>= 0 или , i=1...m.

где x = (x1,x2,...,xn).

Стандартная: Ax=b

Для приведения задачи к стандартному виду: ввести переменные и записать целевую функцию и ограничение задачи.

Метод и алгоритм решения стандартной задачи линейного программирования и способы сведения любой задачи линейного программирования к стандартной форме, которая состоит в следующем. Задана система m линейных алгебраических уравнений с n неизвестными:

(3.7)

и линейная функция относительно переменных х₁, х₂, ¼, х_n:

(3.8)

Требуется найти такие неотрицательные значения переменных х₁, х₂, ¼, х_n, которые бы удовлетворяли системе линейных уравнений (3.7) и, кроме того, обращали в максимум линейную функцию (3.8).

Заметим, что если по условиям задачи требуется отыскать минимум функции L, записанной в виде (3.8), то задачу можно свести к задаче максимизации функции L¢, связанной с функцией L так:

L¢ = - L = -c₁x₁ - c₂x₂ - ¼ - c_nx_n. (3.9)

Максимум функции (3.9) и минимум функции (3.8) будут достигаться при одном и том же наборе переменных (х₁, х₂, ¼, х_n), удовлетворяющих условиям неотрицательности переменных и уравнениям (3.7), областью определения задачи.

Пример перехода от общей задачи к стандартной в 20 вопросе.

19. Графическое решение злп. Основные понятия и идея решения задачи.

Если число неизвестных в задаче линейного программирования равно двум, т.е. n = 2, то ее можно решить графическим методом. Кроме того, графический метод дает геометрическую интерпретацию решения ЗЛП.

Пример:

Задача: Предприятие производит краски 2-х видов: I – для внутренних работ, E – для внешних работ. A,B – исходные продукты, использующиеся для производства I,E.

Доход от реализации 1т краски I – 2000$, E – 3000$

Коэффициенты расхода исходных продуктов A и B на производство 1т краски I и E:

	I	E	Суточный запас, тонн
A	2	1	6
B	1	2	8

Известно, что суточная потребность краски для внутренних работ не превышает 2т, т.е. суточный спрос на I <=2т. Суточный спрос I не превышает суточного спроса на E больше чем на 1т.

Найти: оптимальный суточный план производства красок, максимизирующий ожидаемый максимальный доход.

Математическая постановка задачи:

Обозначим X_I(т/сут) – краски I ; X_E(т/сут) – краски E.

Целевая функция: - ожидаемый максимальный доход

Ограничения на запас продукта А:

Ограничения на запас продукта В:

, ,

При X_I=0 и X_E=0

Найдем точку пересечения:

-3X_I=-4 X_I=4/3 X_E=10/3

Z(4/3;10/3)=38/3 Z(0;4)=12

Идея решения задачи: Используя Симплекс-метод, получить последовательность базисных решений и оптимальное решение.

Целевая функция представляет собой взвешенную линейную сумму от неизвестных переменных x_i вида: Z=c*x_i c- вектор целевой функции.

Ограничения, накладываемые на область возможных решений, имеют вид линейных равенств или неравенств: где a_i, b_i - известные величины, причем величины a_j, x_i, b_i положительные.

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

х₁ ³ 0, х₂ ³ 0, ¼ , х_n ³ 0, (3.10)

удовлетворяющих уравнениям

Оптимальным решением будем называть то из допустимых решений, для которого линейная форма Z обращается в максимум (минимум).