Тема 1. Постановка задачи линейного программирования. Геометрический метод решения задач линейного программирования. Основные понятия, теоремы, следствия.

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

Среди оптимизационных задач наиболее известны задачи линейного программирования (ЛП), в которых функция f(x) является линейной, а ограничения задаются либо линейными равенствами, либо неравенствами.

Существует ряд экономических задач, которые сводятся к линейным математическим моделям.

Для практического решения экономической задачи математическими методами ее следует записать с помощью экономико-математической модели.

Экономико-математическая модель – это математическое описание исследуемого математического процесса или объекта. Модель выражает закономерности экономического процесса в абстрактном виде с помощью математических соотношений [7].

Можно выделить следующие основные этапы построения математической модели [12].

1. Определение цели, т.е. чего хотят добиться, решая поставленную задачу.

2. Определение параметров модели, т.е. заранее известных фиксированных факторов, на значения которых исследователь не влияет.

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

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

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

При решении задач оптимизации можно встретить различные виды задач ЛП.

Виды задач лп:

1. общая задача ЛП;

2. стандартная задача ЛП;

3. каноническая задача ЛП.

Постановка задачи линейного программирования (лп).

В общем виде математическая запись задачи линейного программирования формулируется следующим образом:

Заданы переменные ,, …,.

Требуется найти такие значения переменных ,, …,, которые приводят к экстремальному значению целевой функции(1),

(1)

удовлетворяют системе линейных ограничений (2)

(2)

а также удовлетворяют и, при необходимости, условию неотрицательности

(3)

Система линейных ограничений (2) может содержать как равенства, так и неравенства.

Таким образом, общей задачей ЛП называется задача, в которой имеются ограничения, как в виде равенств, так и в виде неравенств, кроме того, требование неотрицательности может быть наложено не на все переменные [8].

Стандартная задача – это задача с однотипными ограничениями – неравенствами и неотрицательными переменными. В стандартных задачах соотношение между числами неизвестных n и числом ограничений m может быть произвольным [8].

Каноническая задача – задача, где все переменные не являются отрицательными, а ограничения имеют форму равенства. В канонической задаче количество неизвестных всегда больше числа уравнений(n>m) [8].

Замечание: Любая задача ЛП может быть сведена к канонической, стандартной или общей задаче, т.е. задачи эквивалентны между собой.

Отразим основные черты задач линейного программирования в нижеприведенной таблице 1.

Таблица 1

Виды задач ЛП

Задача ЛП в общем виде:	Стандартная задача:	Каноническая задача
Переменные: , , …,.	Переменные: , , …,. Соотношение между числами неизвестных n и числом ограничений m может быть произвольным	Переменные: , , …,. В канонической задаче количество неизвестных всегда больше числа уравнений(n>m)
Целевая функция (ЦФ):	ЦФ: (*) (**)	ЦФ:
Система ограничений (СО):	СО: (*) (**)	СО:
Условие неотрицательности (УН) не на все переменные	УН:	УН:

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

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