Заглавная страница Избранные статьи Случайная статья Познавательные статьи Новые добавления Обратная связь КАТЕГОРИИ:  Археология Биология Генетика География Информатика История Логика Маркетинг Математика Менеджмент Механика Педагогика Религия Социология Технологии Физика Философия Финансы Химия ЭкологияТОП 10 на сайте Приготовление дезинфицирующих растворов различной концентрацииТехника нижней прямой подачи мяча. Франко-прусская война (причины и последствия) Организация работы процедурного кабинета Смысловое и механическое запоминание, их место и роль в усвоении знаний Коммуникативные барьеры и пути их преодоления Обработка изделий медицинского назначения многократного применения Образцы текста публицистического стиля Четыре типа изменения баланса Задачи с ответами для Всероссийской олимпиады по праву 
Мы поможем в написании ваших работ! ЗНАЕТЕ ЛИ ВЫ?
Влияние общества на человека
Приготовление дезинфицирующих растворов различной концентрации Практические работы по географии для 6 класса Организация работы процедурного кабинета Изменения в неживой природе осенью Уборка процедурного кабинета Сольфеджио. Все правила по сольфеджио Балочные системы. Определение реакций опор и моментов защемления |
Задачи для практических занятийСтр 1 из 5Следующая ⇒
Методы оптимальных решений Задачи для практических занятий Модуль 1. Задача линейного программирования и ее геометрическое истолкование Содержание Тема 1. Составление математических моделей экономических задач. Тема 2. Графический метод нахождения оптимального решения ЗЛП. Контрольная работа «Графический метод решения ЗЛП»
Тема 1. составление Математических моделей экономических задач
Примеры решения типовых задач Пример 1. Задача об использовании ресурсов Предприятие располагает двумя видами сырья S 1 и S 2 в количествах 10 и 15 условных единиц и изготавливает из него изделия трех видов П 1, П 2 и П 3. Известен расход каждого вида сырья на единицу продукции, что задается матрицей расхода сырья Составить экономико-математическую модель задачи. Для наглядности данные задачи занесем в таблицу. Таблица – Исходные данные задачи об использовании сырья
Построим экономико-математическую модель. Запишем искомый план производства в виде
а целевая функция (прибыли) Математическая модель задачи имеет стандартную форму. Пример 2. Задача составления рациона (о диете, о смесях), или технологическая задача. Стоимость 1 кг корма вида I – 4 рубля, а вида II – 6 рублей. Используя данные таблицы, необходимо составить такой рацион питания, чтобы стоимость его была минимальной и содержание каждого вида питательных веществ было не менее установленного предела. Таблица - Данные задачи о рационе питания
Модель задачи будет иметь вид:
Пример 3. Технологическая задача (о раскрое материала). Найти план раскроя, обеспечивающий максимальное число комплектов.
Для изготовления брусьев длиной 1,2 м, 3 м и 5 м в соотношении 2:1:3 на распил поступает 195 бревен длиной 6 м. Определить план распила, обеспечивающий максимальное число комплектов. Составим модель задачи. Определим сначала все возможные способы распила бревен, указав соответствующее число получающихся при этом брусьев и остаток. Таблица - Способы распила бревен
Через хi обозначим число бревен распиливаемых i-м способом, Тогда экономико-математическая модель задачи будет иметь вид:
Задачи для самостоятельного решения Задача 1. Составить математическую модель задачи. Для изготовления изделий А и В используется 3 вида сырья. В таблице приведены нормы расхода сырья всех видов на изготовление единицы каждого вида изделий, запасы сырья и прибыль от реализации единицы продукции А и В. Таблица 2
Задача 2. Составить математическую модель задачи. На мебельной фабрике из стандартных листов фанеры необходимо вырезать заготовки трех видов в количестве не менее 24, 30 и 30 штук. Каждый лист фанеры может быть разрезан на заготовки двумя способами. В таблице приведено количество получаемых заготовок и величины отходов, которые получаются при раскрое одного листа фанеры при каждом способе. Сколько листов фанеры по каждому способу следует раскроить, чтобы получить минимальные отходы от раскроя? Таблица 3
Указание. Задача 3. Составить математическую модель задачи. На станках Р1 и Р2 производится два вида продукции А и В. Для изготовления 1 ед. продукции А станок Р1 используется 2 часа, а станок Р2 - 3 час. Для 1 ед. продукции В это время равно соответственно 1 час и 2 часа. Продукции А должно быть произведено не более 4 ед.
В течение суток станок Р1 может работать не более 12 часов, а станок Р2 - не более 5 часов. От реализации 1 ед. А прибыль составляет 2 ден. ед., а от 1 ед. В - 1 ден. ед. Какое количество продукции вида А и В нужно произвести, чтобы чистая прибыль была максимальной? Указание.
Задача 4. Составить математическую модель задачи. Доски длиной 4,5 м, имеющиеся в достаточном количестве, следует распилить на заготовки длиной 1,7 м и длиной 1,4 м, причем заготовок первого вида должно быть получено не менее 86 штук и заготовок второго вида - не менее 90 штук. Каждая доска может быть распилена на указанные заготовки несколькими способами. 1) Требуется найти число досок, распиливаемых каждым способом, с тем, чтобы наименьшее количество заготовок было получено: 1) из наименьшего числа досок; 2) при минимальных отходах. Указание. Для составления математической модели задачи нужно сначала определить всевозможные способы распила на заготовки нужной длины и подсчитать остатки доски от раскроя по каждому способу раскроя. Задача 5. Составить математическую модель задачи. Фирма производит и продает два типа товаров. Фирма получает прибыль в размере 12 тыс.р. от производства и продажи каждой единицы товара 1 и в размере 4 тыс.р. от производства и продажи каждой единицы товара 2. Фирма состоит из трех подразделений. Затраты труда (чел-дни) на производство этих товаров в каждом из подразделений указаны в таблице.
Руководство рассчитало, что в следующем месяце фирма будет располагать следующими возможностями обеспечения производства трудозатратами: 1800 чел-дней в подразделении 1, 1600 — в подразделении 2 и 2000 — в подразделении 3. Задача 6. Составить математическую модель задачи Телевизионная компания производит два вида телевизоров — "Астро" и "Космо". Имеются две производственные линии, каждая для своего типа телевизоров. Мощность линии по производству "Астро" составляет 70 телевизоров в день, а "Космо" — 50 единиц в день. Цех А производит телевизионные трубки. В этом цехе на производство одной трубки к телевизору "Астро" требуется потратить 1,8 чел-ч, а на производство трубки к "Космо" — 1,2 чел-ч. В настоящее время в цехе А на производство трубок к обеим маркам телевизоров может быть затрачено не более 120 чел-ч в день. В цехе Б производятся шасси. В этом цехе на производство одной единицы шасси как к телевизору "Астро", так и к "Космо" требуется затратить 1 чел-ч. В цехе Б на производство шасси к обеим маркам телевизоров может быть затрачено не более 90 чел-ч. Продажа каждого телевизора марки "Астро" обеспечивает получение прибыли в размере 150 тыс.р., а марки "Космо" — 200 тыс.р. Задача 7. Составить математическую модель задачи. В задаче выбора вариантов примем, что для получения результата в виде максимально возможной прибыли необходимо два вида ресурсов: материальные и трудовые Возможны четыре варианта расхода ресурсов и получения прибыли (табл.).
Показатели |
Варианты | Наличие | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 1 | 2 | 3 | 4 | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Прибыль, д.е./ед. Материальные ресурсы Трудовые ресурсы | 65 200 10 | 80 180 15 | 90 240 22 | 210 250 28 | – 800 50 | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
. Известна прибыль от реализации единицы продукции, которая задается вектором 
. Найти такой план производства продукции, от реализации которого предприятие получит максимальную прибыль.
, где 
- количество единиц продукции П 1, П 2, П 3 соответственно. Система ограничений по расходу сырья примет вид
, 
, 
,
.
, а через х – число комплектов брусьев.
- количество листов фанеры, раскраиваемых по 1-му и 2-му способам. Ограничения по количеству заготовок - неравенства вида 
. Целевая функция 
- общие отходы от раскроя.
- количество продукции вида А (вида В). Целевая функция - это доход от реализации продукции.
Требуется выбрать, какие варианты принять для реализации при условии, чтобы общее число принятых вариантов не превышало трех.
Примеры решения типовых задач
Пример 1. Найти наибольшее и наименьшее значения функции 
в области решений системы линейных неравенств
Решение
1. Построим область решений системы линейных неравенств.
у
1 
О 2 x
Прямая () 
, точки для построения 
и 
. Так как 
верно, то полуплоскость обращена в сторону точки 
.
Прямую (
) 
строим по точкам 
и 
; неравенство 
верное, полуплоскость направлена к началу координат.
Прямая () 
построена по точкам 
и 
; полуплоскость обращена в сторону .
Неравенства 
и 
показывают, что искомая область (пересечение всех полуплоскостей) находится в первой координатной четверти.
2. Построим градиент функции . Это вектор с координатами 
с началом в точке 
. Перпендикулярно градиенту построим одну из линий уровня.
3. Параллельным движением линии уровня в направлении градиента 
найдем точку «входа» линии уровня в область – это точка О(0,0). Вычислим значение функции в этой точке: 
.
4. Продолжая движение линии уровня в направлении градиента 
, найдем точку «выхода» линии уровня из области – это точка А. Для определения ее координат решим систему уравнений прямых и 
: 
Решение системы уравнений 
и 
. Вычислим значение функции в точке 
: 
.
Ответ: 
, 
.
Задачи для самостоятельного решения
Задача 1. Решить графическим методом задачу линейного программирования
1) 
2) 
3) 
4) 
5) 
6) 
7) 
Примеры решения типовых задач
Пример 2. Задача о рационе
Решить экономическую задачу линейного программирования графическим методом.
При составлении суточного рациона кормления скота можно использовать свежее сено не более 50 кг и силос не более 85 кг. Рацион должен содержать не менее 30 кормовых единиц, 1000 г белка, 100 г кальция и 80 г фосфора. Определить оптимальный рацион, исходя из условия минимума себестоимости.
|
|
В таблице 4 приведены данные о содержании указанных компонентов в 1 кг каждого корма и себестоимость этих кормов.
Таблица 7
|
Корм | Компоненты |
Себестоимость, ден. ед. | |||
| кормовые единицы | белок, г/кг | кальций, г/кг | фосфор, г/кг | ||
| Сено свежее, кг | 0,5 | 40 | 1,25 | 2 | 1,2 |
| Силос, кг | 0,5 | 10 | 2,5 | 1 | 0,8 |
Решение
Этап 1. Составление математической модели задачи.
Обозначим через 
и 
количество кг сена и силоса, которое предполагается включить в рацион. Естественно, что 
, 
. Из условия задачи следует, что 
(кг); 
(кг).
Количество кормовых единиц в рационе можно выразить суммой 
, что должно быть, по условию, не меньше 30: 
(ед.), или 
.
Ограничения по содержанию в рационе белка, кальция и фосфора имеют вид:
(г), или 
(для белка);
(г), или 
(для кальция);
(г) (для фосфора).
Себестоимость рациона в принятых обозначениях можно выразить формулой 
(руб.). Итак, математическая модель задачи построена.
Математическая постановка задачи: найти неотрицательные значения переменных и , которые удовлетворят системе линейных неравенств
и при которых целевая функция принимает наименьшее значение 
.
Задание
1. Составить систему ограничений, определяющую область допустимых решений (ОДР) задачи. Построить ОДР.
2. Установить графически и аналитически, возможен ли раскрой:
а) 3 листов фанеры по первому способу и 4 листов по второму способу;
б) 4 листов по первому и 2 листов по второму способу?
Какие отходы от раскроя получаются при этом?
3. Сколько листов фанеры по каждому способу следует раскроить, чтобы получить минимальные отходы от раскроя?
Задача 4. Построить математическую модель и решить графическим способом.
На станках Р1 и Р2 производится два вида продукции А и В. Для изготовления 1 ед. продукции А станок Р1 используется 4 часа, а станок Р2 - 2 часа. Для 1 ед. продукции В это время равно соответственно 7 часов и 1 час. Продукции А должно быть произведено не более 4 ед.
В течение суток станок Р1 может работать не более 28 часов, а станок Р2 - не более 10 часов. От реализации 1 ед. А прибыль составляет 2 ден. ед., а от 1 ед. В - 1 ден. ед. Какое количество продукции вида А и В нужно произвести, чтобы чистая прибыль была максимальной?
Задача 5. Найти графическим методом оптимальное решение экономической задачи. Предприятие производит два вида изделий А и В, используя сырье четырех видов. Расход сырья каждого вида на изготовление единицы продукции, запасы сырья и цены готовой продукции приведены в таблице.
| Сырье | Расход сырья на одно изделие | Запасы сырья, кг | |
| А | В | ||
| I II Ш IV | 2 1 0 2 | 3 0 1 1 | 21 4 6 10 |
| Цена одного изделия, ден.ед. | 3 | 2 | |
Считая, что сбыт готовой продукции полностью обеспечен, установить план производства изделий А и В, обеспечивающий максимальный доход от реализации. Определить, запасы каких ресурсов являются избыточными для установленного плана производства.
|
|
Задача 6. Построить математическую модель и решить графическим способом.
В районе лесного массива имеется деревообрабатывающий комбинат, изготавливающий комплекты пиломатериалов и фанеру.
Чтобы деревообрабатывающему комбинату получить 1 м3 комплектов пиломатериалов, необходимо израсходовать 4 м3 еловых и 2 м3 пихтовых лесоматериалов. Для изготовления 1 м2 фанеры требуется 3 м3 еловых и 5 м3 пихтовых лесоматериалов. Лесной массив содержит 1200 м3 еловых и 1300 м3 пихтовых лесоматериалов.
В течение планируемого периода нужно произвести не менее 50 м3 пиломатериалов и не менее 50 м2 фанеры. Доход с 1 м3 пиломатериалов составляет 150 ден. ед., а с 1 м2 фанеры - 100 ден. ед.
Сколько пиломатериалов и фанеры могут изготовить завод и фабрика, чтобы получить наибольший доход?
Примерные задачи в контрольной работе
Задача. Решить графическим методом задачу линейного программирования
1. 
| 2. 
| 3. 
| 4. 
|
Примеры решения типовых задач
Пример. Найти исходное опорное решение ЗЛП.
Запишем задачу в канонической форме, вводя в левую часть первого неравенства системы ограничений дополнительную переменную 
со знаком «+», а в левую часть второго неравенства дополнительную переменную 
со знаком «минус».
Заполним симплексную таблицу 10 (
-строку не заполняем, пока система не будет приведена к единичному базису). Система уравнений имеет две базисные переменные 
и 
(столбцы 
и 
содержат единицу и нули), отмечаем это в столбце «Базис».
Таблица 10
| Базис | 
| 
| 
|
|
| 
| 
| с.о. |
| x4 x5 | 2
1
 1
