2.2 Общая постановка задачи

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

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

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

Математическое выражение целевой функ­ции и ее ограничений называется математической моделью экономической задачи.

Чтобы составить математическую модель задачи ЛП, не­обходимо:

— ввести обозначения переменных;

— исходя из цели экономических исследований, составить целевую функцию;

— учитывая ограничения в использовании экономических показателей задачи и их количественные закономернос­ти, записать систему ограничений

В общем виде математическая модель задачи линейного программирования (ЛП) записывается как

Z(x)=C₁X₁+C₂X₂ + ^{. . .} +С_JX_J + ^{. . .} +С_nX_{n _} max(min)

при ограничениях:

где X_i — неизвестные;a _ij , b_j , C_i — заданные постоянные вели­чины.

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

Математическая модель в более краткой записи имеет вид

Z(x) = ∑C_i X_i max(min)

при ограничениях:

Определение Допустимым решением (планом) зада­чи линейного программирования называется вектор X = (х₁, х₂, ,...х_n , ) , удовлетворяющий системе ограничений.

Множество допустимых решений образует область допус­тимых решений (ОДР).

Определение Допустимое решение, при котором целевая функция достигает своего экстремального значения, называ­ется оптимальным решением задачи линейного программиро­вания и обозначается Х_опт.

Базисное допустимое решение

Задача (о составлении плана выпуска при определенной загрузке оборудования).

Некоторому заводу требуется составить оптимальный план выпуска двух видов изделий, которые обрабатываются на четырех видах машин. Известны определенные возможности и производительность оборудования; цена изделий, обеспечивающая прибыль заводу, составляет 4 тыс. руб. за изделие I вида, 6 тыс. руб. за изделие II вида. Составить план выпуска этих изделий так, чтобы от реализации их завод получил наибольшую прибыль. В таблице 2.2 указано время, необходимое для обработки каждого из двух видов изделий на оборудовании всех четырех видов.

Таблица

Изделия	Виды машин
	1	2	3	4
I	1	0,5	1	0
II	1	1	0	1
Возможное время работы машин	18	12	12	9

Построим математическую модель.

В задаче необходимо определить план выпуска изделий, обозначим за количество изделий I вида, за количество изделий II вида. Тогда определим, сколько времени затратит 1-я машина на обработку всех изделий. Она тратит 1 ед. времени на 1 изделие типа I, значит, на штук изделий потратит ед. времени, на обработку изделий типа II затратится ед. времени. Всего резерв времени работы 1-й машины 18 ед. времени. Значит, Аналогичные рассуждения со 2-й машиной, 3-й и 4-й дадут систему ограничений:

Общая прибыль будет выражена целевой функцией .

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

2.3Формы записи задачи ЛП

В зависимости от системы ограничения различают в Л.П. три формы модели 1) каноническая 2) стандартная форма 3) общая форма.

Общая форма.

Z= c₁x₁+c₂x₂+..+c_nx_n →max( min)

В общей форме линейной математической модели:

1. Требуется найти максимум или минимум,

2. Система ограничений содержит и неравенства, и уравнения;

3. Не все переменные должны быть неотрицательными

Каноническая форма

Z= c₁x₁+c₂x₂+..+c_nx_n →max

В канонической форме линейной математической модели:

1. Требуется найти максимум целевой функции;

2. Система ограничений состоит только из уравнений;

3. Все переменные должны быть неотрицательными

Стандартная форма

Z= c1x1+c2x2+..+cnxn →max

Z= c1x1+c2x2+..+cnxn →min

В стандартной форме линейной математической модели:

1. Требуется найти максимум или минимум функции;

2. Все ограничения являются неравенствами;

3. Все переменные неотрицательные

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

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