Геометрический метод. 
Исследования и проектирования систем на базе ЭВМ

Необходимо найти минимальное значение целевой функции F = x1+x2 > min, при системе ограничений:

• 2x1+x2?6 (1)
• 7x1+8×2?56 (2)

x1+2×2?6 (3)

x1+x2?0 (4)

x1?0 (5)

x2?0 (6)

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

Построим уравнение 2×1+x2 = 6 по двум точкам. Для нахождения первой точки приравниваем x1 = 0. Находим x2 = 6. Для нахождения второй точки приравниваем x2 = 0. Находим x1 = 3. Соединяем точку (0;6) с (3;0) прямой линией.

Построим уравнение 7×1+8×2 = 56 по двум точкам. Для нахождения первой точки приравниваем x1 = 0. Находим x2 = 7. Для нахождения второй точки приравниваем x2 = 0. Находим x1 = 8. Соединяем точку (0;7) с (8;0) прямой линией.

Построим уравнение x1+2×2 = 6 по двум точкам. Для нахождения первой точки приравниваем x1 = 0. Находим x2 = 3. Для нахождения второй точки приравниваем x2 = 0. Находим x1 = 6. Соединяем точку (0;3) с (6;0) прямой линией.

Построим уравнение x1+x2 = 0 по двум точкам. Для нахождения первой точки приравниваем x1 = 1. Находим x2 = -1. Для нахождения второй точки приравниваем x2 = 1. Находим x1 = -1. Соединяем точку (1;-1) с (-1;1) прямой линией.

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

Обозначим границы области многоугольника решений.

Рассмотрим целевую функцию задачи F = x1+x2 > min.

Построим прямую, отвечающую значению функции F = 0: F = x1+x2 = 0. Вектор-градиент, составленный из коэффициентов целевой функции, указывает направление минимизации F (X). Начало вектора — точка (0; 0), конец — точка (1; 1). Будем двигать эту прямую параллельным образом. Поскольку нас интересует минимальное решение, поэтому двигаем прямую до первого касания обозначенной области. На графике эта прямая обозначена пунктирной линией.

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

Прямая F (x) = const пересекает область в точке A. Так как точка A получена в результате пересечения прямых (2) и (6), то ее координаты удовлетворяют уравнениям этих прямых:

7x1+8×2=56.

x1=0.

Решив систему уравнений, получим: x1 = 0, x2 = 7.

Откуда найдем минимальное значение целевой функции:

F (X) = 1*0 + 1*7 = 7.

3. Транспортная задача Постановка задачи:

Математическая модель транспортной задачи:

F = ??c_ijx_ij, (1).

при условиях:

• ?x_ij = a_i, i = 1,2,…, m, (2)
• ?x_ij = b_j, j = 1,2,…, n, (3)

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

Проверим необходимое и достаточное условие разрешимости задачи.

• ?a = 200 + 270 + 130 = 600
• ?b = 80 + 80 + 60 + 80 = 300

Как видно, суммарная потребность груза в пунктах назначения превышает запасы груза на базах. Следовательно, модель исходной транспортной задачи является открытой. Чтобы получить закрытую модель, введем дополнительную (фиктивную) базу с запасом груза, равным 300 (600—300). Тарифы перевозки единицы груза из базы во все магазины полагаем равны нулю.

Занесем исходные данные в распределительную таблицу.

1. Используя метод наименьшей стоимости, построим первый опорный план транспортной задачи.

Суть метода заключается в том, что из всей таблицы стоимостей выбирают наименьшую, и в клетку, которая ей соответствует, помещают меньшее из чисел a_i, или b_j.

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

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

Искомый элемент равен 1.

Для этого элемента запасы равны 270, потребности 80. Поскольку минимальным является 80, то вычитаем его.

x₂₂ = min (270,80) = 80.

Искомый элемент равен 2.

Для этого элемента запасы равны 200, потребности 80. Поскольку минимальным является 80, то вычитаем его.

x₁₁ = min (200,80) = 80.

Искомый элемент равен 4.

Для этого элемента запасы равны 130, потребности 60. Поскольку минимальным является 60, то вычитаем его.

x₃₃ = min (130,60) = 60.

Искомый элемент равен 9.

Для этого элемента запасы равны 120, потребности 80. Поскольку минимальным является 80, то вычитаем его.

x₁₄ = min (120,80) = 80.

Искомый элемент равен 0.

Для этого элемента запасы равны 40, потребности 300. Поскольку минимальным является 40, то вычитаем его.

x₁₅ = min (40,300) = 40.

Искомый элемент равен 0.

Для этого элемента запасы равны 190, потребности 260. Поскольку минимальным является 190, то вычитаем его.