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

Если задача линейного программирования содержит только две переменные, то ее можно решить геометрическим (графоаналитическим) методом. Этот метод основан на следующих положениях.

I. Областью решений неравенства является полуплоскость, расположенная выше или ниже прямой, описываемой уравнением .

Если задана система линейных неравенств с двумя переменными:

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

Заметим, что область решений системы неравенств может быть и неограниченной; и пустой, когда система неравенств противоречива.

Пример 1. Найти область решений неравенства

.

Построим прямую

 

 

на плоскости оху. Для этого найдем точки пересечения прямой с осями: имеем при ; при .

Решением уравнения являются точки, принадлежащие этой прямой. Теперь рассмотрим строгое неравенство

.

Для того чтобы выяснить, какая полуплоскость служит областью решения этого неравенства, решим его относительно переменной у:

.

Отсюда следует, что областью решения неравенства является полуплоскость, расположенная ниже прямой (показано штрихами вниз).

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

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

Каким образом найти эту точку покажем на примере 2.

Пример 2. Определить экстремумы функции

при системе ограничений:

Решение.

В системе координат построим прямые соответствующие уравнениям.

Найдем область решения каждого неравенства.

Многоугольник АВСDЕ, образованный пересечением всех полуплоскостей, образует область допустимых решений системы неравенств.

Далее на этой же плоскости построим вектор .

Координаты вектора равны коэффициентам при переменных в целевой функции . Полагая F=0, построим соответствующую прямую или .

Будем перемещать эту прямую параллельно самой себе в направлении вектора (т.е. снизу вверх) до тех пор, пока прямая не выйдет из ОДР. Зафиксируем ту вершину многоугольника АВСDЕ, через которую F = 0 выходит из ОДР. Такой вершиной является С.

Определим ее координаты. Для этого решим систему уравнений двух прямых, на пересечении которых находится точка С

Подставим координаты т. С (2; 4) в уравнение целевой функции F. Вычислим значение .

Чтобы определить минимум целевой функции F будем перемещать прямую F=0 параллельно самой себе в направлении противоположном вектору . Зафиксируем ту вершину многоугольника АВСDЕ, через которую F=0 выходит из ОДР. Такой вершиной является точка А(1; 2). Подставим ее координаты (1; 2) в уравнение целевой функции F и найдем .

.

Транспортная задача (ТЗ)

Простейшими ТЗ являются задачи о перевозках некоторого однородного груза из пунктов отправления в пункты назначения, или от поставщиков к потребителям, при обеспечении минимальных затрат на перевозки. Как правило, начальные условия таких задач записываются в таблицу. Для m поставщиков и n потребителей таблица имеет вид:

 

Мощность поставщиков	Спрос потребителей
N1	N2	---	Nn
	c11 x11	c12 x12	---	c1n x1n
	c21 x21	c22 x22	---	c2n x2n
---	---	---	---	---
	cm1 xm1	cm2 xm2	---	cmn xmn

Показатели c _ij означают затраты на перевозку единицы груза от i -го поставщика к j -му потребителю (i = 1; 2;...; m; j = 1; 2;...; n);

M_i - мощность (предложение) i - го поставщика;

N_j - спрос j - го потребителя;

x_ij - поставка (количество груза), от i -го поставщика к j -му потребителю.

Суммарные затраты на перевозку всего груза выражаются целевой функцией

Если суммарная мощность поставщиков (предложение) равна суммарному спросу потребителей, то соответствующая модель ТЗ называется закрытой.

,

Если , то модель ТЗ называется открытой.

 

Алгоритм решения ТЗ

1. Определяют модель ТЗ.

Если модель ТЗ открытая, то в случае

(объем мощностей поставщиков превышает объем спроса потребителей) вводят фиктивного потребителя ФN со спросом равным разности

Если (объем спроса потребителей превышает объем мощностей поставщиков), то вводят фиктивного поставщика ФМ с мощностью равной разности

Затраты на перевозки к ФN или ФМ считают равными нулю (или произвольными, но одинаковыми).

2. Составляют первоначальный план распределения поставок по методу «северо-западного угла» или методу учета наименьших затрат.

При этом должно быть заполнено клеток.

Если число заполненных клеток окажется меньше этого числа, то недостающее число свободных клеток заполняют нулевыми поставками.

3. Полученное распределение поставок оценивают методом потенциалов.

При этом если все оценки клеток окажутся неотрицательные, то полученное распределение является оптимальным.

Тогда подсчитывают суммарные затраты на перевозки.

Если хотя бы одна оценка клетки окажется отрицательной, то полученное распределение не является оптимальным.

4. Для получения нового, улучшенного распределения поставок нужно построить цикл для клетки, которая имеет наибольшую по абсолютной величине отрицательную оценку. По циклу перемещают наименьшую поставку среди четных клеток цикла. В результате перераспределения поставок клетка, для которой строился цикл, получает поставку, а четная клетка, которой соответствовала наименьшая поставка, освобождается.

5. Полученное распределение поставок опять проверяют на оптимальность методом потенциалов.

6. Процесс улучшения распределения поставок продолжают до тех пор, пока получат оптимальное распределение поставок. Признаком оптимального распределения поставок служит наличие неотрицательных оценок всех клеток этого распределения.

7. Если среди оценок клеток последнего оптимального распределения есть хотя бы одна нулевая для свободной клетки, то оптимальное распределение поставок не является единственным.

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

Первоначальное распределение поставок методом «Северо–западного угла»

Заполнение начинается с первой верхней клетки (1.1), спускаясь ступеньками по диагонали вниз.

Сначала заполняют клетку (1.1): . Если M₁ не полностью использована в (1.1), то заполняют клетку (1.2): и так далее пока не будет полностью использована мощность M₁. Оставшиеся незаполненные клетки в первой строке мысленно вычеркиваются. Затем переходят ступенькой к распределению мощности M₂ по второй горизонтали и так далее пока не дойдут до клетки в m -й строке.

После распределения поставок необходимо сделать проверку условий:

1) - весь объем продукции у поставщиков должен быть вывезен;

2) - все заказы удовлетворены;

3) - имеем закрытую модель ТЗ;

4) количество заполненных поставками клеток должно равняться , где m – число строк, n – число столбцов.

Пример 3. Распределить поставки по методу «Северо – западного угла» в транспортной задаче: - вектор поставщиков,

- вектор потребителей,

- матрица тарифов.

Решение.

1. Составим таблицу.

Потребители   Поставщики	В1	В2	В3	В4
А1 – 70			-	-
А2 – 80	-			-
А3 – 50	-	-

2. Распределим поставки по методу «Северо–западного угла».

Для этого в клетку (1; 1) запишем груз . Так как спрос потребителя В₁ выполнен, мысленно вычеркиваем клетки (2; 1) и (3;1). У первого поставщика осталось 20 единиц груза. В клетку (1; 2) запишем груз . Так как мощность первого поставщика выбрана вся, то клетки (1; 3) и (1; 4) мысленно вычеркиваем. Переходим на вторую горизонталь. Спрос второго потребителя не удовлетворен. В клетку (2; 2) запишем груз . Так как спрос второго потребителя выполнен, то мысленно вычеркнем клетку (3; 2). У второго поставщика осталось еще 30 единиц груза. В клетку (2; 3) запишем груз . Так как мощность второго поставщика выбрана полностью, то мысленно вычеркнем клетку (2; 4). Переходим на третью горизонталь. Спрос третьего потребителя не удовлетворен. В клетку (3; 3) запишем поставку: . Спрос третьего потребителя удовлетворен. Мысленно вычеркиваются клетки в третьем столбце под клеткой (3; 3). У третьего поставщика осталось 40 единиц груза. Четвертому потребителю требуется 40 единиц груза. В клетку (3; 4) запишем поставку . Спрос четвертого потребителя удовлетворен. Мысленно вычеркиваются клетки в четвертом столбце после клетки (3; 4). Вся мощность третьего потребителя выбрана – мысленно вычеркиваются клетки в третьей строке после клетки (3; 4).

Распределение поставок закончили. Сделаем проверку баланса по строкам и столбцам. Подсчитаем количество заполненных клеток .

Получили опорный план:

Вычислим суммарные затраты всех поставок: