Геометрический метод решения ЗЛП.

Математическая модель экономических задач. Постановка ЗЛП.

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

Предприятию задан план производства продукции по времени и номенклатуре: требуется за время Т выпустить n₁, n₂, n_k единиц продукции P₁,P₂,P_k. Продукция производится на станках S₁,S₂,S_n. Для каждого станка известна производительность a_ij, т.е. число продукции P_j, которое можно произвести на станке S_i, и затраты bij на изготовление продукции Т_j на станке S_i единицу времени. Необходимо составить такой план работы станков, т.е. распределить выпуск продукции между станками, чтобы затраты на производство всей продукции были min.

Экономико-математическая модель задачи:

Обозначим x_ij – время в течение которого станок S_i будет занят изготовлением продукции P_j. Т.к. время работы каждого станка ограничено и не превышает Т, то справедливо неравенство:

x₁₁+x₁₂+…+x_1k≤T

x₂₁+x₂₂+…+x_2k≤T (1)

……………………

x_m1+x_m2+…+x_mk≤T

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

a₁₁x₁₁+ a₂₁x₂₁+…+ a_m1x_m1=n₁

a₁₂x₁₂+ a₂₂x₂₂+…+ a_m2x_m2=n₂ (2)

……………………………...

a_1kx_1k+ a_2kx_2k+…+ a_mkx_mk=n_k

 

Кроме того, xij≥0, (i=1,2,…,m; j=1,2,…,k) (3)

Затраты на производство всей продукции выразиться функцией:

F= b₁₁x₁₁+ b₁₂x₁₂+…+ b_mkx_mk (4)

Экономико-математическая модель задач об использовании мощностей.

Найти такое решение x=(x₁₁,x₁₂…,x_mk) удовлетворяющим системам (1), (2) и условию (3), при котором функция (4) принимает min значение.

Постановка ЗЛП.

Общая ЗЛП имеет вид:

a₁₁x₁+ a₁₂x₂+…+ a_1nx_n≤b₁

a₂₁x₁+ a₂₂x₂+…+ a_2nx_n≤b₂

…………………………..

a_m1x₁+ a_m2x₂+…+ a_mnx_n≤b_m

x₁≥0; x₂≥0;… x_n≥0

 

f= C₁X₁+C₂X₂+…+ C_nX_n→min(max)

Система неравенств называется системой ограничений, ее матрица имеет ранг r≤n, f – целевая функция. Неотрицательное решение (x₁⁰, x₂⁰,…, x_n⁰) системы неравенств называется допустимым решением – планом ЗЛП. Допустимое решение называется оптимальным, если оно обращает целевую функцию в min или max (оптимум).

Геометрический метод решения ЗЛП.

Множество допустимых решений (многогранник решений) ЗЛП представляет собой выпуклый многогранник (или выпуклую многогранную область). Выпуклая область – это такая область, у которой любая точка отрезка, концы которого лежат на границе области принадлежат этой области. Оптимальное решение задачи находится, по крайней мере, в одной из угловых точек многогранника решений. Рассмотрим задачу стандартной формы с двумя переменными (n=2). В такой форме можно привести к классическую задачу (с ограничениями, в виде уравнений, когда число переменных n больше числа уравнений m на 2, т.е. n-m=2). Пусть геометрическим изображением системы ограничений является многоугольник ABCDE (рис.1). Необходимо среди точек этого многоугольника найти такую точку, в которой линейная функция f= C₁X₁+C₂X₂ принимает max или min значение.

 

Рассмотрим линию уровня линейной функции f, т.е. линию вдоль которой это функция принимает одно и то же фиксированное значение, т.е. f=a, или C₁X₁+C₂X₂=a (1)

На многоугольнике решений следует найти точку через которую проходит линия уровня функции f с наиб. или наим. уровнем. Уравнение линии уровня функции (1) есть уравнение прямой линии. При различных уравнениях a, линия уровня параллельна, т.к. их угловые коэффициенты определяются только соотношением между коэффициентами C₁ и C₂ и следовательно равны. Т.о. линия уровня функции f – это своеобразные параллели, расположенные под каким-то углом к осям координат. Важное свойство линии уровня состоит в том, что при параллельном смещении в сторону градиента, уровень только возрастает, а при смещении в другую сторону только убывает. Это и есть свойство градиента. Одну линий уровня можно взять, проходящей через начало координат (если линейная функция имеет вид f= C₁X₁+C₂X₂, т.е. без свободного члена.), то это соответствует нулевому уровню.

Этапы решения задач.

1. Сначала на координатной плоскости X₁O X₂ строится допустимая многоугольная область, соответствующая ограничениям. Далее строится вектор градиент, координаты которого являются частными производными функции f. Вектор показывает направление возрастания линейной функции f, в какой-нибудь точке X₀, принадлежащей допустимой области.

2. Прямая f= C₁X₁+C₂X₂ перпендикулярно вектору-градиенту передвигается в направлении этого вектора, в случае максимизации f, до тех пор, пока не покинет многоугольной области. Предельная точка (или точки) области при этом движении и являются точкой max f.

