МИНИСТЕРСТВО НАУКИ И ВЫСШЕГО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ

федеральное государственное автономное образовательное учреждение высшего образования

«САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ АЭРОКОСМИЧЕСКОГО ПРИБОРОСТРОЕНИЯ»

ИНСТИТУТ НЕПРЕРЫВНОГО И ДИСТАНЦИОННОГО ОБРАЗОВАНИЯ

КАФЕДРА 41

ОЦЕНКА

ПРЕПОДАВАТЕЛЬ

старший преподаватель				Н. Н. Григорьева
должность, уч. степень, звание		подпись, дата		инициалы, фамилия

КОНТРОЛЬНАЯ РАБОТА

Индивидуальные задания для 9-го варианта

по дисциплине: Исследование операций

РАБОТУ ВЫПОЛНИЛ

СТУДЕНТ ГР. №	Z9411				Р. С. Кафка
	номер группы		подпись, дата		инициалы, фамилия
Студенческий билет №	2019/3603

Шифр ИНДО

Санкт-Петербург 2023

Вариант 9

Раздел 2 Линейное программирование

1 Решите задачу линейного программирования графическим методом и симплекс-методом

Решение:

Графический метод

Шаг №1. Построим область допустимых решений, т.е. решим графически систему неравенств. Для этого построим каждую прямую и определим полуплоскости, заданные неравенствами (полуплоскости обозначены штрихом).

Шаг №2. Границы области допустимых решений.

Пересечением полуплоскостей будет являться область, координаты точек которого удовлетворяют условию неравенствам системы ограничений задачи.

Обозначим границы области многоугольника решений.

Шаг №3. Рассмотрим целевую функцию задачи F = 3x1+x2 → max.

Построим прямую, отвечающую значению функции F = 3x1+x2 = 0. Вектор-градиент, составленный из коэффициентов целевой функции, указывает направление максимизации F(X). Начало вектора – точка (0; 0), конец – точка (3;1). Будем двигать эту прямую параллельным образом. Поскольку нас интересует максимальное решение, поэтому двигаем прямую до последнего касания обозначенной области. На графике эта прямая обозначена пунктирной линией.

Прямая F(x) = const пересекает область в точке B. Так как точка B получена в результате пересечения прямых (1) и (3), то ее координаты удовлетворяют уравнениям этих прямых:

x1+x2=5

x1-x2=1

Решив систему уравнений, получим: x1 = 3, x2 = 2

Откуда найдем максимальное значение целевой функции:

F(x) = 3*3 + 1*2 = 11

Симплекс-Метод

В 1-м неравенстве смысла (≤) вводим базисную переменную y1. В 2-м неравенстве смысла (≥) вводим базисную переменную y2 со знаком минус. В 3-м неравенстве смысла (≤) вводим базисную переменную y3.

Оптимальный план можно записать так:

2 Составьте опорный план транспортной задачи методом Фогеля и оцените его стоимость.

	B1	B2	B3	B4	ai
A1	5	5	3	4	40
A2	6	7	6	5	50
A3	4	3	4	5	35
A4	3	5	7	6	70
bj	48	65	32	50	195

Решение

Используя метод Фогеля, построим первый опорный план транспортной задачи. Суть метода заключается в том, что из всей таблицы стоимостей выбирают наименьшую, и в клетку, которая ей соответствует, помещают меньшее из чисел a_i, или b_j. Затем, из рассмотрения исключают либо строку, соответствующую поставщику, запасы которого полностью израсходованы, либо столбец, соответствующий потребителю, потребности которого полностью удовлетворены, либо и строку и столбец, если израсходованы запасы поставщика и удовлетворены потребности потребителя. Из оставшейся части таблицы стоимостей снова выбирают наименьшую стоимость, и процесс распределения запасов продолжают, пока все запасы не будут распределены, а потребности удовлетворены.

Искомый элемент равен c₁₃=3. Для этого элемента запасы равны 40, потребности 32. Поскольку минимальным является 32, то вычитаем его. x₁₃ = min(40,32) = 32.

	B1	B2	B3	B4	ai
A1	5	5	3	4	40-32=8
A2	6	7	x	5	50
A3	4	3	x	5	35
A4	3	5	x	6	70
bj	48	65	32-32=0	50

Искомый элемент равен c₃₂=3. Для этого элемента запасы равны 35, потребности 65. Поскольку минимальным является 35, то вычитаем его. x₃₂ = min(35,65) = 35.

	B1	B2	B3	B4	ai
A1	5	5	3	4	8
A2	6	7	x	5	50
A3	x	3	x	x	35-35=0
A4	3	5	x	6	70
bj	48	65-35=30	0	50

Искомый элемент равен c₄₁=3. Для этого элемента запасы равны 70, потребности 48. Поскольку минимальным является 48, то вычитаем его. x₄₁ = min(70,48) = 48.

	B1	B2	B3	B4	ai
A1	x	5	3	4	8
A2	x	7	x	5	50
A3	x	3	x	x	0
A4	3	5	x	6	70-48=22
bj	48-48=0	30	0	50

Искомый элемент равен c₁₄=4. Для этого элемента запасы равны 8, потребности 50. Поскольку минимальным является 8, то вычитаем его. x₁₄ = min(8,50) = 8.

	B1	B2	B3	B4	ai
A1	x	x	3	4	8-8=0
A2	x	7	x	5	50
A3	x	3	x	x	0
A4	3	5	x	6	22
bj	0	30	0	50-8=42

Искомый элемент равен c₂₄=5. Для этого элемента запасы равны 50, потребности 42. Поскольку минимальным является 42, то вычитаем его. x₂₄ = min(50,42) = 42.

	B1	B2	B3	B4	ai
A1	x	x	3	4	0
A2	x	7	x	5	50-42=8
A3	x	3	x	x	0
A4	3	5	x	x	22
bj	0	30	0	42-42=0

Искомый элемент равен c₄₂=5. Для этого элемента запасы равны 22, потребности 30. Поскольку минимальным является 22, то вычитаем его. x₄₂ = min(22,30) = 22.

	B1	B2	B3	B4	ai
A1	x	x	3	4	0
A2	x	7	x	5	8
A3	x	3	x	x	0
A4	3	5	x	x	22-22=0
bj	0	30-22=8	0	0

Искомый элемент равен c₂₂=7. Для этого элемента запасы равны 8, потребности 8. Поскольку минимальным является 8, то вычитаем его. x₂₂ = min(8,8) = 8.

	B1	B2	B3	B4	ai
A1	x	x	3	4	0
A2	x	7	x	5	8-8=0
A3	x	3	x	x	0
A4	3	5	x	x	0
bj	0	8-8=0	0	0

	B1	B2	B3	B4	ai
A1	5	5	3[32]	4[8]	40
A2	6	7[8]	6	5[42]	50
A3	4	3[35]	4	5	35
A4	3[48]	5[22]	7	6	70
bj	48	65	32	50	195

В результате получен первый опорный план, который является допустимым, так как все грузы из баз вывезены, потребность магазинов удовлетворена, а план соответствует системе ограничений транспортной задачи.

Значение целевой функции для этого опорного плана равно: Lф = 3*32 + 4*8 + 7*8 + 5*42 + 3*35 + 3*48 + 5*22 = 753 (единиц)

3 Составьте опорный план транспортной задачи из задачи 2 методом северо-западного угла, а затем оптимизируйте план распределительным методом (поиск циклов с отрицательной ценой) Проверьте правильность решения задач данного раздела в MS Еxcel.

	B1	B2	B3	B4	ai
A1	5	5	3	4	40
A2	6	7	6	5	50
A3	4	3	4	5	35
A4	3	5	7	6	70
bj	48	65	32	50	195

Решение:

1. Используя метод северо-западного угла, построим первый опорный план транспортной задачи. План начинается заполняться с верхнего левого угла. Искомый элемент равен c₁₁=5. Для этого элемента запасы равны 40, потребности 48. Поскольку минимальным является 40, то вычитаем его. x₁₁ = min(40,48) = 40.

	B1	B2	B3	B4	ai
A1	5	x	x	x	40-40=0
A2	6	7	6	5	50
A3	4	3	4	5	35
A4	3	5	7	6	70
bj	48-20=8	65	32	50

Искомый элемент равен c₂₁=6. Для этого элемента запасы равны 50, потребности 8. Поскольку минимальным является 8, то вычитаем его. x₂₁ = min(50,8) = 8.

	B1	B2	B3	B4	ai
A1	5	x	x	x	0
A2	6	7	6	5	50-8=42
A3	x	3	4	5	35
A4	x	5	7	6	70
bj	8-8=0	65	32	50

Искомый элемент равен c₂₂=7. Для этого элемента запасы равны 42, потребности 65. Поскольку минимальным является 42, то вычитаем его. x₂₂ = min(42,65) = 42.

	B1	B2	B3	B4	ai
A1	5	x	x	x	0
A2	6	7	x	x	42-42=0
A3	x	3	4	5	35
A4	x	5	7	6	70
bj	0	65-42=23	32	50

Искомый элемент равен c₃₂=3. Для этого элемента запасы равны 35, потребности 23. Поскольку минимальным является 23, то вычитаем его. x₃₂ = min(35,23) = 23.

	B1	B2	B3	B4	ai
A1	5	x	x	x	0
A2	6	7	x	x	0
A3	x	3	4	5	35-23=12
A4	x	x	7	6	70
bj	0	23-23=0	32	50

Искомый элемент равен c₃₃=4. Для этого элемента запасы равны 12, потребности 32. Поскольку минимальным является 12, то вычитаем его. x₃₃ = min(12,32) = 12.

	B1	B2	B3	B4	ai
A1	5	x	x	x	0
A2	6	7	x	x	0
A3	x	3	4	x	12-12=0
A4	x	x	7	6	70
bj	0	0	32-12=20	50

Искомый элемент равен c₄₃=7. Для этого элемента запасы равны 70, потребности 20. Поскольку минимальным является 20, то вычитаем его. x₄₃ = min(70,20) = 20.

	B1	B2	B3	B4	ai
A1	5	x	x	x	0
A2	6	7	x	x	0
A3	x	3	4	x	0
A4	x	x	7	6	70-20=50
bj	0	0	20-20=0	50

Искомый элемент равен c₄₄=6. Для этого элемента запасы равны 50, потребности 50. Поскольку минимальным является 50, то вычитаем его. x₄₄ = min(50,50) = 50.

	B1	B2	B3	B4	ai
A1	5	x	x	x	0
A2	6	7	x	x	0
A3	x	3	4	x	0
A4	x	x	7	6	50-50=0
bj	0	0	0	50-50=0

	B1	B2	B3	B4	ai
A1	5[40]	5	3	4	40
A2	6[8]	7[42]	6	5	50
A3	4	3[23]	4[12]	5	35
A4	3	5	7[20]	6[50]	70
bj	48	65	32	50	195

В результате получен первый опорный план, который является допустимым, так как все грузы из баз вывезены, потребность магазинов удовлетворена, а план соответствует системе ограничений транспортной задачи.

Значение целевой функции для этого опорного плана равно: Lф = 5*40 + 6*8 + 7*42 + 3*23 + 4*12 + 7*20 + 6*50 = 1099