| 1 2 -1 | -2 4 2 | 1 0 0 | 0 1 0 | 0 0 -1 | 24 22 10 | 12 22 10 |
|
|
Чтобы получить еще одну базисную переменную, обратимся к столбцам небазисных переменных 
, , 
, , из которых имеют положительные элементы первый, второй, третий столбцы. Выберем среди них, например, первый столбец – он и будет разрешающим.
Составим для положительных элементов разрешающего столбца симплексные отношения 
, 
, 
(столбец с.о.). Наименьшему симплексному отношению (10) соответствует третья строка, которая и будет разрешающей строкой. На пересечении первого столбца и третьей строки находим разрешающий элемент 
. Проведем с ним одну итерацию метода исключения переменных.
Таблица 11
| Базис |
|
|
|
|
| 
| 
|
| x4 x5 x1 | 0 0 1 | 3 3 -1 | -6 2 2 | 1 0 0 | 0 1 0 | 2 1 -1 | 4 12 10 |
|
|
В таблице 8 имеется теперь три базисные переменные , и 
. Это означает, что система приведена к единичному базису 
.
Приравняем к нулю свободные переменные 
, тогда базисные переменные будут равны свободным членам 
. Запишем исходное опорное решение 
.
Пример 4. Проверить, будет ли решение 
оптимальным. Если нет, то можно ли его улучшить.
Решение
Заполним -строку. Для этого вверху таблицы запишем коэффициенты при переменных и свободный член из целевой функции, слева от таблицы – коэффициенты при базисных переменных в целевой функции. В -строке под базисными переменными 
запишем нули.
Таблица 12
| 2 | -3 | 6 | 1 | 0 | 0 | 0 | |||
| Базис |
|
|
| 
| 
|
|
| с. о. |
| 1 0 2 | x4 x5 x1 | 0 0 1 | 3 3 -1 | -6 2 2 | 1 0 0 | 0 1 0 | 2 1 -1 | 4 12 10 | |
|
|
Вычислим оценки свободных переменных, значение целевой функции 
по и заполним таблицу 10:
Таблица 13
| 2 | -3 | 6 | 1 | 0 | 0 | 0 | |||
|
| Базис |
|
|
|
|
|
|
| с. о. |
| 1 0 2 | x4 x5 x1 | 0 0 1 | 3 3 -1 | -6 2 2 | 1 0 0 | 0 1 0 | 2 1 -1 | 4 12 10 | |
|
| 0 | 4 | -8 | 0 | 0 | 0 | 24 |
Проверим, будет ли решение 
оптимальным. Из трех оценок свободных переменных в 
–строке 
, 
, 
одна оценка отрицательная - это 
- это признак того, что решение 
не является оптимальным. Значение целевой функции для решения 
находится в правом нижнем углу симплексной таблицы - это 
.
Теперь проверим, можно ли решение улучшить: в –строке выберем отрицательную оценку , в столбце над которой имеются положительные элементы. Поэтому исходное опорное решение можно улучшить.
Пример 5. Выполнить переход от решения 
к улучшенному решению 
и так далее до получения оптимального решения.
Решение
Рассмотрим симплексную таблицу 13, из которой следует решение . Для построения нового опорного решения 
нужно от базиса 
перейти к новому базису 
.
1. Выберем наибольшую по абсолютной величине отрицательную оценку 
, следовательно, столбец переменной 
станет разрешающим, а переменная 
должна быть введена в базис.
2. Для положительных элементов разрешающего столбца составим симплексные отношения 
= 6; 
= 5 (столбец с.о.), выбираем наименьшее из них – это 5, оно находится в третьей строке, которая и станет разрешающей строкой. Значит, базисная переменная этой строки 
будет выведена из базиса и станет свободной. На пересечении разрешающих столбца и строки имеем разрешающий элемент 
.
3. Проведем в таблице итерацию симплексных преобразований с выбранным разрешающим элементом:
- разделим каждый элемент разрешающей строки на разрешающий элемент a 33 = 2;
- в разрешающем столбце все элементы, кроме разрешающего элемента, заменим нулями;
- все остальные элементы таблицы, включая -строку, пересчитаем по правилу прямоугольника. Например, элемент 
в новой таблице получится равным 
. В результате получим симплексную таблицу 14.
Таблица 14
| 2 | -3 | 6 | 1 | 0 | 0 | 0 | |||
| Базис |
|
|
|
|
|
|
| с.о. | |
| 1 0 6 |
| 3 -1 1/2 | 0 4 -1/2 | 0 0 1 | 1 0 0 | 0 1 0 | -1
 2
