Введение

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

Лучшие варианты – это те, при которых достигается максимальная производительность труда, минимум себестоимости, максимальная прибыль, минимум использования ресурсов и т.д. С точки зрения математики – это класс оптимизационных задач. Основным инструментом при их решении является математическое моделирование. Математическая модель – это формальное описание изучаемого явления и «перевод» всех существующих сведений о нем на язык математики в виде уравнений, тождеств, неравенств. Если все эти соотношения линейные, то вся задача называется задачей линейного программирования (ЗЛП). Критерием эффективности этой модели является некоторая функция, которую называют целевой.

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

Сформулируем общую задачу линейного программирования.

Пусть дана система mлинейных уравнений и неравенств сn переменными (система ограничений):

(1)

и линейная функция

. (2)

Необходимо найти такое решение

системы (1), при котором линейная функция

принимает максимальное (минимальное) значение.

В общем случае ЗЛП может иметь бесконечное множество решений. Часто решение

, удовлетворяющее ограничениям (1), называют планом. Если все компоненты

(3) для

, то

называют допустимым решением.

Оптимальным решением или оптимальным планом задачи линейного программирования называется такое ее решение

, которое удовлетворяет всем ограничениям системы (1), условию (3) и при этом дает максимум (минимум) целевой функции (2).

Каноническая	Стандартная	Общая
1)*Ограничения*
Уравнения ,	Неравенства ,	Уравнения и неравенства ,
2)*Условия неотрицательности*
Все переменные ,	Все переменные ,	Часть переменных , ,
3)*Целевая функция*
(max илиmin)

Здесь:

– переменные задачи;

– коэффициенты при переменных в целевой функции;

– коэффициенты при переменных в основных ограничениях задачи;

– правые части ограничений.

Пример. Составить экономико-математическую модель задачи: Для выпуска изделий двух типов А и В на заводе используют сырье четырех видов (I, II, III, IV). Для изготовления изделия А необходимо: 2 ед. сырья первого вида, 1 ед. второго вида, 2 ед. третьего вида и 1 ед. четвертого вида. Для изготовления изделия В требуется: 3 ед. сырья первого вида, 1 ед. второго вида, 1 ед. третьего вида. Запасы сырья составляют: I вида – 21 ед., II вида – 8 ед., III вида – 12 ед., IV вида – 5 ед. Выпуск одного изделия типа А приносит 3 УДЕ прибыли, а одного изделия типа В – 2 УДЕ. Составить план производства, обеспечивающий наибольшую прибыль.

Решение.Достаточно часто при составлении математической модели экономической задачи бывает удобно данные условия представить в виде таблицы:

Сырье	Кол-во сырья на ед. продукции, ед.		Запас сырья, ед.
Сырье	А	В	Запас сырья, ед.
I	2	3	21
II	1	1	8
III	2	1	12
IV	1	–	5
Прибыль от ед. продукции, УДЕ	3	2

Пусть

– количество изделий типа А и В соответственно, планируемое к выпуску (

Тогда прибыль составит:

, т. к. план производства должен обеспечивать наибольшую прибыль, то целевая функция задачи:

Составим систему ограничений, используя заданную ограниченность сырья. При планируемых объемах производства расходуется сырья Iвида:

(ед.), что не должно превышать запас 21 ед. Т.о. получим неравенство:

. Составляя неравенства по каждому виду сырья, получим систему:

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

Пример. Составить математическую модель задачи: На четырех станках (I, II, III, IV) обрабатываются два вида деталей (А и В). Каждая деталь проходит обработку на всех станках. Известны время обработки деталей на каждом станке, время работы станков в течение одного цикла производства и прибыль, полученная от выпуска одной детали. Данные приведены в таблице:

Станки	Время обработки детали, ч.		Время работы станка(цикл пр-ва), ч.
Станки	А	В	Время работы станка(цикл пр-ва), ч.
I	1	2	16
II	2	3	26
III	1	1	10
IV	3	1	24
Прибыль от 1 детали, УДЕ	4	1

Составить план производства, обеспечивающий наибольшую прибыль при условии, что количество деталей вида В не должно быть меньше количества деталей вида А.

Решение.Пусть

– количество деталей вида А и В соответственно, планируемое к выпуску (

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

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

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

Приведение задач к каноническому виду

Пусть имеем задачу общего вида, которую нужно привести к каноническому виду, т.е. из ограничений-неравенств сделать ограничения-равенства. Для этого в каждое ограничение вводится дополнительная неотрицательная балансовая переменная со знаком «+», если знак неравенства «

», и со знаком «–», если знак неравенства «

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

Примечание: 1) В канонической форме равенства принято записывать так, чтобы правые части ограничений были неотрицательными. Если какое-либо

отрицательное, то умножив i-е ограничение на (–1), получим в правой части положительное число. При этом знак неравенства нужно изменить на противоположный.

Практикум по решению линейных задач математического программирования (стр. 1 из 11)

Введение

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

Приведение задач к каноническому виду