Файл: Z9411_КафкаРС_ИссОп_КР.docx

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

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

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

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

КАФЕДРА 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

---