-1/2
| 34 2 5 | - 1 - |
|
| 4 | 3 | 0 | 0 | 0 | - 4 | 64 |
4. Запишем новое опорное решение 
. В этом решении свободные переменные равны нулю: x 1 = 0, x 2 = 0, x 6 = 0, а базисные – свободным членам: x 3 = 5; x 4 = 34; x 5 = 2.
Значение целевой функции находится в правом нижнем углу симплексной таблицы: 
. Оно также проверяется путем подстановки компонент решения в целевую функцию 
.
5. Новое опорное решение «лучше» предыдущего опорного решения , так как 
. Вычислим двумя способами приращение целевой функции при переходе от к :
; 
.
Решение 
не является оптимальным, поскольку в строке оценок симплексной таблицы есть отрицательная оценка 
. Но можно улучшить, т.к. в столбце над этой оценкой имеется положительный элемент 
.
6. Отрицательная оценка 
определяет переменную, вводимую в новый базис 
- это . Определим, какую переменную следует вывести из базиса 
. Составим симплексные отношения для положительных элементов столбца над отрицательной оценкой . Такое отношение 
является единственным и выполняется для второй строки, в которой базисной переменной является , она и выведется из базиса . Проведя итерацию симплексных преобразований с разрешающим элементом 
, получим симплексную таблицу 15 с базисом 
.
Таблица 15
| 2 | -3 | 6 | 1 | 0 | 0 | 0 | |||
| Базис |
|
|
|
|
|
|
| с.о. | |
| 1 0 2 |
| 2,5 -0,5 0,25 | 2 2 0,5 | 0 0 1 | 1 0 0 | 0,5 0,5 0,25 | 0 1 0 | 35 1 5,5 | |
|
| 2 | 11 | 0 | 0 | 2 | 0 | 68 |
Опорное решение 
«лучше» решения 
, так как 
. В -строке нет отрицательных оценок, поэтому решение 
оптимальное, а значение 
- наибольшее.
Ответ: 
; 
.
Задачи для самостоятельного решения
