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

Требуется: Найти оптимальный (по критерию максимума доходов) план загрузки судна.

Порядок выполнения:

1. Составить математическую модель задачи.

2. Построить многоугольник допустимых решений.

3. Найти оптимальное решение:

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

- построением иперемещением линии уровня целевой функции.

4. Проверить ограничение задачи.

5. Сравнить полученные решение в заданиях 1 и 2 и сделать выводы.

Вариант	Регистров. Грузоподъёмность Судна	Объём перевозок	Удельные Погрузочные объёмы	Время погрузки одной тонны груза	Наличие груза в порту	Плановое время погрузки судна	Доходная ставка
			0.45	1.3	0.9	2.3

Решение:

1) Составим математическую модель. Пусть количество первого груза (т.) по условию Плановое время погрузки судна 40 часов (2400 минут), при этом время погрузки 1 т., первого груза 0,9 мин/т., второго 2,3 мин/т. , далее объем трюмов судна = 2150 , а удельные погрузочные объемы грузов: первого груза 0,45 , второго 1,3 , а так же следуя из того что грузоподъёмность судна равна 2100 т., а имеем в наличии первого груза 1110 т., второго 3000 т. . Теперь введем целевую функцию – по критерию max доходов, которая составляет , то есть получаем целевую функцию и систему ограничений:. .

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

При

При

Или

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

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

3)

а) При

При

При

б) Рассмотрим целевую функцию задачи F = 140x₁+150x₂ → max.
Построим прямую, отвечающую значению функции F = 0: F = 140x₁+150x₂ = 0. Будем двигать эту прямую параллельным образом. Поскольку нас интересует максимальное решение, поэтому двигаем прямую до последнего касания обозначенной области. На графике эта прямая обозначена пунктирной линией.

Равный масштаб

Область допустимых решений представляет собой треугольник.

Прямая F(x) = const пересекает область в точке C. Так как точка C получена в результате пересечения прямых (4) и (1), то ее координаты удовлетворяют уравнениям этих прямых:
x₂=0
1110x₁+3000x₂≤2100

Решив систему уравнений, получим: x₁ = 1.89, x₂ = 0
Откуда найдем максимальное значение целевой функции:

4) Проверим ограничение задачи.

Составим двойственную задачу к прямой задаче.

Решение двойственной задачи дает оптимальную систему оценок ресурсов.
Для решения двойственной задачи используем вторую теорему двойственности.
Подставим оптимальный план прямой задачи в систему ограниченной математической модели:
1110*1.89 + 3000*0 = 2100 = 2100
1-ое ограничение прямой задачи выполняется как равенство. Это означает, что 1-ый ресурс полностью используется в оптимальном плане, является дефицитным и его оценка согласно второй теореме двойственности отлична от нуля (y₁>0).
0.45*1.89 + 1.3*0 = 0.85 < 2150
2-ое ограничение выполняется как строгое неравенство, т.е. ресурс 2-го вида израсходован не полностью. Значит, этот ресурс не является дефицитным и его оценка в оптимальном плане y₂ = 0
0.9*1.89 + 2.3*0 = 1.7 < 2400
3-ое ограничение выполняется как строгое неравенство, т.е. ресурс 3-го вида израсходован не полностью. Значит, этот ресурс не является дефицитным и его оценка в оптимальном плане y₃ = 0
С учетом найденных оценок, новая система примет вид:

Решая систему графическим способом, находим оптимальный план двойственной задачи:

Область допустимых решений представляет собой многоугольник.

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

Решив систему уравнений, получим: x₁ = 0.1261, x₂ = 0
Откуда найдем минимальное значение целевой функции:
F(X) = 2100*0.1261 + 0*0 = 264.86
Поскольку функция цели F(x) параллельна прямой (1), то на отрезке AA функция F(x) будет принимает одно и тоже минимальное значение.
Для определения координат точки A решим систему двух линейных уравнений:
x₂=0
1110x₁≥140

Решив систему уравнений, получим: x₁ = 0.1261, x₂ = 0
Откуда найдем минимальное значение целевой функции:
F(X) = 2100*0.1261 + 0*0 = 264.86
y₁ = 0.13
Z(Y) = 2100*0.13 = 264.86
Таким образом, отличную от нуля двойственные оценки имеют лишь те виды ресурсов, которые полностью используются в оптимальном плане. Поэтому двойственные оценки определяют дефицитность ресурсов.

Дата добавления: 2015-04-29