Xreferat.com » Рефераты по информатике и программированию » Практикум по решению линейных задач математического программирования

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

ПРАКТИКУМ

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

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


Введение


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

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


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


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

Пусть дана система 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), получим в правой части положительное число. При этом знак неравенства нужно изменить на противоположный.

2) Если ограничение содержит знак «=», то дополнительную переменную вводить не нужно.

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


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

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

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


Решение. Второе ограничение системы содержит в правой части отрицательное число –2. Умножим второе ограничение на (–1), при этом знак неравенства Практикум по решению линейных задач математического программирования изменится на противоположный Практикум по решению линейных задач математического программирования. Задача примет вид:


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

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

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


В первое и во второе ограничения добавим по дополнительной переменной Практикум по решению линейных задач математического программирования и Практикум по решению линейных задач математического программирования соответственно, а из третьего вычтем дополнительную переменную Практикум по решению линейных задач математического программирования. Имеем следующий канонический вид задачи:


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

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

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


Задания для самостоятельной работы.

Составить экономико-математические модели следующих задач:

Для изготовления двух видов продукции P1 и Р2 используют четыре вида ресурсов S1, S2, S3 и S4. Запасы ресурсов, число единиц ресурсов, затрачиваемых на изготовление единицы продукции, приведены в таблице:


Вид

ресурса

Запас

ресурса

Число ед. ресурсов,

затрачиваемых на изготовление ед. продукции



Р1 Р2
S1 18 1 3
S2 16 2 1
S3 5 1
S4 21 3

Прибыль, получаемая от единицы продукции Р1 и Р2, – соответственно 2 грн. и 3 грн.

На приобретение оборудования для нового производственного участка общей площадью 375 м2 предприятие обладает необходимым количеством денежных средств. Предприятие может заказать оборудование двух видов: машины первого типа стоимостью 10000 грн., требующие производительную площадь 6 м2 (с учетом проходов), производящие 4000 единиц продукции за смену, и машины второго типа стоимостью 20000 грн., занимающие 10 м2 площади, производящие 5000 единиц продукции за смену. Общая производительность данного производственного участка должна быть не менее 221000 единиц продукции за смену. Построить модель задачи при условии, что оптимальным для предприятия вариантом приобретения оборудования считается тот, который обеспечивает наименьшие общие затраты.

Фермер планирует произвести не менее 120 тонн пшеницы, 70 тонн кукурузы и 15 тонн гречихи. Для этого можно использовать два массива сельскохозяйственных угодий в 1000 и 800 га. В таблице приведены урожайность каждой культуры на различных участках (верхний показатель) и затраты на 1 га сельскохозяйственных угодий при производстве различных культур (нижний показатель). Требуется составить такой план засева, чтобы валовой сбор зерна удовлетворял плановому заданию, а стоимость затрат была наименьшей.


Поле Размер поля Культуры


пшеница кукуруза гречиха
I 1000

10

7

20

10

6

15

II 800

12

8

24

12

5

20

План по культурам 120 70 15

Фирма имеет возможность рекламировать свою продукцию, используя для этого телевидение, радио и газеты. Затраты на рекламу в бюджете фирмы ограничены суммой 8000 грн. в месяц. Опыт прошлых лет показал, что 1 грн., потраченная на телерекламу, дает фирме прибыль в размере 10 грн., а потраченная на рекламу по радио и в газетах – соответственно 4 и 8 грн.

Фирма намерена затратить на теле- и радиорекламу не более 70% рекламного бюджета, а затраты на газетную рекламу не должны больше чем вдвое превышать затраты на радиорекламу.

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

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


Заявка

Нужная ширина

рулона, м

Нужное кол-во

рулонов

1 0,8 150
2 1,0 200
3 1,2 300

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


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


1. Область решений линейных неравенств.

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


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

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

Пример 1. Найти полуплоскость, определяемую неравенством

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

Решение. Строим прямую Практикум по решению линейных задач математического программирования по двум точкам, например, по точкам пересечения с осями координат (0; 4) и (6; 0). Эта линия делит плоскость на две части, т.е. на две полуплоскости. Берем любую точку плоскости, не лежащую на построенной прямой. Если координаты точки удовлетворяют заданному неравенству, то областью решений является та полуплоскость, в которой находится эта точка. Если же получаем неверное числовое неравенство, то областью решений является та полуплоскость, которой эта точка не принадлежит. Обычно для контроля берут точку (0; 0).

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

Пример 2. Найти полуплоскость, определяемую неравенством

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

Решение. Строим прямую Практикум по решению линейных задач математического программирования, например, по точкам (0; 0) и (1; 3). Т.к. прямая проходит через начало координат, точку (0; 0), то нельзя брать ее для контроля. Возьмем, например, точку (– 2; 0) и подставим ее координаты в заданное неравенство. Получим Практикум по решению линейных задач математического программирования. Это неверно. Значит, областью решений данного неравенства будет та полуплоскость, которой не принадлежит контрольная точка (заштрихованная часть рис. 2).

2. Область решений системы линейных неравенств.

Пример. Найти область решений системы неравенств:

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


Решение. Находим область решений I-го неравенства (рис. 1) и II-го неравенства (рис. 2).

Все точки части плоскости, где штриховка наложилась, будут удовлетворять и первому и второму неравенству. Таким образом, получена область решений заданной системы неравенств (рис. 3).

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

Принцип нахождения решения системы линейных неравенств не зависит от количества неравенств, входящих в систему.

Примечание: Область допустимых решений (ОДР) если существует, то представляет собой замкнутый или незамкнутый выпуклый многоугольник.

3. Алгоритм графического метода решения ЗЛП

Если задача линейного программирования содержит только две переменные, то ее можно решить графическим методом, выполняя следующие операции:

Строим все полуплоскости, соответствующие ограничениям системы.

Находим область допустимых решений (ОДР), как множество точек, в котором пересекаются все построенные полуплоскости.

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

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

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: