Практика
.pdf
Стоимость |
|
2000 |
2500 |
4000 |
3500 |
3800 |
|
единицы |
|
|
|
|
|
|
|
продукции (руб) |
|
|
|
|
|
|
|
Выпуск (штук) |
120 |
90 |
20 |
40 |
30 |
|
|
минимальный |
|
|
|
|
|
|
|
Выпуск |
(штук) |
480 |
560 |
180 |
160 |
120 |
|
максимальный |
|
|
|
|
|
|
|
Требуется определить такой план производства, при котором стоимость ее реализации будет максимальной.
Задача 13
Продукция производится на трех предприятиях 1, 2, 3, а затем развозится в 4 пункта назначения 1, 2, 3, 4. Стоимость перевозки единицы продукции, запасы и потребности продукции содержатся в таблице. Найти такой план перевозки продукции, при котором суммарные транспортные расходы минимальны.
Пункты |
Пункты назначения |
|
|
Запасы |
|
отправления |
|
|
|
|
|
1 |
2 |
3 |
4 |
|
|
|
|
||||
|
|
|
|
|
|
1 |
5 |
4 |
3 |
4 |
160 |
2 |
3 |
2 |
5 |
5 |
80 |
3 |
1 |
6 |
3 |
2 |
60 |
Потребности |
80 |
80 |
60 |
80 |
|
|
|
|
|
|
|
Решить задачу методом потенциалов.
РЕШЕНИЕ:
Запишем экономико-математическую модель для нашей задачи.
Переменные:
x11 – количество груза из 1-го склада к 1-у потребителю. x12 – количество груза из 1-го склада к 2-у потребителю. x13 – количество груза из 1-го склада к 3-у потребителю. x14 – количество груза из 1-го склада к 4-у потребителю. x21 – количество груза из 2-го склада к 1-у потребителю.
x22 – количество груза из 2-го склада к 2-у потребителю. x23 – количество груза из 2-го склада к 3-у потребителю. x24 – количество груза из 2-го склада к 4-у потребителю. x31 – количество груза из 3-го склада к 1-у потребителю. x32 – количество груза из 3-го склада к 2-у потребителю. x33 – количество груза из 3-го склада к 3-у потребителю. x34 – количество груза из 3-го склада к 4-у потребителю.
Ограничения по запасам:
x11 + x12 + x13 + x14 ≤ 160 (для 1 базы) x21 + x22 + x23 + x24 ≤ 80 (для 2 базы) x31 + x32 + x33 + x34 ≤ 60 (для 3 базы)
Ограничения по потребностям:
x11 + x21 + x31 = 80 (для 1-го потребителя.) x12 + x22 + x32 = 80 (для 2-го потребителя.) x13 + x23 + x33 = 60 (для 3-го потребителя.) x14 + x24 + x34 = 80 (для 4-го потребителя.)
Целевая функция:
5x11 + 4x12 + 3x13 + 4x14 + 3x21 + 2x22 + 5x23 + 5x24 + 1x31 + 6x32 + 3x33 + 2x34 → min
Стоимость доставки единицы груза из каждого пункта отправления в соответствующие пункты назначения задана матрицей тарифов
|
1 |
2 |
3 |
4 |
Запас |
|
|
|
|
|
ы |
1 |
5 |
4 |
3 |
4 |
160 |
2 |
3 |
2 |
5 |
5 |
80 |
3 |
1 |
6 |
3 |
2 |
60 |
Потре |
80 |
80 |
60 |
80 |
|
бност |
|
|
|
|
|
и |
|
|
|
|
|
Проверим необходимое и достаточное условие разрешимости задачи.
∑a = 160 + 80 + 60 = 300
∑b = 80 + 80 + 60 + 80 = 300
Условие баланса соблюдается. Запасы равны потребностям. Следовательно, модель транспортной задачи является закрытой.
Занесем исходные данные в распределительную таблицу.
|
1 |
2 |
3 |
4 |
Запас |
|
|
|
|
|
ы |
1 |
5 |
4 |
3 |
4 |
160 |
2 |
3 |
2 |
5 |
5 |
80 |
3 |
1 |
6 |
3 |
2 |
60 |
Потре |
80 |
80 |
60 |
80 |
|
бност |
|
|
|
|
|
и |
|
|
|
|
|
Этап I. Поиск первого опорного плана.
1. Используя метод северо-западного угла, построим первый опорный план транспортной
задачи.
План начинается заполняться с верхнего левого угла.
Искомый элемент равен c11=5. Для этого элемента запасы равны 160, потребности 80. Поскольку минимальным является 80, то вычитаем его.
x11 = min(160,80) = 80.
5 |
4 |
3 |
4 |
160 - |
|
|
|
|
80 = |
|
|
|
|
80 |
x |
2 |
5 |
5 |
80 |
x |
6 |
3 |
2 |
60 |
80 - 80 |
80 |
60 |
80 |
|
= 0 |
|
|
|
|
Искомый элемент равен c12=4. Для этого элемента запасы равны 80, потребности 80. Поскольку минимальным является 80, то вычитаем его.
x12 = min(80,80) = 80.
5 |
4 |
x |
x |
80 - 80 |
|
|
|
|
= 0 |
x |
2 |
5 |
5 |
80 |
x |
6 |
3 |
2 |
60 |
0 |
80 - 80 |
60 |
80 |
|
|
= 0 |
|
|
|
Искомый элемент равен c23=5. Для этого элемента запасы равны 80, потребности 60. Поскольку минимальным является 60, то вычитаем его.
x23 = min(80,60) = 60.
5 |
4 |
x |
x |
0 |
x |
2 |
5 |
5 |
80 - 60 |
|
|
|
|
= 20 |
x |
6 |
x |
2 |
60 |
0 |
0 |
60 - 60 |
80 |
|
|
|
= 0 |
|
|
Искомый элемент равен c24=5. Для этого элемента запасы равны 20, потребности 80. Поскольку минимальным является 20, то вычитаем его.
x24 = min(20,80) = 20.
5 |
4 |
x |
x |
0 |
x |
2 |
5 |
5 |
20 - 20 |
|
|
|
|
= 0 |
x |
6 |
x |
2 |
60 |
0 |
0 |
0 |
80 - 20 |
|
|
|
|
= 60 |
|
Искомый элемент равен c34=2. Для этого элемента запасы равны 60, потребности 60. Поскольку минимальным является 60, то вычитаем его.
x34 = min(60,60) = 60.
5 |
4 |
x |
x |
0 |
x |
2 |
5 |
5 |
0 |
x |
6 |
x |
2 |
60 - 60 |
|
|
|
|
= 0 |
0 |
0 |
0 |
60 - 60 |
|
|
|
|
= 0 |
|
Далее, согласно алгоритму, ищем элементы среди не вычеркнутых.
5 |
4 |
3 |
4 |
160 |
3 |
2 |
5 |
5 |
80 |
1 |
6 |
3 |
2 |
60 |
80 |
80 |
60 |
80 |
|
Искомый элемент равен c13=3, но т.к. ограничения выполнены, то x13=0.
|
1 |
2 |
3 |
4 |
Запас |
|
|
|
|
|
ы |
1 |
5[80] |
4[80] |
3[0] |
4 |
160 |
2 |
3 |
2 |
5[60] |
5[20] |
80 |
3 |
1 |
6 |
3 |
2[60] |
60 |
Потре |
80 |
80 |
60 |
80 |
|
бност |
|
|
|
|
|
и |
|
|
|
|
|
В результате получен первый опорный план, который является допустимым, так как все грузы из баз вывезены, потребность потребителей удовлетворена, а план соответствует системе ограничений транспортной задачи.
2. Подсчитаем число занятых клеток таблицы, их 6, а должно быть m + n - 1 = 6. Следовательно, опорный план является невырожденным.
Значение целевой функции для этого опорного плана равно:
F(x) = 5*80 + 4*80 + 5*60 + 5*20 + 2*60 = 1240
Ответ:
Анализ оптимального плана.
Из 1-го склада необходимо груз направить к 2-у потребителю (20), к 3-у потребителю (60), к 4-у потребителю (80)
Из 2-го склада необходимо груз направить к 1-у потребителю (20), к 2-у потребителю (60)
Из 3-го склада необходимо весь груз направить к 1-у потребителю.
Задача 14
На предприятии для производства двух видов продукции используется 2 вида ресурсов. Расход каждого вида ресурса на изготовление единицы каждого вида продукции, запасы каждого вида ресурсов, а также доходы от реализации единицы каждого вида продукции приведены в таблице.
Составить план выпуска продукции, обеспечивающий предприятию максимальную прибыль от реализации всей продукции.
Таблица – Исходная информация задачи
Вид ресурса |
Необходимое количество условных единиц |
Запас |
|
ресурсов на единицу продукции |
ресурса |
|
|
П1 |
П2 |
|
|
|
|
|
|
S |
1 |
2 |
1 |
8 |
|
|
|
|
|
|
|
|
|
|
S |
2 |
1 |
2 |
10 |
|
|
|
|
|
|
|
|
|
|
Доход от реализации |
1 |
1 |
|
|
единицы продукции |
|
|
|
|
|
|
|
|
|
РЕШЕНИЕ:
Переменные:
x11 – количество груза из 1-го склада к 1-у потребителю. x12 – количество груза из 1-го склада к 2-у потребителю. x21 – количество груза из 2-го склада к 1-у потребителю. x22 – количество груза из 2-го склада к 2-у потребителю.
Ограничения по запасам:
x11 + x12 ≤ 8 (для 1 базы)
x21 + x22 ≤ 10 (для 2 базы)
Ограничения по потребностям:
x11 + x21 = 1 (для 1-го потребителя.)
x12 + x22 = 1 (для 2-го потребителя.)
Целевая функция:
2x11 + 1x12 + 1x21 + 2x22 → max
Стоимость доставки единицы груза из каждого пункта отправления в соответствующие пункты назначения задана матрицей тарифов
|
1 |
2 |
Запас |
|
|
|
ы |
1 |
2 |
1 |
8 |
2 |
1 |
2 |
10 |
Потре |
1 |
1 |
|
бност |
|
|
|
и |
|
|
|
Проверим необходимое и достаточное условие разрешимости задачи.
∑a = 8 + 10 = 18
∑b = 1 + 1 = 2
Как видно, суммарная потребность груза в пунктах назначения меньше запасов груза на базах. Следовательно, модель исходной транспортной задачи является открытой. Чтобы получить закрытую модель, введем дополнительную (фиктивную) потребность, равной 16 (18—2). Тарифы перевозки единицы груза к этому потребителю полагаем равны нулю.
Занесем исходные данные в распределительную таблицу.
|
1 |
2 |
3 |
Запас |
|
|
|
|
ы |
1 |
2 |
1 |
0 |
8 |
2 |
1 |
2 |
0 |
10 |
Потре |
1 |
1 |
16 |
|
бност |
|
|
|
|
и |
|
|
|
|
Этап I. Поиск первого опорного плана.
1. Используя метод наибольшей стоимости, построим первый опорный план транспортной задачи.
Суть метода заключается в том, что из всей таблицы стоимостей выбирают наибольшую, и в клетку, которая ей соответствует, помещают меньшее из чисел ai, или bj.
Затем, из рассмотрения исключают либо строку, соответствующую поставщику, запасы которого полностью израсходованы, либо столбец, соответствующий потребителю, потребности которого полностью удовлетворены, либо и строку и столбец, если израсходованы запасы поставщика и удовлетворены потребности потребителя.
Из оставшейся части таблицы стоимостей снова выбирают наибольшую стоимость, и процесс распределения запасов продолжают, пока все запасы не будут распределены, а потребности удовлетворены.
Искомый элемент равен c22=2. Для этого элемента запасы равны 10, потребности 1. Поскольку минимальным является 1, то вычитаем его.
x22 = min(10,1) = 1.
2 |
x |
0 |
8 |
1 |
2 |
0 |
10 - 1 |
|
|
|
= 9 |
1 |
1 - 1 = |
16 |
|
|
0 |
|
|
Искомый элемент равен c11=2. Для этого элемента запасы равны 8, потребности 1. Поскольку минимальным является 1, то вычитаем его.
x11 = min(8,1) = 1.
2 |
x |
0 |
8 - 1 = |
|
|
|
7 |
x |
2 |
0 |
9 |
1 - 1 = |
0 |
16 |
|
0 |
|
|
|
Искомый элемент равен c23=0. Для этого элемента запасы равны 9, потребности 16. Поскольку минимальным является 9, то вычитаем его.
x23 = min(9,16) = 9.
2 |
x |
0 |
7 |
x |
2 |
0 |
9 - 9 = |
|
|
|
0 |
0 |
0 |
16 - 9 |
|
|
|
= 7 |
|
Искомый элемент равен c13=0. Для этого элемента запасы равны 7, потребности 7. Поскольку минимальным является 7, то вычитаем его.
x13 = min(7,7) = 7.
2 |
x |
0 |
7 - 7 = |
|
|
|
0 |
x |
2 |
0 |
0 |
0 |
0 |
7 - 7 = |
|
|
|
0 |
|
|
1 |
2 |
3 |
Запас |
|
|
|
|
ы |
1 |
2[1] |
1 |
0[7] |
8 |
2 |
1 |
2[1] |
0[9] |
10 |
Потре |
1 |
1 |
16 |
|
бност |
|
|
|
|
и |
|
|
|
|
В результате получен первый опорный план, который является допустимым, так как все грузы из баз вывезены, потребность потребителей удовлетворена, а план соответствует системе ограничений транспортной задачи.
2. Подсчитаем число занятых клеток таблицы, их 4, а должно быть m + n - 1 = 4. Следовательно, опорный план является невырожденным.
Значение целевой функции для этого опорного плана равно:
F(x) = 2*1 + 0*7 + 2*1 + 0*9 = 4
Этап II. Улучшение опорного плана.
Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0.
u1 + v1 = 2; 0 + v1 = 2; v1 = 2
u1 + v3 = 0; 0 + v3 = 0; v3 = 0
u2 + v3 = 0; 0 + u2 = 0; u2 = 0
u2 + v2 = 2; 0 + v2 = 2; v2 = 2
|
v1=2 |
v2=2 |
v3=0 |
u1=0 |
2[1] |
1 |
0[7] |
u2=0 |
1 |
2[1] |
0[9] |
Опорный план является оптимальным, так все оценки свободных клеток удовлетворяют условию ui + vj ≤ cij.
Максимальная прибыль составит: F(x) = 2*1 + 0*7 + 2*1 + 0*9 = 4
Ответ:
Анализ оптимального плана.
Из 1-го склада необходимо часть груза (1) направить к 1-у потребителю.
Из 2-го склада необходимо часть груза (1) направить к 2-у потребителю.
На 1-ом складе остался невостребованным груз в количестве 7 ед.
Оптимальный план является вырожденным, так как базисная переменная x13=0.
На 2-ом складе остался невостребованным груз в количестве 9 ед.
Оптимальный план является вырожденным, так как базисная переменная x23=0.
Задача 15
Предприятие располагает двумя видами сырья S1 и S2 в количествах 15 и 13 условных единиц и изготавливает из него изделия двух видов П1 и П2. Изготовление единицы изделия П1 требует расхода сырья S1 в 1 усл.ед., S2 в 3 усл.ед., а для производства единицы изделия П2 необходимо сырья S1 – 3 усл.ед., сырья S2 - 1 усл.ед. Известна прибыль от реализации одной единицы продукции каждого вида. Для вида П1 она составляет 2 ден.ед, для вида П2 – 3 ден.ед. Требуется найти оптимальный план производства продукции, реализация которого обеспечит предприятию максимальную прибыль.
1) Составим математическую модель исходной задачи.
Представим исходные данные в виде таблицы:
Вид сырья |
Нормы расхода сырья на |
Запасы |
|
одно изделие |
сырья |
||
|
|||
|
|
|
|
П1 |
П2 |
|
|
|
|
|
S1 |
1 |
3 |
15 |
|
|
|
|
S2 |
3 |
1 |
13 |
|
|
|
|
Прибыль от реализации |
|
|
|
одной единицы |
2 |
3 |
|
продукции, ден.ед. |
|
|
|
|
|
|
|
Объектом моделирования является процесс получения максимальной прибыли, а целью – оптимизация структуры и объема производства.
Задача относится к классу оптимизационных задач. Математическая модель для задач такого класса состоит в построении целевой функции, для которой надо найти экстремум, при ограничениях.
Для решения поставленной задачи введем обозначения:
х1 – объем производства изделий вида П1;
х2 – объем производства изделий вида П2.
Общую прибыль от реализации изделий можно определить по формуле:
F(X ) 2x |
3x |
2 |
1 |
|
(ден.ед.)
Функция F называется целевой, ее следует максимизировать. Поэтому получаем:
F 2x |
3x |
2 |
max |
1 |
|
|
На целевую функцию накладываются следующие ограничения:
а) объем выпуска изделий каждого вида не может быть отрицательным: