Контрольная работа по транспорту на тему Задачи с графиками

Решение
Построим область допустимых решений, т.е. решим графически систему неравенств. Для этого построим каждую прямую и определим полуплоскости, заданные неравенствами (полуплоскости обозначены штрихом).
1) Построим уравнение -2x1+x2 = 2 по двум точкам. Для нахождения первой точки приравниваем x1 = 0. Находим x2 = 2. Для нахождения второй точки приравниваем x2 = 0. Находим x1 = -1. Соединяем точку (0;2) с (-1;0) прямой линией. Определим полуплоскость, задаваемую неравенством. Выбрав точку (0; 0), определим знак неравенства в полуплоскости -2 * 0 + 1 * 0 - 2 ≤ 0, т.е. -2x1+x2 - 2≤ 0 в полуплоскости ниже прямой.
2) Построим уравнение x1-3x2 = -9 по двум точкам. Для нахождения первой точки приравниваем x1 = 0. Находим x2 = 3. Для нахождения второй точки приравниваем x2 = 0. Находим x1 = -9. Соединяем точку (0;3) с (-9;0) прямой линией. Определим полуплоскость, задаваемую неравенством. Выбрав точку (0; 0), определим знак неравенства в полуплоскости 1 * 0 - 3 * 0 + 9 ≥ 0, т.е. x1-3x2 + 9 ≥ 0 в полуплоскости ниже прямой.
3) Построим уравнение 4x1+3x2 = 24 по двум точкам. Для нахождения первой точки приравниваем x1 = 0. Находим x2 = 8. Для нахождения второй точки приравниваем x2 = 0. Находим x1 = 6. Соединяем точку (0;8) с (6;0) прямой линией. Определим полуплоскость, задаваемую неравенством. Выбрав точку (0; 0), определим знак неравенства в полуплоскости 4 * 0 + 3 * 0 - 24 ≤ 0, т.е. 4x1+3x2 – 24 ≤ 0 в полуплоскости ниже прямой. Пересечением полуплоскостей будет являться область, координаты точек которого удовлетворяют условию неравенствам системы ограничений задачи.
Обозначим границы области многоугольника решений.

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

Рисунок 3 – Решение задачи
Прямая F(x) = const пересекает область в точке D. Так как точка D получена в результате пересечения прямых (2) и (3), то ее координаты удовлетворяют уравнениям этих прямых:
x1-3x2=-9
4x1+3x2=24
Решив систему уравнений, получим: x1 = 3, x2 = 4
Откуда найдем максимальное значение целевой функции:
F(x) = 2*3 + 3*4 = 18
 
2. Решить следующие задачи линейного программирования с n переменными:
а) графическим методом;
б) методом искусственного базиса.


Решение
Решение задачи графическим методом
Так как число переменных в задаче равно 4, в исходной постановке задача графическим методом не решается.
Сведем эту задачу к задаче с двумя переменными. Рассмотрим систему ограничений задачи:

Выразим какие-либо две переменные задачи через остальные две переменные.
{█(x_3=-3x_1-2x_2+18@x_4=x_1-x_2+4)┤
Нашли искомые выражения. Подставляем их в целевую функцию:
Z(X)=2x_1+8x_2+3(-3x_1-2x_2+18)+4(x_1-x_2+4)=-3x_1-2x_2+70
Так как по условию задачи x_3,x_4>0 получаем ограничения:
{█(x_3=-3x_1-2x_2+18≥0@x_4=x_1-x_2+4≥0)┤
Приходим к задаче линейного программирования с двумя переменными:
Z(X)=-3x_1-2x_2+70→min
{█(-3x_1-2x_2≥-18@x_1-x_2≥-4)┤
x_1,x_2>0
Решаем данную задачу графическим методом. Строим область допустимых решений в плоскости, ограниченную неравенствами

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

Рисунок 5 – Решение
Прямая F(x) = const пересекает область в точке B. Так как точка B получена в результате пересечения прямых (1) и (3), то ее координаты удовлетворяют уравнениям этих прямых:
-3x1-2x2=-18
x1=0
Решив систему уравнений, получим: x1 = 0, x2 = 9
Откуда найдем минимальное значение целевой функции: F(x) = -3*0 - 2*9 + 70 = 52
Решение задачи методом искусственного базиса
Выразим базисные переменные через остальные:
x4 = x1-x2+4
x3 = -3x1-2x2+18
Подставим их в целевую функцию:
F(X) = 2x1+8x2+3(-3x1-2x2+18)+4(x1-x2+4) или F(X) = -3x1-2x2+70
-x1+x2+x4=4
3x1+2x2+x3=18
При вычислениях значение Fc = 70 временно не учитываем.
Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:
A = -1 1 0 1
3 2 1 0


Базисные переменные - это переменные, которые входят только в одно уравнение системы ограничений и притом с единичным коэффициентом.
Базисное решение называется допустимым, если оно неотрицательно.