Этап II. Улучшение опорного плана. Проверка опорного плана на оптимальность. Чтобы установить является ли опорный план оптимальным, надо проверить, как повлияет на величину целевой функции любое возможное перераспределение поставок. План распределения поставок будет оптимальным лишь в том случае, когда целевая функция имеет минимальное значение, т.е. когда дальнейшее уменьшение затрат на поставку будет невозможно. Проверим возможность уменьшения суммарных затрат на поставку продукции. С этой целью для каждой свободной от поставки клетки определяется величина Δ_ij, характеризующая изменение суммарных затрат на поставку (в расчете на единицу перераспределяемой продукции), при условии включения в план единичной поставки х_ij=1 от поставщика А_i к потребителю В_j. При этом должно быть произведено такое изменение остальных поставок, чтобы получившаяся совокупность поставок не нарушала баланса спроса и поставок транспортной задачи. Величина Δ_ij называется оценкой свободной клетки (или характеристика). В исходном решении задачи имеются клетки свободные от поставок. Необходимо вычислить значение оценок Δ_ij для этих свободных от поставок клеток. С этой целью для каждой свободной клетки составляется означенный цикл перерасчета (или замкнутая цепь, круг, кольцо, контур и т.д.). Под циклом пересчета (цепью) понимается замкнутая ломаная линия. Вершинами цикла (цепи) являются клетки таблицы, проще – вершины лежат в клетках таблицы. Причем одна из вершин находится в свободной от поставки клетке, в той, для которой определяется оценка Δ_ij. Все другие вершины находятся в базисных клетках, т.е. клетках, занятых поставками. Вершины, в которых поставки при перераспределении увеличиваются, отмечаются плюсом и называются положительными вершинами и, наоборот, вершины, в которых поставки при перераспределении уменьшаются отмечаются минусом и называются отрицательными вершинами. В цикле знаки по вершинам расставляют начиная с вершины, лежащей в свободной клетке, для которой определяется Δ_ij. В нее записывают знак плюс, затем знаки по вершинам чередуются: минус, плюс , минус, плюс и т. д., независимо от того, расставляют ли их по часовой стрелке или в обратном направлении. Таким образом, в цикле всегда насчитывается одинаковое число положительных и отрицательных вершин. Следующий этап решения транспортной задачи заключается в улучшении опорного плана. Если при каком-то опорном плане оказывается несколько свободных клеток с отрицательными оценками Δ_ij, то за один переход к лучшему плану можно занять поставкой только одну клетку – ту, которая обеспечивает наибольшее снижение целевой функции.

(1;1): В свободную клетку (1;1) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

	B1	B2	B3	B4	ai
A1	5[+]	5[8][-]	3[32]	4	40
A2	6	7[22][+]	6	5[28][-]	50
A3	4	3[35]	4	5	35
A4	3[48][-]	5	7	6[22][+]	70
bj	48	65	32	50	195

Цикл приведен в таблице (1,1 → 1,2 → 2,2 → 2,4 → 4,4 → 4,1). Оценка свободной клетки равна Δ₁₁ = (5) - (5) + (7) - (5) + (6) - (3) = 5. (1;4): В свободную клетку (1;4) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

	B1	B2	B3	B4	ai
A1	5	5[8][-]	3[32]	4[+]	40
A2	6	7[22][+]	6	5[28][-]	50
A3	4	3[35]	4	5	35
A4	3[48]	5	7	6[22]	70
bj	48	65	32	50	195

Цикл приведен в таблице (1,4 → 1,2 → 2,2 → 2,4). Оценка свободной клетки равна Δ₁₄ = (4) - (5) + (7) - (5) = 1. (2;1): В свободную клетку (2;1) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

	B1	B2	B3	B4	ai
A1	5	5[8]	3[32]	4	40
A2	6[+]	7[22]	6	5[28][-]	50
A3	4	3[35]	4	5	35
A4	3[48][-]	5	7	6[22][+]	70
bj	48	65	32	50	195

Цикл приведен в таблице (2,1 → 2,4 → 4,4 → 4,1). Оценка свободной клетки равна Δ₂₁ = (6) - (5) + (6) - (3) = 4. (2;3): В свободную клетку (2;3) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

	B1	B2	B3	B4	ai
A1	5	5[8][+]	3[32][-]	4	40
A2	6	7[22][-]	6[+]	5[28]	50
A3	4	3[35]	4	5	35
A4	3[48]	5	7	6[22]	70
bj	48	65	32	50	195

Цикл приведен в таблице (2,3 → 2,2 → 1,2 → 1,3). Оценка свободной клетки равна Δ₂₃ = (6) - (7) + (5) - (3) = 1. (3;1): В свободную клетку (3;1) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

	B1	B2	B3	B4	ai
