Тема 3. . Постановка и классификация задач мп.

Операция – управляемое мероприятие, направленное на достижение цели.

Условие задачи математического программирования состоит из:

(1) = целевой функции, характеризующей зависимость

результата операций от её факторов, переменных ЗМП.

(2) системы ограничений, состоящей из m равенств или неравенств,

показывающей связи между факторами операции,

…

Допустимым решением ЗМП называют любой n-мерный вектор , удовлетворяющий системе ограничений (2) и естественному условию неотрицательности переменных

Совокупность всех допустимых решений образуют область в n-мерном пространстве – ОДР.

Решить ЗМП – выбрать из всех допустимых решений то, при котором результат операции будет наилучшим (целевая функция (1) достигнет своего наибольшего или наименьшего значения).

Оптимальным решением ЗМП называется допустимое решение ЗМП, при котором целевая функция = достигает экстремума.

Классификация задач МП.

ЗМП	Динамические
	Статические	Невыпуклое программирование
		Выпуклое программирование	Нелинейное программирование
			Задачи Линейного Программирования (в т. ч. целочисленные, в т.ч. транспортные )

Задачи выпуклого программирования - ЗМП, в которых и целевая функция и все ограничения – выпуклые функции.

ЗЛП – ЗМП, в которых и целевая функция и все ограничения – линейны относительно переменных задачи.

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

Транспортные задачи - ЗЛП в канонической форме, коэффициенты при переменных в ограничениях равны нулю или единице и каждая переменная входит в систему ограничений два раза.

Различают общую (см.(2)), каноническую и стандартную формы системы ограничений:

Система ограничений линейной задачи в канонической форме состоит из одних равенств:	Система ограничений ЛЗ в стандартной форме состоит из неравенств одного направления:
…….	…….

Приведение ЗЛП к каноническому виду: Если условия ограничения содержат неравенство, преобразовываем его в равенство, добавляя «слабые» переменные (со знаком «+» для « », и со знаком «-» для « »). В целевую функцию слабые переменные входят с нулевыми коэффициентами.

Приведение ЗЛП к стандартному виду: Изменяем знаки неравенств, умножая их на (-1). В равенства вводим дополнительные (слабые) переменные.