3. Для нахождения координат точки max достаточно из соответствующих ограничений, и дающих пересечения точки max. Значение f, найденное в получаемой точке являются max. В случае минимизации f, прямую f= C₁X₁+C₂X₂, надо двигать в направлении, противоположному вектору-градиенту. Ясно, что, если прямая f= C₁X₁+C₂X₂ не покидает допустимой области, то соответствующий max или min f не существует.

 

4. Вопрос 4. Взаимодвойственные задачи ЛП. Основные теории двойственности. С каждой задачей ЛП связана некоторая другая задача ЛП, называемая двойственной по отношению к данной (исходной). Различают симметричную и несимметричную формы взаимодвойственных задач. Рассмотрим симметричную форму: Пусть дана зад ЛП станд. Формы:

a11x1+a12x2+...+a1n xn>=b1

a21x1+a22x2+...+a2nxn>=b2

...-....-....-....-...-....-....-....-

am1x1+am2x2+...+amnxn>=bm

x1>=0; x2>=0;...., 1n>=0

f = c1x1+c2x2+...+cnxn

Составим др. зад., связанную с данной кот. Назовем двойственной:

A11y1+a12y2+...+am1ym <= c1

A12y1+a22y2+...+am2ym <= c2

...-...-...-...-...-...-...-...-...-...-.

a1ny1+a2nyn+...+amnym <= cn

yi >=0, i=1,m

f = b1y1+b2y2+...+bnym

Сопоставляя пару взаимодвойственных зад. М. установить взаимосвязи:

1) матрицы системы неравенств исх. Двойственных зад. Транспонир. Др.др,

2) если исх. Зад. Имеет min, то двойств к ней max,

3) коэффициенты целевой функции исх. Зад. Являются свободн. членами сист. Неравенств двойств. и обратно, своб чл. Сист. Исх. Являются коэф-ами целевой функции двойственной.

4) в сист. ограничений исход. и двойственных задач неравенства имеют противоположный смысл.

5) число неравенств исх. задач = числу неизв. двойств-ой и обратно числу неравенств двойствен. – числу неизв. исходных.

6) свойства взаимодвойственных задач:

a) если одна из 2ух взаимодвойств. зад. имеет оптим. план., то и др. имеет оптим. план, причем min f = max φ (осн. теорема двойствен-ти)

b) значение целевой функции исх. задачи не превышает значение целевой функции двойств. зад., т.е. f(x)<=φ(y) для

c) если целевая ф-ция исх. зад. неограниченна снизу, то двойств. не имеет оптимального плана.

Приведенные взаимодв. и св-ва взаимодв. зад. позволяют сделать вывод о том, что решение одной из них фактич. дает решение двойств. ей задач.

Во-первых, по осн. теории двойств-ти, оптим-ое значение целевой ф-ции совпадает min f = max φ; во-вторых, остается найти координацию точек оптимумов этих функций.

5. Экономико-математическая модель транспортной задачи. Составление первоначального опорного плана.

Приведем экономическую формулировку транспортной задачи (ТЗ) по критерию стоимости: однородный груз, имеющийся в m пунктах отправителя А1, А2. Требуется доставить каждый груз из n пунктов назначения В1, В2, …,Вn. Стоимость перевозки из a_i в b_i известна для всех маршрутов и равна S_ij. Требуется составить такой план перевозок, при котором весь груз из пунктов отправления вывозится и запросы всех пунктов потребления удовлетворяются. x_ij>>0

 

 

 

Из приведенной таблицы легко усматривается и составляется математическая модель ТЗ для закрытой модели. (Σ_i=1^ma_i= Σ_j=1^mb_j)

X11+X12+…+X1n=a1

X21+X22+…+X2n=a2

……………………….

Xm1+Xm2+…+Xmn=am (1)

X11+X21+…+Xm1=b1

X21+X22+…+X2n=b2

……………………….

X1n+X2n+…+Xmn=bn

F=C11X11+C12X12+…+C1nX1n+…+CmnXmn →min (общая стоимость перевозок) (2)

Число r=m+n-1 равное рангу систем (1) называется рангом транспортной системы. Если число заполненных клеток таблицы равно r, то план называется невырожденным. А если это число меньше, то – вырожденным. В случае открытой модели Σa_i≠Σb_j легко сводится к закрытой модели путем введения Bn+1 с потребностью b_n+1= Σa_i+Σb_j либо a _n+1=Σb_j-Σa_i.

Составление опорного плана.

1. Способ северо-западного угла (диагонали). Сущность способа заключается в том, что на каждом шаге заполняется левая верхняя клетка. Оставшейся части таблицы причем максимально возможным числом: либо полностью вывозится груз из a_i, либо полностью удовлетворяется потребность b_j. Процедура производится до тех пор, пока на каком-то шаге не исчерпаются запасы a_i и не удовлетворятся потребности b_j. В заключении проверяют, что найденные компоненты плана удовлетворяют горизонтальным и вертикальным уравнениям и что выполняются условия невырожденности плана.

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