ПРАКТИКУМ
ПО РЕШЕНИЮ ЛИНЕЙНЫХ ЗАДАЧ
МАТЕМАТИЧЕСКОГО ПРОГРАММИРОВАНИЯ
Введение Математическое программирование – это раздел математики, который изучает теорию и методы поиска лучших вариантов планирования хозяйственной деятельности человека как на одном определенном предприятии, так и в некоторой отрасли или в отдельном регионе, или в целом государстве.
Лучшие варианты – это те, при которых достигается максимальная производительность труда, минимум себестоимости, максимальная прибыль, минимум использования ресурсов и т.д. С точки зрения математики – это класс оптимизационных задач. Основным инструментом при их решении является математическое моделирование. Математическая модель – это формальное описание изучаемого явления и «перевод» всех существующих сведений о нем на язык математики в виде уравнений, тождеств, неравенств. Если все эти соотношения линейные, то вся задача называется задачей линейного программирования (ЗЛП). Критерием эффективности этой модели является некоторая функция, которую называют целевой.
Постановка задачи линейного программирования и формы ее записи Сформулируем общую задачу линейного программирования.
Пусть дана система 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 УДЕ. Составить план производства, обеспечивающий наибольшую прибыль.
Решение. Достаточно часто при составлении математической модели экономической задачи бывает удобно данные условия представить в виде таблицы:
Сырье Кол-во сырья на ед. ............
