Практикум по решению линейных задач математического программирования (стр. 2 из 11)
2) Если ограничение содержит знак «=», то дополнительную переменную вводить не нужно.
Пример. Записать задачу линейного программирования в каноническом виде.
max(min) 
, 
Решение. Второе ограничение системы содержит в правой части отрицательное число –2. Умножим второе ограничение на (–1), при этом знак неравенства
изменится на противоположный 
. Задача примет вид: max(min) 
, В первое и во второе ограничения добавим по дополнительной переменной
и 
соответственно, а из третьего вычтем дополнительную переменную 
. Имеем следующий канонический вид задачи: max(min) 
, 
Задания для самостоятельной работы.
Составить экономико-математические модели следующих задач:
1. Для изготовления двух видов продукции P1 и Р2 используют четыре вида ресурсов S1, S2, S3 и S4. Запасы ресурсов, число единиц ресурсов, затрачиваемых на изготовление единицы продукции, приведены в таблице:
2.
| Видресурса | Запасресурса | Число ед. ресурсов,затрачиваемых на изготовление ед. продукции | |
| Р1 | Р2 | ||
| S1 | 18 | 1 | 3 |
| S2 | 16 | 2 | 1 |
| S3 | 5 | – | 1 |
| S4 | 21 | 3 | – |
Прибыль, получаемая от единицы продукции Р1 и Р2, – соответственно 2 грн. и 3 грн.
3. На приобретение оборудования для нового производственного участка общей площадью 375 м2 предприятие обладает необходимым количеством денежных средств. Предприятие может заказать оборудование двух видов: машины первого типа стоимостью 10000 грн., требующие производительную площадь 6 м2 (с учетом проходов), производящие 4000 единиц продукции за смену, и машины второго типа стоимостью 20000 грн., занимающие 10 м2 площади, производящие 5000 единиц продукции за смену. Общая производительность данного производственного участка должна быть не менее 221000 единиц продукции за смену. Построить модель задачи при условии, что оптимальным для предприятия вариантом приобретения оборудования считается тот, который обеспечивает наименьшие общие затраты.
4. Фермер планирует произвести не менее 120 тонн пшеницы, 70 тонн кукурузы и 15 тонн гречихи. Для этого можно использовать два массива сельскохозяйственных угодий в 1000 и 800 га. В таблице приведены урожайность каждой культуры на различных участках (верхний показатель) и затраты на 1 га сельскохозяйственных угодий при производстве различных культур (нижний показатель). Требуется составить такой план засева, чтобы валовой сбор зерна удовлетворял плановому заданию, а стоимость затрат была наименьшей.
| Поле | Размер поля | Культуры | ||
| пшеница | кукуруза | гречиха | ||
| I | 1000 | 107 | 2010 | 615 |
| II | 800 | 128 | 2412 | 520 |
| План по культурам | 120 | 70 | 15 | |
5. Фирма имеет возможность рекламировать свою продукцию, используя для этого телевидение, радио и газеты. Затраты на рекламу в бюджете фирмы ограничены суммой 8000 грн. в месяц. Опыт прошлых лет показал, что 1 грн., потраченная на телерекламу, дает фирме прибыль в размере 10 грн., а потраченная на рекламу по радио и в газетах – соответственно 4 и 8 грн.
Фирма намерена затратить на теле- и радиорекламу не более 70% рекламного бюджета, а затраты на газетную рекламу не должны больше чем вдвое превышать затраты на радиорекламу.
Определить такой вариант распределения рекламного бюджета по разным направлениям рекламы, который дает фирме наибольшую прибыль от рекламы своей продукции.
6. Продукция фабрики выпускается в виде бумажных рулонов стандартной ширины – 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).Принцип нахождения решения системы линейных неравенств не зависит от количества неравенств, входящих в систему.
Примечание: Область допустимых решений (ОДР) если существует, то представляет собой замкнутый или незамкнутый выпуклый многоугольник.