Балансовый метод планирования
Ответ: Fmах = 7840 ед. стоимости; хопт = (905; 0; 50; 0; 0; 0; 1390; 165).
Для получения прибыли равной 7840 ед. стоимости необходимо включить в план продукцию первого и третьего вида в количествах:
В1 = 905 ед.;
В3 = 50 ед.,
При этом остались недоиспользованные ресурсы в количествах:
А3 = 1390 ед.
А4 = 165 ед.
Задача 3
Для откорма группы животных на ферме необходимо наличие в ежедневном рационе не менее как В1, единиц питательных веществ В2 и т.д. – не менее как Вm. Указанные питательные вещества содержатся в n разных кормовых продуктах, которые можно закупить.
Составить такой ежедневный кормовой рацион, при котором будет удовлетворена потребность в питательных и затраты на откорм будут минимальны.
Питательные вещества | Кормовые продукты |
Суточная необходимость Вi = В0 + n1 |
|||
В1 | В2 | В3 | В4 | ||
А1 | 1 | 2 | 2 | 1 | 64 + 9 |
А2 | 0 | 3 | 1 | 1 | 39 + 9 |
А3 | 2 | 1 | 0 | 3 | 35 + 9 |
Стоимость 1 кг кормов | 2 | 1 | 3 | 4 |
Составить математическую модель и решить ЗЛП.
Решение
Введем переменные:
х1 – количество кормового продукта В1
х2 – количество кормового продукта В2
х3 – количество кормового продукта В3
х4 – количество кормового продукта В4
Строим математическую модель:
Fmах = 2х1 + х2 + 3х3 + 4х4
при условиях:
х1 + 2х2 + 2х3 + х4 ≥ 155;
3х2 + х3 + х4 ≥ 130;
2х1 + х2 + 3х4 ≥ 126;
хj ≥ 0; j = 1,4.
Приведем систему ограничений к каноническому виду:
х1 + 2х2 + 2х3 + х4 – х5 = 155;
3х2 + х3 + х4 – х6 = 130;
2х1 + х2 + 3х4 – х7 = 126;
хj ≥ 0; j = 1,7.
Приведем систему ограничений к виду удобному для решения:
х1 + 2х2 + 2х3 + х4 – х5 + х8 = 155;
3х2 + х3 + х4 – х6 + х9 = 130;
2х1 + х2 + 3х4 – х7 + х10 = 126;
хj ≥ 0; j = 1,10.
Переменные х8, х9, х10 являются искусственными и они введены на знак «=», поэтому для корректировки задачи эти переменные вводят в целевую функцию с коэффициентом +М.
Fmin = 2х1 + х2 + 3х3 + 4х4 + Мх8 + Мх9 + Мх10.
Задача решается модифицированным симплекс-методом (метод искусственного базиса).
№ о/п |
Ба- зис |
С | bi | С1=2 | С2=1 | С3=3 | С4=4 | С5=0 | С6=0 | С7=0 | С8=М | С9=М | С10=М |
Х1 | Х2 | Х3 | Х4 | Х5 | Х6 | Х7 | Х8 | Х9 | Х10 | ||||
х8 | М | 155 | 1 | 2 | 2 | 1 | -1 | 0 | 0 | 1 | 0 | 0 | |
х9 | М | 130 | 0 | <3> | 1 | 1 | 0 | -1 | 0 | 0 | 1 | 0 | |
х10 | М | 126 | 2 | 1 | 0 | 3 | 0 | 0 | -1 | 0 | 0 | 1 | |
Fj - Сj | 0 | -2 | -1 | -3 | -4 | 0 | 0 | 0 | 0 | 0 | 0 | ||
М | 411 | 3 | 6 | 3 | 5 | -1 | -1 | -1 | 0 | 0 | 0 | ||
х8 | М | 1 | 0 | 4/3 | 1/3 | -1 | 2/3 | 0 | 1 | 0 | |||
х2 | 1 | 0 | 1 | 1/3 | 1/3 | 0 | -1/3 | 0 | 0 | 0 | |||
х10 | 0 | <2> | 0 | -1/3 | 8/3 | 0 | 1/3 | -1 | 0 | 1 | |||
Fj - Сj | -2 | 0 | -8/3 |
- |
0 | -1/3 | 0 | 0 | 0 | ||||
М | 151 | 3 | 0 | 1 | 3 | -1 | 1 | -1 | 0 | 0 | |||
х8 | М | 27 | 0 | 0 |
<> |
-1 | -1 | 1/2 | 1/2 | 1 | |||
х2 | 1 | 0 | 1 | 1/3 | 1/3 | 0 | -1/3 | 0 | 0 | ||||
х1 | 2 | 1 | 0 | -1/6 | 4/3 | 0 | 1/6 | -1/2 | 0 | ||||
Fj - Сj | 126 | 0 | 0 | -3 | -1 | 0 | 0 | -1 | 0 | ||||
М | 27 | 0 | 0 | 3/2 | -1 | -1 | 1/2 | 1/2 | 0 | ||||
х3 | 3 | 18 | 0 | 0 | 1 | -2/3 | -2/3 |
1/3 |
<1/3> | ||||
х2 | 1 | 0 | 1 | 0 | 5/9 | 2/9 | -4/9 | -1/9 | |||||
х1 | 2 | 1 | 0 | 0 | 11/9 | -1/9 | 2/9 | -4/9 | |||||
Fj - Сj | 180 | 0 | 0 | 0 | -3 | -2 | 1 | 0 | |||||
х6 | 0 | 54 | 0 | 0 | 3 | -2 | -2 | 1 | 1 | ||||
х2 | 1 | 0 | 1 | 4/3 | -1/3 | -2/3 | 0 | 1/3 | |||||
х1 | 2 | 1 | 0 | -2/3 | 5/3 | 1/3 | 0 | -2/3 | |||||
Fj - Сj | 126 | 0 | 0 | -3 | -1 | 0 | 0 | -1 |
Каждый опорный план проверяем на оптимальность.
В 5-м опорном плане в индексной строке все разности Fj - Сj ≤ 0, следовательно этот план является оптимальным (F→min).
Можно записать ответ:
Fmin = 126 ед.стоимости,
Хопт = (97/3 = 32,33; 184/3 = 61,33; 0; 0; 0; 54).
Для получения минимальной себестоимости на изготовление кормовой продукции равной 126 ед. ст. необходимо включить в план кормовые продукты 1-го В1 = 32,33 ед. и второго вида В2 = 61,33 ед. и остались недоиспользованы ресурсы по А3 в количестве 54 ед.
Задача 4
С четырех карьеров к трем керамическим заводам перевозят глину.
Карьеры | Керамические заводы |
Мощность карьера Вj = Воj + n |
||
В1 | В2 | В3 | ||
А1 | 15 | 6 | 12 | 45 + 9 |
А2 | 4 | 6 | 8 | 38 + 9 |
А3 | 24 | 21 | 5 | 23 + 9 |
А4 | 12 | 9 | 12 | 84 |
Вj + Воj + n | 70 + 9 | 65 + 9 | 55 + 9 | 190 + 3*9 |
Сделать математическую постановку задачи и спланировать перевозку глины на керамические заводы так, чтобы транспортные затраты были минимальны.
Решение
Данная задача относится к типу транспортных задач линейного программирования и её математическая модель в сокращенной форме записи будет выглядеть так:
m n
Smin = Σ Σ Cij Хij,
i=1 j=1
при условиях по ресурсам:
n
Σ хij = Аi,, i = 1,m
j=1
m
Σ хij = Вj, j = 1,n
i=1
хij ≥ 0; i = 1,m; j = 1,n.
Существует два вида моделей:
m n
закрытая Σ Аi = Σ Вj;
i=1 j=1
m n
открытая Σ Аi ≠ Σ Вj.
i=1 j=1
Если в условии задачи дана открытая модель, то её нужно привести к закрытой, путем введения фиктивного поставщика или потребителя с нулевыми стоимостями перевозок, но ноль считается как максимально большое число. Закрытую модель можно решить методом потенциалов.
Проверяем в данной задаче тип модели:
Σ Аi = 217; Σ Вj = 217.
Строим первый опорный план по правилу минимального элемента:
Поставщики | Потребители | U | ||
В1 = 79 | В2 = 74 | В3 = 64 | ||
А1 = 54 |
15 32- ρ |
6 22 + ρ |
12 | U1 = 0 |
А2 = 47 |
4 47 |
6 | 8 | U2 = -11 |
А3 = 32 | 24 | 21 |
5 32 |
U3 = -4 |
А4 = 84 |
12 +ρ |
9 52-ρ |
12 32 |
U4 = 3 |
V | V1 = 15 | V2 = 6 | V3 = 9 | Smin = 1812 |
Далее делается проверка системы ограничений:
n m =
Σ хij = Аi,, Σ хij = Вj,
j=1 i=1
убеждаемся, что все ресурсы распределены и потребители удовлетворены максимальным образом.
Проверяем план на вырожденность: количество заполненных клеток должно быть равно: m + n – 1 = 4 + 3 – 1 = 6.
Считаем стоимость перевозок:
Smin = 15*32 + 6*22 + 4*47 + 5*92 + 9*52 + 12*32 = 1812.
Так как неизвестно, является ли этот план оптимальным, т.е. стоимость перевозок = 1812 ед.ст. или её можно уменьшить, то проверим каждую свободную клетку на оптимальность, а для этого необходимо найти потенциалы U и V, они находятся для заполненных клеток по формуле:
Сij = Ui + Vj, хij > 0.
После чего проверяем свободные клетки на оптимальность по формуле:
Sij = Сij – (Ui + Vj) ≥ 0.
Оказалось, что одна клетка не оптимальна S41 = -6.
Ставим в эту клетку +ρ – это величина для перераспределения ресурсов. От этой клетки строим цикл пересчета – это многоугольник любой конфигурации с прямыми циклами, расположенными в заполненных клетках. По углам этого цикла (прямоугольника) ставим +ρ и –ρ, чтобы был баланс по строкам и столбцам.
Определяем величину перераспределения груза (ресурсов):
ρ = min {32;52} = 32.
Строим новый опорный план:
Поставщики | Потребители | U | ||
В1 = 79 | В2 = 74 | В3 = 64 | ||
А1 = 54 |
15 |
6 54 |
12 | U1 = 0 |
А2 = 47 |
4 47 |
6 | 8 | U2 = -5 |
А3 = 32 | 24 | 21 |
5 32 |
U3 = -4 |
А4 = 84 |
12 32 |
9 20 |
12 32 |
U4 = 3 |
V | V1 = 9 | V2 = 6 | V3 = 9 | Smin = 1620 |
и весь алгоритм повторяется снова:
Smin 2 = 6*54 + 4*47 + 5*32 + 12*32 + 9*20 + 12*32 = 324 + 188 + 160 + 384 +180+ + 384 = 1620.
Все Sij ≥ 0, следовательно 2-й опорный план является оптимальным.
Ответ: минимальная стоимость перевозок равна 1620 ед. стоимости.
Поставки глины: х12 = 54 т; х21 = 47 т; х33 = 32 т; х41 = 32 т; х42 = 20 т; х43 = 32 т.
Список литературы
1. Акулич И.Л. Математическое программирование в примерах и задачах. – М.: Высшая школа, 1986.
2. Архангельский Ю.С., Коваленко И.И. Межотраслевой баланс. – К.: Выща шк. Головное изд-во, 1988.
3. Ашманов С.А. Введение в математическую экономику. – М.: Наука, 1984.
4. Вентцель Е.С. Исследование операций: Задачи, принципы, методология. – М.: Наука, 1980
5. Вивальнюк Л.М. Елементи лінійного програмування. – К.: Вища школа, 1975.
6. Гейл Д. Теория линейных экономических моделей. – М.: ИЛ, 1963.
7. Гольштейн Е.Г., Юдин Д.Б. Линейное программирование (теория, методы и приложения). – М.: Наука, 1969.
8. Данциг Дж. Линейное программирование, его обобщения и приложения. – М.: Прогресс, 1966.
9. Деордица Ю.С., Нефедов Ю.М. Исследование операцій в планировании и управлении. – К.: Вища школа, 1991.
10. Ефимов Н.В. Квадратичные формы и матрицы. – М.: Наука, 1972.
11. Зайченко Ю.П. Исследование операций. – К.: Вища школа, 1979.
12. Исследование операций. / Под ред. Н.С. Кремера. – М.: Бизнес и банки, ЮНИТИ, 1997.
13. Кузнецов Ю.Н. и др. Математическое программирование. – М.: Высшая школа, 1980.
14. Карпелевич Ф.М., Садовский Л.Е. Математическое программми-рование. – И.: Наука, 1967.
15. Лотов А.В. Введение в экономико-математическое моделирование. – М.: Наука, 1984.
16. Математика в экономике: Учебник: в 2-х ч. Ч.1/ А.С. Солодовников, В.А. Бабайцев, А.В. Браилов, И.Г. Шандра. – 2-е изд., перераб. и доп. – М.: Финансы и статистика, 2006.
17. Математические методы и модели в планировании и управлении. Сборник задач. К.: Вища школа, 1985.
18. Терехов Л.Л., Куценко В.А.Ж, Сиднев С.П. Экономико-математические методы и модели в планировании и управлении. – К.: Вища школа, 1984.