ПОЗНАВАТЕЛЬНОЕ

Оси и плоскости тела человека - Тело человека состоит из определенных топографических частей и участков, в которых расположены органы, мышцы, сосуды, нервы и т.д.

Отёска стен и прирубка косяков - Когда на доме не достаёт окон и дверей, красивое высокое крыльцо ещё только в воображении, приходится подниматься с улицы в дом по трапу.

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

ТИПЫ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

Построение математических моделей

Задача об оптимальном планировании производства

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

Таблица 6

Виды сырья	Количество ед. сырья, идущих на изготовление единицы продукции	Запасы сырья
( )	( )
( )
( )
( )
Прибыль от реализации ед. продукции

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

Составим математическую модель задачи. Обозначим через — количество продукции , выпускаемое предприятием, — количество продукции , выпускаемое предприятием. Умножая удельные запасы ресурса (12 или 4) на соответствующие объемы и продукции и , получим:

— затраты ресурса на весь выпуск продукции ,

— затраты ресурса на весь выпуск продукции .

Тогда — суммарные затраты ресурса на весь выпуск продукции и . Так как суммарные затраты ресурса не должны превышать его запасов, равных 300 единицам, то получим ограничение, имитирующее использование ресурса :

Аналогично получим ограничения, имитирующие использование ресурсов и :

На переменные и следует наложить естественные ограничения

, .

Через обозначим прибыль, полученную предприятием от реализации всей продукции. Так как известны прибыли от реализации единицы продукции каждого вида (30 и 40), то

Окончательно математическая модель задачи имеет вид

(4.6)

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

(4.7)

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

ТИПЫ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

Общей задачей ЛП называется задача, которая формулируется следующим образом:

Найти максимальное (минимальное) значение линейной функции

(2.1)

при условиях

( ), (2.2)

( ), (2.3)

( ) (2.4)

где , , — заданные постоянные величины и .

Функция (2.1) называется целевой функцией (или линейной формой) задачи (2.1)-(2.4), а условия (2.2)–(2.4) — ограничениями данной задачи.

Стандартная (или симметрическая) задача ЛП состоит в определении максимума функции (2.1) при ограничениях неравенствах (2.2) и условиях (2.4), где , т.е. имеет вид:

( ), (2.5)

, ( ).

Каноническая (или основная) задача ЛП состоит в определении максимума функции (2.1) при ограничениях-равенствах (2.3) и условиях (2.4):

( ), (2.6)

, ( ).

Задачу ЛП можно записать более компактно, если ввести обозначения:

— матрица ограничений размерности ( ),

— вектор-столбец свободных членов,

— вектор-строка коэффициентов целевой функции,

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

Тогда стандартная задача (2.5) примет вид:

, (2.7)

а каноническая задача (2.6) –

, (2.8)

Здесь (или — в ином обозначении — ) — скалярное произведение векторов c и x, т.е.

— произведение матрицы А на вектор-столбец x.

Вектор , удовлетворяющий ограничениям задачи (2.2)–(2.4), называется допустимым решением (или планом). Обозначим множество всех допустимых планов задачи .

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

— неразрешимость первого типа (НР1), если множество допустимых планов пусто ( Ø ‌);

— неразрешимость второго типа (НР2), если целевая функция не ограничена на непустом множестве ‌ ( Ø).‌

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

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

т.е. задача ‌‌ соответствует задаче

;

2) чтобы изменить в ограничении-неравенстве неравенство на неравенство противоположного смысла, следует умножить обе части неравенства на (–1):

;

3) чтобы перейти от ограничения-неравенства к равенству, нужно ввести дополнительную (слабую) переменную :

;

4) чтобы перейти от ограничения-равенства к неравенству, следует заменить это равенство на два противоположных неравенства:

;

5) чтобы исключить свободную переменную (т.е. такую, для которой

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

, , .

Пример. Привести к каноническому виду задачу ЛП:

Перейдём к задаче на максимум:

введём дополнительные переменные, исключив ограничения-неравенства:

Исключим свободную переменную , используя замену

Окончательно получим: