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

ПРАКТИКУМ

ПО РЕШЕНИЮ ЛИНЕЙНЫХ ЗАДАЧ

МАТЕМАТИЧЕСКОГО ПРОГРАММИРОВАНИЯ

г. Симферополь, 2006

УДК 519.35(075)

ББК 22.18 – Я-73

А-44

Акульшина Т.С., Стебко Т.В. Практикум по решению линейных задач математического программирования. – Симферополь, УЭУ, 2006 – 44 с.

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

Рассмотрено и одобрено на заседании кафедры высшей математики

протокол № 8 от 20 апреля 2006

© Симферополь, 2006.

Введение

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

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

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

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

Пусть дана система 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
II
III
IV		–
Прибыль от ед. продукции, УДЕ

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

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

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

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

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

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

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

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

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

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