СОДЕРЖАНИЕ
Задача № 1
Задача № 2
Задача № 3
Задача № 4
Задача № 5
СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ
Задача №1
Решить задачу графически:
F = + → max,
Найти максимальное
значение целевой функции F = + → max,
при системе ограничений:
≥ 0,
≥ 0,
1) Построим область
допустимых решений, т.е. решим графически
систему неравенств. Для этого построим
каждую прямую и определим полуплоскости,
заданные неравенствами (полуплоскости
обозначены штрихом).
Построим уравнение +≤21 по двум точкам.
Для нахождения первой точки приравниваем
x1 = 0. Находим x2 = 3. Для нахождения
второй точки приравниваем x2 = 0. Находим x1 = 10.5. Соединяем точку
(0;3) с (10.5;0) прямой линией. Определим полуплоскость,
задаваемую неравенством. Выбрав точку
(0; 0), определим знак неравенства в полуплоскости:
2 * 0 + 7 * 0 - 21 ≤ 0, т.е. 2x1+7x2 - 21≤ 0 в полуплоскости
ниже прямой.
Построим уравнение
7+≤ 49 по двум
точкам. Для нахождения первой точки приравниваем
x1 = 0. Находим x2 = 24.5. Для нахождения
второй точки приравниваем x2 = 0. Находим x1 = 7. Соединяем точку
(0;24.5) с (7;0) прямой линией. Определим полуплоскость,
задаваемую неравенством. Выбрав точку
(0; 0), определим знак неравенства в полуплоскости:
7 * 0 + 2 * 0 - 49 ≤ 0, т.е.
7x1+2x2 – 49 ≤ 0 в полуплоскости
ниже прямой.
2) Границы области
допустимых решений.
Пересечением полуплоскостей
будет являться область, координаты точек
которого удовлетворяют условию неравенствам
системы ограничений задачи.
Обозначим границы
области многоугольника решений.
3) Рассмотрим целевую
функцию задачи F = + → max.
Построим прямую, отвечающую
значению функции F = 0: F = 4x+7 = 0. Вектор-градиент,
составленный из коэффициентов целевой
функции, указывает направление максимизации
F(X). Начало вектора – точка (0; 0), конец
– точка (4; 7). Будем двигать эту прямую
параллельным образом. Поскольку нас интересует
максимальное решение, поэтому двигаем
прямую до последнего касания обозначенной
области. На графике эта прямая обозначена
пунктирной линией.
Прямая F(x) = const пересекает область
в точке C. Так как точка C получена в результате
пересечения прямых (1) и (2), то ее координаты
удовлетворяют уравнениям этих прямых:
+=21
+=49
Решив систему уравнений,
получим: x = 6.6889, y = 1.0889
Откуда найдем максимальное
значение целевой функции:
F(X) = 4 х 6.6889 + 7 х 1.0889
= 34.3778
Задача № 2
Для производства
4-х видов продукции используется 3 вида
сырья. Нормы расхода сырья (кг) запасы
(кг) его ценность от реализации единицы
продукции заданы таблицей.
Составим план выпуска продукции,
обеспечивающий получение максимальной
прибыли, используя симплексный метод,
а также построить двойственную задачу
и решить ее симплекс-методом.
Норма расхода ресурсов на
единицу изделия
| |
Изд 1 |
Изд 2 |
Изд 3 |
Изд 4 |
Запас ресурсов |
Ресурс 1 |
5 |
10 |
15 |
20 |
150 |
Ресурс 2 |
20 |
15 |
10 |
5 |
170 |
Ресурс 3 |
15 |
9 |
4 |
17 |
190 |
Ценность |
6,5 |
8 |
14 |
10 |
|
F(X) = 6,5x1 + 8x2 + 14x3 + 10x4 → max при ограничениях:
5x1 + 10x2 + 15x3 + 20x4≥150
20x1 + 15x2 + 10x3 + 5x4≥170
15x1 + 9x2 + 4x3 + 17x4≥190
x1 ≥ 0, x2 ≥ 0, x3 ≥ 0, x4 ≥ 0
F(X) =6,5x1 + 8x2 + 14x3 + 10x4
В 1-м неравенстве смысла
(≥) вводим базисную переменную x5 со знаком минус. В
2-м неравенстве смысла (≥) вводим базисную
переменную x6 со знаком минус. В
3-м неравенстве смысла (≥) вводим базисную
переменную x7 со знаком минус.
5x1 + 10x2 + 15x3 + 20x4-1x5 + 0x6 + 0x7 = 150
20x1 + 15x2 + 10x3 + 5x4 + 0x5-1x6 + 0x7 = 170
15x1 + 9x2 + 4x3 + 17x4 + 0x5 + 0x6-1x7 = 190
Переход к СЗЛП.
Расширенная матрица
системы ограничений данной задачи:
5 |
10 |
15 |
20 |
-1 |
0 |
0 |
150 |
20 |
15 |
10 |
5 |
0 |
-1 |
0 |
170 |
15 |
9 |
4 |
17 |
0 |
0 |
-1 |
190 |
Приводим систему неравенств
к следующему виду:
- 5x1 - 10x2 - 15x3 - 20x4 ≤ -150
- 20x1 - 15x2 - 10x3 - 5x4 ≤ -170
- 15x1 - 9x2 - 4x3 - 17x4 ≤ -190
F(X) = 6,5x1 + 8x2 + 14x3 + 10x4 → max
Упростим систему.
- 5x1 - 10x2 - 15x3 - 20x4 ≤ -150
- 20x1 - 15x2 - 10x3 - 5x4 ≤ -170
- 15x1 - 9x2 - 4x3 - 17x4 ≤ -190
F(X) = 13x1 + 16x2 + 28x3 + 20x4 → max
Если далее решать
систему (симплекс-методом), то полученное
значение целевой функции необходимо
будет разделить на 2
Решим прямую задачу
линейного программирования симплекс-методом.
Поскольку в правой
части присутствуют отрицательные значения,
умножим соответствующие строки на (-1).
Определим максимальное значение целевой
функции F(X) = 13x1 + 16x2 + 28x3 + 20x4 при следующих условиях
- ограничений.
5x1 + 10x2 + 15x3 + 20x4≥150
20x1 + 15x2 + 10x3 + 5x4≥170
15x1 + 9x2 + 4x3 + 17x4≥190
Для построения первого
опорного плана систему неравенств приведем
к системе уравнений путем введения дополнительных
переменных (переход к канонической форме).
В 1-м неравенстве смысла
(≥) вводим базисную переменную x5 со знаком минус. В
2-м неравенстве смысла (≥) вводим базисную
переменную x6 со знаком минус. В
3-м неравенстве смысла (≥) вводим базисную
переменную x7 со знаком минус.
5x1 + 10x2 + 15x3 + 20x4-1x5 + 0x6 + 0x7 = 150
20x1 + 15x2 + 10x3 + 5x4 + 0x5-1x6 + 0x7 = 170
15x1 + 9x2 + 4x3 + 17x4 + 0x5 + 0x6-1x7 = 190
Последняя строка содержит
отрицательные элементы. Пространство
допустимых решений неограниченно. Решения
не существует.
Задача №3
Четыре
предприятия данного экономического района
для производства продукции использует
три вида сырья. Потребности в сырье каждого
из предприятий соответственно равны b1, b2, b3
и b4 ед. Сырье сосредоточено в трех
местах его получения, а запасы соответственно
равны a1, a2, a3 ед. На каждое из предприятий сырье
может завозиться из любого пункта его
получения. Тарифы перевозок являются
известными величинами и задаются матрицей
С =
Составить такой план перевозок,
при котором общая себестоимость перевозок
является минимальной. Задачу решить методом
потенциалов.
| |
В1 |
В2 |
В3 |
В4 |
|
А 1 |
7 |
12 |
4 |
6 |
150 |
А 2 |
5 |
6 |
3 |
4 |
130 |
А 3 |
13 |
8 |
7 |
3 |
160 |
| |
120 |
80 |
80 |
70 |
|
1)Проверка на сбалансированность
Общее число запасов на складах 440
Мы видим, что общее число запасов
превышает общую потребность на 90 |
9 |
Задача является открытой
(несбалансированной), для приведения ее
к закрытой введем фиктивного потребителя №5
С потребностью
в продукции равной 90
Все издержки по доставке
продукции данному потребителю с любого
склада принимаем равными нулю.
2) Отыскание начального
решения. Метод минимального элемента
Запишем настоящую задачу в
виде транспортной таблицы. В верхней
строке перечислим потребности потребителей
по порядку номеров. В левом столбце перечислим
имеющиеся запасы на складах. На пересечении
j-го столбца и i-й строки будем записывать
количество продукции, поставляемое с
i-го склада j-му потребителю. Пока начальное
решение не найдено, оставим эти клетки
пустыми. В правом нижнем углу каждой клетки,
зеленым цветом, отобразим соответствующие
издержки.
| |
= 120 |
= 80 |
80 |
= 70 |
= 90 |
= 150 |
|
|
|
|
|
= 130 |
|
|
|
|
|
= 160 |
|
|
|
|
|
Введем вспомогательные строку и столбец,
в которых будем отмечать оставшиеся нераспределенные
запасы и соответственно потребности
(остатки). Изначально их содержимое равно
исходным запасам и потребностям, так
как еще ничего не распределялось. На рисунке
они представлены желтым цветом.
Выберем клетку в которую будем распределять
продукцию на следующей итерации, это
клетка содержащая минимальное значение
издержек(минимальный элемент). На рисунке
как сама клетка так и соответствующие
ей остатки отображаются красным шрифтом.
| |
= 120 |
= 80 |
80 |
= 70 |
= 90 |
|
= 150 |
|
|
|
|
Х 0 |
150 |
= 130 |
|
|
|
|
|
130 |
= 160 |
|
|
|
|
|
160 |
| |
120 |
80 |
80 |
70 |
90 |
|