A1	5	5[8]	3[32]	4	40
A2	6	7[22][+]	6	5[28][-]	50
A3	4[+]	3[35][-]	4	5	35
A4	3[48][-]	5	7	6[22][+]	70
bj	48	65	32	50	195

Цикл приведен в таблице (3,1 → 3,2 → 2,2 → 2,4 → 4,4 → 4,1). Оценка свободной клетки равна Δ₃₁ = (4) - (3) + (7) - (5) + (6) - (3) = 6. (3;3): В свободную клетку (3;3) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

	B1	B2	B3	B4	ai
A1	5	5[8][+]	3[32][-]	4	40
A2	6	7[22]	6	5[28]	50
A3	4	3[35][-]	4[+]	5	35
A4	3[48]	5	7	6[22]	70
bj	48	65	32	50	195

Цикл приведен в таблице (3,3 → 3,2 → 1,2 → 1,3). Оценка свободной клетки равна Δ₃₃ = (4) - (3) + (5) - (3) = 3. (3;4): В свободную клетку (3;4) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

	B1	B2	B3	B4	ai
A1	5	5[8]	3[32]	4	40
A2	6	7[22][+]	6	5[28][-]	50
A3	4	3[35][-]	4	5[+]	35
A4	3[48]	5	7	6[22]	70
bj	48	65	32	50	195

Цикл приведен в таблице (3,4 → 3,2 → 2,2 → 2,4). Оценка свободной клетки равна Δ₃₄ = (5) - (3) + (7) - (5) = 4. (4;2): В свободную клетку (4;2) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

	B1	B2	B3	B4	ai
A1	5	5[8]	3[32]	4	40
A2	6	7[22][-]	6	5[28][+]	50
A3	4	3[35]	4	5	35
A4	3[48]	5[+]	7	6[22][-]	70
bj	48	65	32	50	195

Цикл приведен в таблице (4,2 → 4,4 → 2,4 → 2,2). Оценка свободной клетки равна Δ₄₂ = (5) - (6) + (5) - (7) = -3. (4;3): В свободную клетку (4;3) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

	B1	B2	B3	B4	ai
A1	5	5[8][+]	3[32][-]	4	40
A2	6	7[22][-]	6	5[28][+]	50
A3	4	3[35]	4	5	35
A4	3[48]	5[+]	7[+]	6[22][-]	70
bj	48	65	32	50	195

Цикл приведен в таблице (4,3 → 4,4 → 2,4 → 2,2 → 1,2 → 1,3). Оценка свободной клетки равна Δ₄₃ = (7) - (6) + (5) - (7) + (5) - (3) = 1. Опорный план является неоптимальным, поскольку имеются отрицательные оценки клеток (4,2;) равные: (-3).

Переход от неоптимального опорного плана к лучшему. Поскольку в исходном опорном плане рассматриваемой задачи свободная клетка (4;2) имеет отрицательную оценку, то для получения плана, обеспечивающего меньшее значение целевой функции, эту клетку следует занять возможно большей поставкой, не нарушающей при этом условий допустимости плана. Из грузов х_ij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (4, 4) = 22. Прибавляем 22 к объемам грузов, стоящих в плюсовых клетках и вычитаем 22 из Х_ij, стоящих в минусовых клетках. В результате получим новый опорный план.

	B1	B2	B3	B4	ai
A1	5	5[8]	3[32]	4	40
A2	6	7[0]	6	5[50]	50
A3	4	3[35]	4	5	35
A4	3[48]	5[22]	7	6	70
bj	48	65	32	50	195

Минимальные затраты составят:

Lф = 5*8 + 3*32 + 5*50 + 3*35 + 3*48 + 5*22 = 745

Анализ оптимального плана. Из 1-го склада необходимо груз направить в 2-й магазин (8 ед.), в 3-й магазин (32 ед.) Из 2-го склада необходимо весь груз направить в 4-й магазин. Из 3-го склада необходимо весь груз направить в 2-й магазин. Из 4-го склада необходимо груз направить в 1-й магазин (48 ед.), в 2-й магазин (22 ед.)

Проверка в Excel: