Математическое программирование — страница 3

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

неизвестных в целевую функцию; ответы должны совпасть. 5. Геометрическая интерпретация ЗЛП и графический метод решения (при двух неизвестных) Система ограничений ЗЛП геометрически представляет собой многоугольник или многоугольную область как пересечение полуплоскостей - геометрических образов неравенств системы. Целевая функция f = c1x1 + c2x2 геометрически изображает семейство параллельных прямых, перпендикулярных вектору n

(с1,с2). Теорема. При перемещении прямой целевой функции направлении вектора n значения целевой функции возрастают, в противоположном направлении - убывают. На этих утверждениях основан графический метод решения ЗЛП. 6. Алгоритм графического метода решения ЗЛП. 1)  В системе координат построить прямые по уравнениям, соответствующим каждому неравенству системы ограничений; 2)  найти полуплоскости решения каждого неравенства

системы (обозначить стрелками); 3)  найти многоугольник (многоугольную область) решений системы ограничений как пересечение полуплоскостей; 4)  построить вектор n (с1,с2) по коэффициентам целевой функции f = c1x1 + c2x2; 5)  в семействе параллельных прямых целевой функции выделить одну, например, через начало координат; 6)  перемещать прямую целевой функции параллельно самой себе по области решения, достигая max f при движении

вектора n и min f при движении в противоположном направлении. 7)  найти координаты точек max и min по чертежу и вычислить значения функции в этих точках (ответы). 7. Постановка транспортной задачи. Приведем экономическую формулировку транспортной задачи по критерию стоимости: Однородный груз, имеющийся в m пунктах отправления (производства) А1, А2, ..., Аm соответственно в количествах а1, а2, ..., аm единиц, требуется доставить в каждый из n

пунктов назначения (потребления) В1, В2, ..., Вn соответственно в количествах b1, b2, ..., bn единиц. Стоимость перевозки (тариф) единицы продукта из Ai в Bj известна для всех маршрутов AiBj и равна Cij (i=1,m; j=1,n). Требуется составить такой план перевозок, при котором весь груз из пунктов отправления вывозиться и запросы всех пунктов потребления удовлетворяются (закрытая модель), а суммарные транспортные расходы минимальны. Условия задачи удобно