Практика
.pdf
Шаг №3. Рассмотрим целевую функцию задачи F = 3x1+4x2 → max.
Построим прямую, отвечающую значению функции F = 3x1+4x2 = 0. Вектор-градиент, составленный из коэффициентов целевой функции, указывает направление максимизации F(X). Начало вектора – точка (0; 0), конец – точка (3;4). Будем двигать эту прямую параллельным образом. Поскольку нас интересует максимальное решение, поэтому двигаем прямую до последнего касания обозначенной области. На графике эта прямая обозначена пунктирной линией.
Прямая F(x) = const пересекает область в точке C. Так как точка C получена в результате пересечения прямых (1) и (2), то ее координаты удовлетворяют уравнениям этих прямых:
x1+7x2=77
4x1+5x2=78
Решив систему уравнений, получим: x1 = 7, x2 = 10
Откуда найдем максимальное значение целевой функции:
F(X) = 3*7 + 4*10 = 61
Задача 25 (ОШИБКА в УСЛОВИИ)
Есть запасы однотипной продукции у поставщиков A1, A2, A3, A4. Существует потребность в этой продукции B1, B2, B3.
Стоимость доставки единицы продукции от поставщиков к потребителям представлена в таблице.
Поставщик |
Потребитель |
Запас |
Запас |
В1 |
В2 |
В2 |
|
А1 |
6 |
5 |
2 |
200 |
250 |
А2 |
3 |
7 |
4 |
100 |
100 |
А3 |
7 |
8 |
1 |
100 |
80 |
А4 |
2 |
2 |
3 |
150 |
120 |
Потребность |
150 |
150 |
250 |
|
|
Необходимо составить такой план перевозок, который бы удовлетворил все
потребности и имел минимальную стоимость.
Задача 26
Стоимость доставки единицы продукции от поставщика к потребителю располагается в правом нижнем углу ячейки.
|
|
Потребитель |
|
Запас |
|
|
|
|
|
|
|
|
В1 |
В2 |
В3 |
В4 |
|
|
|
|
|
|
|
А1 |
7 |
8 |
1 |
2 |
200 |
|
|
|
|
|
|
А2 |
4 |
5 |
9 |
8 |
180 |
|
|
|
|
|
|
А3 |
9 |
2 |
3 |
6 |
190 |
|
|
|
|
|
|
Потребность |
150 |
130 |
150 |
140 |
|
|
|
|
|
|
|
Требуется составить план перевозок, при котором общая стоимость доставки продукции будет наименьшей.
РЕШЕНИЕ:
Запишем экономико-математическую модель для нашей задачи.
Переменные:
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 ≤ 200 (для 1 базы) x21 + x22 + x23 + x24 ≤ 180 (для 2 базы) x31 + x32 + x33 + x34 ≤ 190 (для 3 базы)
Ограничения по потребностям:
x11 + x21 + x31 = 150 (для 1-го потребителя.) x12 + x22 + x32 = 130 (для 2-го потребителя.) x13 + x23 + x33 = 150 (для 3-го потребителя.) x14 + x24 + x34 = 140 (для 4-го потребителя.)
Целевая функция:
7x11 + 8x12 + 1x13 + 2x14 + 4x21 + 5x22 + 9x23 + 8x24 + 9x31 + 2x32 + 3x33 + 6x34 → min
Стоимость доставки единицы груза из каждого пункта отправления в соответствующие пункты назначения задана матрицей тарифов
|
1 |
2 |
3 |
4 |
Запасы |
1 |
7 |
8 |
1 |
2 |
200 |
2 |
4 |
5 |
9 |
8 |
180 |
3 |
9 |
2 |
3 |
6 |
190 |
Потребности |
150 |
130 |
150 |
140 |
|
Проверим необходимое и достаточное условие разрешимости задачи.
∑a = 200 + 180 + 190 = 570
∑b = 150 + 130 + 150 + 140 = 570
Условие баланса соблюдается. Запасы равны потребностям. Следовательно, модель транспортной задачи является закрытой.
Занесем исходные данные в распределительную таблицу.
|
1 |
2 |
3 |
4 |
Запасы |
1 |
7 |
8 |
1 |
2 |
200 |
2 |
4 |
5 |
9 |
8 |
180 |
3 |
9 |
2 |
3 |
6 |
190 |
Потребности |
150 |
130 |
150 |
140 |
|
Этап I. Поиск первого опорного плана.
1. Используя метод северо-западного угла, построим первый опорный план транспортной
задачи.
План начинается заполняться с верхнего левого угла.
Искомый элемент равен c11=7. Для этого элемента запасы равны 200, потребности 150. Поскольку минимальным является 150, то вычитаем его.
x11 = min(200,150) = 150.
7 |
8 |
1 |
2 |
200 - 150 = 50 |
x |
5 |
9 |
8 |
180 |
x |
2 |
3 |
6 |
190 |
150 - 150 = 0 |
130 |
150 |
140 |
|
Искомый элемент равен c12=8. Для этого элемента запасы равны 50, потребности 130. Поскольку минимальным является 50, то вычитаем его.
x12 = min(50,130) = 50.
7 |
8 |
x |
x |
50 - 50 = 0 |
x |
5 |
9 |
8 |
180 |
x |
2 |
3 |
6 |
190 |
0 |
130 - 50 = 80 |
150 |
140 |
|
Искомый элемент равен c22=5. Для этого элемента запасы равны 180, потребности 80. Поскольку минимальным является 80, то вычитаем его.
x22 = min(180,80) = 80.
7 |
8 |
x |
x |
0 |
x |
5 |
9 |
8 |
180 - 80 = 100 |
x |
x |
3 |
6 |
190 |
0 |
80 - 80 = 0 |
150 |
140 |
|
Искомый элемент равен c23=9. Для этого элемента запасы равны 100, потребности 150. Поскольку минимальным является 100, то вычитаем его.
x23 = min(100,150) = 100.
7 |
8 |
x |
x |
0 |
x |
5 |
9 |
x |
100 - 100 = 0 |
x |
x |
3 |
6 |
190 |
0 |
0 |
150 - 100 = 50 |
140 |
|
Искомый элемент равен c33=3. Для этого элемента запасы равны 190, потребности 50. Поскольку минимальным является 50, то вычитаем его.
x33 = min(190,50) = 50.
7 |
8 |
x |
x |
0 |
x |
5 |
9 |
x |
0 |
x |
x |
3 |
6 |
190 - 50 = 140 |
0 |
0 |
50 - 50 = 0 |
140 |
|
Искомый элемент равен c34=6. Для этого элемента запасы равны 140, потребности 140. Поскольку минимальным является 140, то вычитаем его.
x34 = min(140,140) = 140.
7 |
8 |
x |
x |
0 |
x |
5 |
9 |
x |
0 |
x |
x |
3 |
6 |
140 - 140 = 0 |
0 |
0 |
0 |
140 - 140 = 0 |
|
|
1 |
2 |
3 |
4 |
Запасы |
1 |
7[150] |
8[50] |
1 |
2 |
200 |
2 |
4 |
5[80] |
9[100] |
8 |
180 |
3 |
9 |
2 |
3[50] |
6[140] |
190 |
Потребности |
150 |
130 |
150 |
140 |
|
В результате получен первый опорный план, который является допустимым, так как все грузы из баз вывезены, потребность потребителей удовлетворена, а план соответствует системе ограничений транспортной задачи.
2. Подсчитаем число занятых клеток таблицы, их 6, а должно быть m + n - 1 = 6. Следовательно, опорный план является невырожденным.
Значение целевой функции для этого опорного плана равно:
F(x) = 7*150 + 8*50 + 5*80 + 9*100 + 3*50 + 6*140 = 3740
ОТВЕТ:
Анализ оптимального плана.
Из 1-го склада необходимо груз направить к 3-у потребителю (60), к 4-у потребителю (140)
Из 2-го склада необходимо груз направить к 1-у потребителю (150), к 2-у потребителю (30)
Из 3-го склада необходимо груз направить к 2-у потребителю (100), к 3-у потребителю (90)
Задача 27
Используя метод потенциалов найти оптимальный план перевозок. Стоимость доставки единицы груза из каждого пункта отправления в соответствующие пункты назначения задана матрицей.
|
1 |
2 |
3 |
4 |
Запасы |
1 |
1 |
2 |
4 |
3 |
6 |
2 |
4 |
3 |
8 |
5 |
8 |
3 |
2 |
7 |
6 |
3 |
10 |
Потребности |
4 |
6 |
8 |
8 |
|
РЕШЕНИЕ:
Запишем экономико-математическую модель для нашей задачи.
Переменные:
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 ≤ 6 (для 1 базы) x21 + x22 + x23 + x24 ≤ 8 (для 2 базы) x31 + x32 + x33 + x34 ≤ 10 (для 3 базы)
Ограничения по потребностям:
x11 + x21 + x31 = 4 (для 1-го потребителя.) x12 + x22 + x32 = 6 (для 2-го потребителя.) x13 + x23 + x33 = 8 (для 3-го потребителя.) x14 + x24 + x34 = 8 (для 4-го потребителя.)
Целевая функция:
1x11 + 2x12 + 4x13 + 3x14 + 4x21 + 3x22 + 8x23 + 5x24 + 2x31 + 7x32 + 6x33 + 3x34 → min
Стоимость доставки единицы груза из каждого пункта отправления в соответствующие пункты назначения задана матрицей тарифов
|
1 |
2 |
3 |
4 |
Запасы |
1 |
1 |
2 |
4 |
3 |
6 |
2 |
4 |
3 |
8 |
5 |
8 |
3 |
2 |
7 |
6 |
3 |
10 |