Практикум по решению линейных задач математического программирования
(2; 3)
1
+ 3 – 5 = –1
0;
(2; 4)
1
+ 1 – 8 = –6
0;
(2; 5)
1
– 4 – 0 = –4
0;
(3; 1)
4
+ 1 – 6 = –1
0;
(3; 2)
4
+ 2 – 8 = –2
0;
(3; 3)
4
+ 3 – 7 = 0
0;
(3; 4)
4
+ 1 – 10 = –5
0;
(4; 1)
4
+ 1 – 5 = 0
0;
(4; 4)
4
+ 1 – 2 = 3
0.
Т.к. среди свободных клеток есть такие, в которых второе условие оптимальности не выполняется, то план не оптимален.
Осуществим переход к нехудшему опорному плану. Наиболее перспективная для заполнения клетка (4; 4), т. к. ей соответствует наибольшая положительная оценка
4
+ 1 – 2 = 3.
Найдем цикл перераспределения груза для этой клетки.
Выбранной для заполнения клетке присваиваем знак «+», далее знаки чередуем. Среди вершин со знаком «–» выбираем наименьшую поставку.
–
объем перепоставки.
Перераспределим поставки по циклу, тем самым перейдем к новому опорному плану.
|
|
31 | 52 | 17 | 20 | 45 |
|
|||||
| 35 | 5 | 4 | 3 | 1 | 0 | 0 | |||||
| 17 | 18 | ||||||||||
| 40 | 2 | 3 | 5 | 8 | 0 | –2 | |||||
| 31 | 9 | ||||||||||
| 40 | 6 | 8 | 7 | 10 | 0 | 1 | |||||
| 40 | |||||||||||
| 50 | 5 | 6 | 7 | 2 | 0 | 1 | |||||
| 43 | 2 | 5 | |||||||||
|
|
4 | 5 | 3 | 1 | –1 | Таб.2 | |||||
Транспортные
затраты, соответствующие
опорному плану:
(ден.
ед.).
Исследуем
опорный план
на оптимальность.
Найдем значения
потенциалов,
используя
первое условие
оптимальности.
Для заполненных
поставками
клеток
.
,
,
,
,
,
,
,
,
.
Проверим
выполнение
второго условия
оптимальности.
Для всех пустых
клеток должно
выполняться
неравенство:
.
Выпишем клетки, в которых условие нарушено:
(1;
2)
0
+ 5 – 4 = 1
0.
Осуществим
переход к нехудшему
опорному плану.
Наиболее
перспективная
для заполнения
клетка (1; 2), т. к.
ей соответствует
положительная
оценка
1.
Найдем цикл
перераспределения
груза для этой
клетки.
–
объем перепоставки.
Число заполненных клеток распределительной таблицы 8 равно рангу матрицы задачи r = 8, следовательно, опорный план (таб. 3) является невырожденным.
|
|
31 | 52 | 17 | 20 | 45 |
|
|||||
| 35 | 5 | 4 | 3 | 1 | 0 | 0 | |||||
| 18 | 17 | ||||||||||
| 40 | 2 | 3 | 5 | 8 | 0 | –1 | |||||
| 31 | 9 | ||||||||||
| 40 | 6 | 8 | 7 | 10 | 0 | 2 | |||||
| 40 | |||||||||||
| 50 | 5 | 6 | 7 | 2 | 0 | 2 | |||||
| 25 | 20 | 5 | |||||||||
|
|
3 | 4 | 3 | 0 | –2 | Таб.3 | |||||
Транспортные затраты, соответствующие опорному плану:
(ден.
ед.).
Исследуем опорный план на оптимальность.
Найдем
значения потенциалов,
используя
первое условие
оптимальности.
Для заполненных
поставками
клеток
.
,
,
,
,
,
,
,
,
.
Проверим
выполнение
второго условия
оптимальности.
Для всех пустых
клеток должно
выполняться
неравенство:
.
Второе условие оптимальности выполняется для всех свободных клеток, следовательно, план оптимален.
Наименьшие
транспортные
затраты
.
Ответ:
;
оптимальный
план распределения
поставок расположен
в таб. 3.
Задания для самостоятельной работы.
Составить план перевозок с минимальными транспортными затратами.
| а) |
|
б) |
|
Решение оптимизационных задач с помощью Excel
При решении оптимизационных экономических задач необходимо пройти через следующие этапы:
Составить математическую модель экономической задачи;
Решить полученную экстремальную математическую задачу;
Дать экономическую интерпретацию ответу.
Рассмотрим прохождение этих этапов на примере задачи об использовании ресурсов.
Пример. Для изготовления изделий двух видов А и В на заводе используют сырье четырех типов (І, ІІ, ІІІ, IV). Для выпуска изделия А необходимо 2 единицы сырья І типа; 1 ед. сырья ІІ типа; 2 ед. сырья ІІІ типа; 1 ед. сырья IV типа. Для изготовления изделия В требуется 3 единицы сырья І типа; 1 ед. сырья ІІ типа; 1 ед. сырья ІІІ типа. Запасы сырья составляют: І типа – 21 ед., ІІ типа – 8 ед., ІІІ типа – 12 ед., IV типа – 5 ед. Выпуск одного изделия типа А приносит 3 грн. прибыли, а одного изделия типа В – 2 грн. прибыли. Составить план производства, обеспечивающий наибольшую прибыль.
Решение.
Составление математической модели.
Вопрос задачи, сформулированный в виде «составить план производства, обеспечивающий наибольшую прибыль», означает, что необходимо определить, какое количество изделий А и В нужно производить (для достижения наибольшей прибыли).
Так как необходимо определить количество изделий А и В, то введем следующие обозначения:
–
количество
изделий А,
планируемое
к выпуску;
–
количество
изделий В,
планируемое
к выпуску;
Z (целевая функция задачи) по своему экономическому смыслу – это прибыль. (Т.к. из условия задачи мы видим, что слово «наибольшая», связанное с экстремумом, соответствует прибыли).
Получим:
– математическая
модель задачи.
Решение полученной экстремальной задачи:
Для решения задачи воспользуемся возможностями Microsoft Excel.
Откройте Microsoft Excel.
В ячейки
первой строки
(в данном случае
А1 и В1) введите
обозначения
имеющихся в
задаче переменных
,
(язык и шрифт
значения не
имеют, т. к.
обозначения
необходимы
для понимания
смыслов соответствующих
им чисел).
В ячейки
второй строки
(в данном случае
А2 и В2), соответствующие
заполненным
ячейкам первой,
введите произвольные
значения переменных
(для простоты
возьмем значения
1, хотя на самом
деле это могут
быть любые
числа). Тем самым
мы присваиваем
и
пока значения
1.
В ячейку А4 введите обозначение целевой функции Z=.
В ячейку В4 введите формулу вычисления целевой функции из математической модели задачи
(
),
подставляя
вместо
и
,
соответствующие
им значения
из ячеек А2 и
В2. (Вспомните,
что введение
формулы начинается
со знака =)
После
нажатия кнопки
Enter на экране
монитора должно
быть следующее.
(Продумайте,
как изменится
картинка, если
ввести иные
значения
и
,
к примеру, не
1, а 2. А теперь
поэкспериментируйте.
Оправдался
ваш прогноз?)
В ячейки А5 и В5 введите соответственно слова: А5 – Ограничение, В5 – Правая часть ограничения.
В ячейку
А6 введите формулу
вычисления
левой части
первого ограничения
,
подставляя
вместо
и
,
соответствующие
им значения
из ячеек А2 и
В2.
В ячейку В6 введите свободный член первого ограничения – 21. После нажатия кнопки Enter на экране монитора должно быть следующее.
Аналогично
в ячейку А7 введите
формулу вычисления
левой части
второго ограничения
,
а в В7 его свободный
член – 8; в ячейку
А8 введите формулу
вычисления
левой части
третьего ограничения
,
а в В8 его свободный
член – 12; в ячейку
А9 введите формулу
вычисления
левой части
четвертого
ограничения
,
а в В9 его свободный
член – 5;
После нажатия кнопки Enter на экране монитора должно быть следующее.
Таким образом, мы ввели все данные условия задачи в компьютер и подготовились к тому, чтобы задачу решить.
В меню Сервис выберите команду Поиск решения (именно она является инструментом для поиска решений задач оптимизации)
В этой команде вам будет предложено установить целевую ячейку. Именно слово «целевую» поможет вам в дальнейшем вспомнить, о чем идет речь. Конечно же, о значении целевой функции. Введите это значение, щелкнув левой кнопкой мышки на ячейке В4 (содержащей в данном случае числовое значение целевой функции). Получите:
Т.к. в данной задаче функция Z исследуется на максимум, то оставляем Равной: • максимальному значению.
Если решаем задачу на минимум, то нужно поставить метку • перед словами минимальному значению.
Далее нажмите на стрелку, расположенную в правой части пространства ячейки Изменяя ячейки:, в результате чего на экране должно появиться следующее
В полученное
пространство
необходимо
ввести диапазон
изменяющихся
в задаче переменных
(т.е. ячейки,
содержащие
числовые значения
и
,
т. к. именно
и
могут принимать
различные
числовые значения,
среди которых
мы и пытаемся
отыскать оптимальное
решение задачи).
Т.е. заполненная ячейка должна принять вид:
После этого заполняют пространство ячейки Ограничения: Для чего нужно щелкнуть по кнопке Добавить, в результате чего на экране появится новое окно:
В Ссылка на ячейку: введите номер ячейки, содержащей левую часть ограничения (в данном случае для первого ограничения – это ячейка А6).
Выберите
знак ограничения
в соответствии
с математической
моделью из
предлагаемых
вариантов (в
данном случае
<=, т. к. первое
ограничение
со знаком
)
В Ограничение: введите номер ячейки, содержащей свободный член ограничения (в данном случае для первого ограничения – это ячейка В6).
Т.о. перед вами на экране должна быть следующая картинка:
Это вы ввели только первое ограничение, а есть еще и другие, поэтому нажмите кнопку Добавить и аналогичным образом введите второе, третье и четвертое ограничения.
Но после
того, как все
ограничения
системы введены,
еще рано нажимать
ОК, т. к. в
математической
модели имеется
условие неотрицательности
переменных
(
),
а в описании
задачи для
компьютера
оно еще не
упоминалось.
Поэтому
после введения
последнего
ограничения
вновь нажмите
кнопку Добавить
и в Ссылка на
ячейку: введите
номер ячейки,
содержащей
числовое значение
;
выберите знак
>=; а в Ограничение:
введите
0.
Еще раз
нажмите Добавить
и аналогичным
образом создайте
условие неотрицательности
для
.
Таким образом, компьютер получил все те ограничения, которые есть в условии задачи, поэтому теперь можно нажать ОК. В результате на экране появится следующее:
Появилось? Если ДА, то нажимайте Выполнить.
И согласитесь на то, чтобы Сохранить найденное решение. Т.е. в появившемся окне нажмите ОК.
Обратите
внимание на
то, какие теперь
значения принимают
,

