Настоящая лекция посвящена
Исследования в этом направлении, начатые еще в шестидесятые годы прошлого столетия, к настоящему времени продвинулись настолько далеко, что сейчас мы уже вправе говорить о самостоятельном разделе математического программирования – дискретном программировании. В литературе употребляется также термин "
Линейное программирование является составной частью более общего метода — математического программирования. Математическое программирование позволяет находить наилучшие планы распределения ограниченных ресурсов для достижения требуемой цели – решения задачи. Линейное программирование может быть использовано как один из методов оптимизации решения. Наилучший результат здесь достигается не за счет выделения дополнительных сил и средств или иных ресурсов, а за счет их рационального распределения.
Линейное программирование от других видов математического программирования отличается тем, что математическая модель, соответствующая целевой установке задачи, может быть записана с помощью линейных соотношений вида:
$$c_1x_1+c_2x_2+...+c_jx_j+...+c_nx_n=c_0$$,
где $$c_j$$ — $$j$$ - $$e$$ — известные коэффициенты;
$$x_j$$ - $$j$$ - $$e$$ — неизвестные переменные $$(j=1,2,...,n)$$.
В общем виде постановка задачи линейного программирования выглядит следующим образом.
Условия задачи задаются в виде системы линейных уравнений или неравенств, которые представляют ограничения, налагаемые на использование имеющихся ресурсов:
$$a_{11}x_1+a_{12}x_2+...+a_{1j}x_j+...+a_{1n}x_n=b_1;\\ a_{21}x_1+a_{22}x_2+...+a_{2j}x_j+...+a_{2n}x_n=b_2;\\ .......................................\\ a_{i1}x_1+a_{i2}x_2+...+a_{ij}x_j+...+a_{in}x_n=b_i;\\ a_{m1}x_1+a_{m2}x_2+...+a_{mj}x_j+...+a_{mn}x_n=b_m;\\ $$
где
$$j=1,2,...n;i=1,2,...,m;m < n\\ x_j \ge 0 (j=1,2,...n)$$.
Искомые величины $$(x_1,x_2,...,x_n)$$ не могут быть отрицательными; $$a_{ij},b_i$$ — известные постоянные величины, характеризующие условия задачи.
$$y=c_1x_1+c_2x_2+...+c_jx_j+...+c_nx_n$$
где $$c_j$$ — постоянные коэффициенты, которые обычно называют коэффициентами стоимости $$(j=1,2,...,n)$$.
Целевую функцию по условиям задачи требуется обратить в минимум или максимум. В некоторых задачах выражения (6.2.) задаются в виде неравенств. В этих случаях, вводя в каждое линейное ограничение дополнительные неотрицательные неизвестные
$$x_{n+1},x_{n+2},...,x_{n+m}$$,
можно привести систему линейных ограничений к виду (6.2.).
Геометрическую интерпретацию задачи линейного программирования рассмотрим на примере.
Четыре вида овощей $$(m=4)$$ необходимо распределить по шести транспортным средствам $$(n=6)$$.
Распределение овощей по транспортным средствам сопряжено с необходимостью учета ряда ограничений, которые могут быть описаны системой четырех уравнений с шестью неизвестными, аналогичными системе 6.2.
$$\left. \begin{array}{ccc} 4x_1+x_4=16;\\ 2x_2+x_5=10;\\ x_3+2x_4+6x_5=76;\\ 4x_1+3x_2+x_6=24;\\ x_j\ge 0(j=1,...,4)\\ \end{array} \right\}$$
Смысл первого уравнения в нашем примере означает, что овощ типа 1, общий ресурс которого составляет 16 единиц, может размещаться в количестве четырех единиц на транспортном средстве первого типа и одной единицы на транспортном средстве четвертого типа. Аналогично и второе уравнение и так далее.
Последнее условие говорит о том, что число типов транспортного средства не может быть отрицательным.
Необходимо определить, какое количество транспортного средства каждого типа следует иметь, чтобы общие потери в них были минимальными.
Оплата за конкретное транспортное средство (в тысячах рублей) задана следующей таблицей.
| Тип единицы транспорта, $$j$$ | 1 | 2 | 3 | 4 | 5 | 6 |
| Стоимость перевозки на транспорте данного типа, $$c_j$$ | 0,4 | 0,5 | 0,2 | 0,8 | 0,6 | 0,3 |
В соответствии с приведенными данными, целевая функция, подлежащая оптимизации, примет вид:
$$y=0,4x_1+0,5x_2+0,2x_3+0,8x_4+0,6x_5+0,3x_6$$.
Решение задачи сводится к выполнению ограничений, заданных уравнением (6.4.)
В этом примере, когда $$n-m=2$$, каждое из ограничительных линейных уравнений (6.4.), а также линейная функция (6.5.), могут быть представлены геометрически в двухмерном пространстве (на плоскости), что дает возможность весьма наглядно интерпретировать основные идеи метода линейного программирования.
Геометрическая интерпретация задачи линейного программирования. Чтобы иметь возможность наглядно представить ограничения и целевую функцию на графике, необходимо выразить все неизвестные через две независимые величины, например, $$x_1$$ и $$x_2$$, соответствующие координатным осям, относительно которых будет производиться построение (рис. 6.1). Из уравнения (6.4.) следует:
$$\left. \begin{array}{ccc} x_3=8x_1+12x_2-16;\\ x_4=16-4x_1;\\ x_5=10-2x_2;\\ x_6=24-4x_1-3x_2 \end{array} \right\}$$
А целевая функция примет такой вид:
$$y=-2,4x_1+0,8x_2+22,8$$.
Из сопоставления уравнений (6.6.) и последнего из ограничений (6.2.) $$x_j\ge 0$$ следует:
$$x_1\ge 0;\\ x_2\ge 0;\\ x_3=8x_1+12x_2-16\ge 0;\\ x_4=16-4x_1\ge 0;\\ x_5=10-2x_2\ge 0;\\ x_6=24-4x_1-3x_2\ge 0;$$
Каждому из неравенств (6.8.) на графике рис. 6.1 соответствует полуплоскость, в пределах которой находятся все допускаемые данным неравенством значения переменной величины $$x_j(j=1,2,...,6)$$.
Так, например, неравенству $$x_1\ge 0$$ соответствует полуплоскость вправо от оси $$x_2$$ (граница ее заштрихована).
Неравенству
$$x_3=8x_1+12x_2 -16\ge 0$$
соответствует полуплоскость вправо и вверх от линии, соответствующей значению данного неравенства (при $$x_3=0$$ ).
Уравнение этой линии
$$x_1+\frac{3}{4}x_2-1=0$$.
Таким же образом можно построить границы, определяемые другими уравнениями.
Неравенствам (6.8.) соответствует некоторая область – шестиугольник $$ABCDEF$$, образованный границами упомянутых выше полуплоскостей.
Из всех доступных планов нас интересует оптимальный план, при котором функция цели достигает минимума.
Целевой функции соответствует семейство параллельных прямых. Рассмотрим одну из них, проходящую через начало координат, что будет иметь место при $$y=22,8$$.
При этом
$$x_2=3x_1$$.
Интересующая нас прямая $$y=22,8$$, как видно из рисунка 6.1, имеет наклон вправо от оси $$x_2$$. Задаваясь различными значениями $$y$$, получим семейство прямых линий, параллельных прямой $$y=22,8$$, которая проходит через точку 0. При этом чем меньше будет $$y$$, тем, очевидно, правее располагается соответствующая прямая.
Поскольку мы добиваемся минимального значения $$y$$, нас будет интересовать прямая, расположенная в наибольшем удалении вправо от прямой $$y=22,8$$ и проходящая через многоугольник $$ABCDEF$$, — прямая $$y_{min}$$.
Как видно из рисунка 6.1, единственной точкой, соответствующей оптимальному плану, будет та вершина многоугольника $$ABCDEF$$, которая одновременно принадлежит области допустимых планов и отвечает требованию минимизации целевой функции $$y$$ — вершина $$C$$.
Итак минимум целевой функции достигается в вершине многогранника. Существует теорема о том, что для любой задачи линейного программирования найдется вершина многогранника допустимых решений, в которой целевая функция достигает своего минимального (максимального) значения.
(рис 6.1)
Рассмотрим общий путь нахождения оптимального плана на примере.
Первый шаг в решении задачи – построение области допустимых планов – нами уже сделан (см. рис. 6.1). Из рисунка видно, как определить координаты точки $$C$$, соответствующей оптимальному плану. Из уравнения прямой $$BC$$, проходящей через ту же точку, следует, что $$x_1=4$$. Из уравнения прямой $$DC$$, проходящей через ту же точку, следует, что $$x_2=0$$. Подставляя полученные значения $$x_1=4$$ и $$x_2=0$$ в уравнения (6.6.), определим величины остальных переменных, составляющих оптимальный план:
$$x_3=16;\\ x_4=0;\\ x_5=10;\\ x_6=8;$$
Таким образом, оптимальный план будет следующим:
$$\left. \begin{array}{ccc} x_1=4;\\ x_2=0;\\ x_3=16;\\ x_4=0;\\ x_5=10;\\ x_6=8; \end{array} \right\}$$
$$y=-\frac{24}{10}\cdot 4+ \frac{8}{10}\cdot 0 +\frac{228}{10}=\frac{132}{10}=13,2$$.
Рассмотренная геометрическая интерпретация задачи линейного программирования возможна лишь при наличии двух независимых переменных. При трех переменных наглядное представление существенно усложняется, так как в этом случае имеет место некоторый выпуклый многогранник в трехмерном пространстве, соответствующий объему допустимых планов.
При количестве переменных более трех задача теряет геометрическую наглядность, так как трудно представить себе, например, четырехмерное пространство. Однако идея получения решения, рассмотренного выше, сохраняет смысл и для случая многомерного пространства.
На основе этой идеи создан и разработан один из основных методов решения задач линейного программирования – так называемый
Первый шаг. Найти допустимый план, соответствующий одной из вершин области допустимых планов.
Второй шаг. Проверить, оптимален ли найденный план. Если оптимален, вычисления окончены. Если нет – следующий план.
Третий шаг. Переход к другой вершине (другому допустимому плану), в которой значение целевой функции меньше, проверка его на оптимальность и так далее.
Поэтому первым шагом должно быть получение координат одной из вершин многоугольника (многогранника) допустимых планов. Для этого необходимо преобразовать систему уравнений таким образом, чтобы с ее помощью можно было легко получить координаты вершины многоугольника (многогранника) области допустимых планов.
Анализируя рис 6.1, можно заметить, что в каждой из вершин две из переменных обращаются в нуль. Поэтому мы должны положить две переменные равными нулю, а затем найти остальные четыре из системы уравнений (6.4.). В совокупности все переменные дадут один из допустимых планов, соответствующих некоторой вершине.
Чтобы преобразовать систему уравнений описанным образом, необходимо выразить каждую из неизвестных $$x_1,x_2,...,x_m$$ через остальные.
Такая возможность существует лишь в случае, если определитель
$$\begin{vmatrix} a_{11} a_{12}... a_{1m}\\ a_{21} a_{22}... a_{2m}\\ ....\\ a_{m1} a_{m2}... a_{mm}\\ \end{vmatrix} \ne 0$$
Если это условие выполняется, то величины $$x_1,x_2,...,x_m$$ называют
Преобразуем систему уравнений (6.4.) так, чтобы, приравнивая две переменные нулю (например, $$x_5=0,x_6=0$$ ), можно было получить значения
Предварительно убедимся, что определитель, составленный из коэффициентов при этих неизвестных в уравнениях (6.4.), не равен нулю.
Действительно,
$$\begin{vmatrix} 4 00 1\\ 0200\\ 0012\\ 4300\\ \end{vmatrix} =8$$
Это дает нам право считать, что величины $$x_1,x_2,x_3,x_4$$ являются базисными и система (6.4.) может быть разрешена относительно их.
Все необходимые преобразования будем производить с матрицей коэффициентов уравнений (6.4.):
$$\begin{pmatrix} 40010016\\ 02001010\\ 00126076\\ 43000124\\ \end{pmatrix}$$
Преобразуем матрицу (6.11.) в соответствии с указанным выше требованием получения базисных значений переменных величин. Для этого необходимо выполнить над ней такие преобразования, чтобы базисные переменные остались по одной в каждом из уравнений (строке матрицы), а коэффициенты при них были равны единице. Начинаем с коэффициента при $$x_1$$ в первом уравнении. Чтобы сделать его равным единице, делим все коэффициенты первого уравнения на четыре. Для исключения переменной $$x_1$$ из остальных уравнений отнимаем от каждого из них первое уравнение, умноженное на такое число, при котором разность коэффициентов при $$x_1$$ была бы равна нулю. Например, второе и третье уравнения (строки) нужно умножить на нуль, четвертое – на единицу.
В результате преобразований получим
$$\begin{pmatrix} 100\frac{1}{4}004\\ 02001010\\ 00126076\\ 030-1018\\ \end{pmatrix}$$
Аналогичные преобразования выполняем для переменной во второй строке:
$$\begin{pmatrix} 100\frac{1}{4}004\\ 0100\frac{1}{2}05\\ 00126076\\ 000-1-\frac{3}{2}1-7\\ \end{pmatrix} $$
Для переменной $$x_3$$ — в третьей строке и $$x_4$$ — в четвертой:
$$\begin{pmatrix} 1000-\frac{3}{8}\frac{1}{4}\frac{9}{4}\\ 0100\frac{1}{2}05\\ 00103262\\ 0001\frac{3}{2}-17\\ \end{pmatrix}$$
Теперь, приравнивая переменные $$x_5$$ и $$x_6$$ (соответственно пятый и шестой столбцы матрицы) нулю, можем написать значение базисных переменных, которые будут в этом случае равны свободным членам соответствующих уравнений:
$$x_1=\frac{9}{4};\\ x_2=5;\\ x_3=62;\\ x_4=7;\\$$
Обращаясь к геометрической интерпретации (рис. 6.1), можно убедиться, что полученные координаты $$(x_1=2\frac{1}{4}, x_2=5, x_5=x_6=0)$$ соответствуют вершине $$A$$ многоугольника $$ABCDEF$$ — области допустимых планов. Это и есть первый допустимый план.
Теперь можно перейти ко второму шагу симплекс-метода – установлению того, является ли допустимый план, соответствующий найденной вершине $$A$$, оптимальным.
Наиболее естественным путем решения этой задачи был бы сплошной перебор всех вершин области допустимых планов, определение для каждой из них значений переменных $$x_j(j=1,2,...,6)$$ и вычисление по ним в каждой вершине величины целевой функции.
Та вершина, в которой величина $$y$$ окажется минимальной, и даст искомый оптимальный план.
Но этот путь весьма неэкономный, ибо требует просчитать большое количество планов, в том числе и явно неоптимальных.
В чем сущность направленного перебора?
В первом допустимом плане, соответствующем вершине $$A$$, целевая функция в соответствии с формулой (6.7.) равна:
$$y_A=-2,4\cdot 2\frac{1}{4}+0,8\cdot 5+22,8=21,4$$
Мы уже знаем из (6.10.), что $$y_{min}=13,2$$. Следовательно, целевая функция в точке $$A$$ значительно больше минимума, и необходимо продолжать перебор вершин-планов до тех пор, пока не придем к оптимальному.
Из вершины $$A$$ можно перейти к соседним вершинам $$F$$ и $$B$$ (рис. 6.1), двигаясь по сторонам многоугольника $$AF$$ и $$AB$$ соответственно. Видимо, нужно избрать такое направление перехода к соседней вершине, которое приведет к наибольшему уменьшению целевой функции.
Рассчитаем значения целевой функции для соседних вершин $$F,B$$. Пользуясь формулой (6.7.) и подставляя соответствующие значения $$x_1$$, $$x_2$$, получим:
$$y_F= -2,4\cdot 0+0,8\cdot 5=26,8;\\ y_B= -2,4\cdot 4+0,8\cdot 2\frac{2}{3}+22,8=15,33$$.
Сопоставляя два последних выражения, нетрудно убедиться, что минимизация функции цели достигается при движении к точке $$B$$ по стороне $$AB$$. Это означает, что в базис вводится переменная $$x_5$$, которая в вершине $$A$$ была равна нулю.
Поскольку при отсутствии наглядного геометрического представления заранее нельзя располагать значениями переменных в вершинах многоугольника, то для установления необходимости и направления перебора планов пользуются специальным критерием $$\delta_j$$:
$$\delta_j=\sum\limits_{i=1}^{m}c_ia_{ij}-c_j$$,
где индекс $$j$$ приписывается небазисным (нулевым) переменным, а индекс $$i$$ — базисным. Имеется доказательство того, что в случае оптимальности полученного плана все $$\delta_j$$ становятся равными нулю или меньшими нуля. Включению в базис подлежит та переменная, для которой $$\delta_j$$ принимает наибольшее положительное значение. В нашем примере это:
$$\delta_5=-\frac{8}{5}\cdot (\frac{3}{8})+(-\frac{16}{10})\cdot \frac{1}{2}+\frac{2}{10}\cdot 3+\frac{8}{10}\cdot\frac{3}{2}-0=\frac{13}{10};$$
$$\delta_6=-\frac{8}{10}\cdot \frac{1}{4}-\frac{16}{10}\cdot 0+\frac{2}{10}\cdot 2-\frac{8}{10}\cdot 1-0=-\frac{3}{5}$$.
Таким образом, мы приходим к тому же заключению о необходимости включения в базис переменной $$x_5$$, для которой критерий имеет наибольшее положительное значение.
Далее необходимо установить, какая переменная должна быть выведена из базиса при введении в него переменной $$x_5$$. Чтобы ответить на этот вопрос, будем рассуждать так.
Очевидно, следует переместиться по стороне $$AB$$ как можно дальше от точки $$A$$, чтобы как можно больше уменьшить целевую функцию. Стало быть, можно взять в качестве координаты $$x_1$$ точки $$B$$ ее максимальное возможное значение, которое допускается системой уравнений , соответствующей матрице (6.12.), то есть такое, при котором ни одна из переменных не становится отрицательной. Можно показать, что это достигается в том случае, если вывести из базиса переменную, которой соответствует минимальное положительное
Поэтому избирается четвертая строка матрицы и соответственно переменная $$x_4$$, подлежащая исключению из базиса.
Теперь необходимо получить в четвертой строке значение коэффициента при новой
Получим
$$\begin{pmatrix} 1000004\\ 01000\frac{1}{3}\frac{8}{3}\\ 00100448\\ 000\frac{2}{3}1-\frac{2}{3}\frac{14}{3} \end{pmatrix}$$
Данной матрице отвечает допустимый план в вершине $$B$$. Приравнивая небазисные переменные нулю $$(x_4=x_6=0)$$, получаем значения остальных переменных, соответствующих второму плану:
$$x_1=4; x_3=48;\\ x_2=\frac{8}{3};x_5=\frac{14}{3}$$.
Как уже было показано, $$y_B=15\frac{1}{3}$$. Итак, получено существенное сокращение целевой функции, однако критерий $$\delta_6$$ продолжает оставаться положительным, что говорит о необходимости дальнейшего улучшения плана:
$$\delta_4=-\frac{2}{5}; \delta_6=\frac{3}{10}$$.
На этот раз в базис вводится переменная $$x_6$$, а выводится переменная $$x_2$$, которой соответствует наименьшее значение коэффициента в столбце $$x_6$$.
После преобразования матрицы (6.14.) получаем матрицу (6.15.), отвечающую третьему плану:
$$\begin{pmatrix} 1000004\\ 0300018\\ 0-12100016\\ 020\frac{2}{3}1010 \end{pmatrix}$$.
Данный план соответствует вершине $$C$$:
$$x_1=4; x_4=0;\\ x_2=0; x_5=10;\\ x_3=16; x_6=8$$.
Критерии для данного плана равны:
$$\delta_2=-\frac{4}{5}; \delta_4 =-\frac{2}{5}$$.
Поскольку нет ни одного положительного критерия, то третий план и является оптимальным, что следует из рис. 6.1.
Целевая функция при данном плане равна:
$$y_C=13,2$$
Итак, мы пришли аналитическим путем к тому же оптимальному плану, который был ранее получен геометрическим способом.
Решение примера 6.1. можно сформулировать следующим образом.
Чтобы общие потери были минимальны, количество носителей первого типа должно быть равно 4, второго – 0, третьего – 16, четвертого 0, пятого 10, шестого – 8.
При этом потери в носителях будут составлять 13,2 единицы.
Важно отметить, что наихудший план распределения, соответствующий точке $$F$$, приводит к потерям 26,8 единиц. Таким образом, без дополнительного расходования носителей и овощей (только за счет их рационального распределения) улучшен результат решения задачи перевозки более чем в два раза.
Полученное решение – целочисленное, что, однако, не является обязательным для задач линейного программирования. В ряде случаев для получения целочисленного решения приходится прибегать к искусственным приемам, что существенно усложняет вычислительную процедуру.
Имеется $$m$$ пунктов поставщиков $$A_1,A_2,...,A_m$$ и $$n$$ пунктов назначения (потребителей) $$B_1,B_2,...,B_n$$.
$$a_i$$ — количество груза в тоннах, сосредоточенное в пункте $$A_i(i=1,2,...,m)$$ ;
$$b_j$$ — количество груза, ожидаемое в пункте $$B_j(j=1,2,...,n)$$.
Принимаем условие
$$a_1+a_2+...+a_m=b_1+b_2+...+b_n$$,
означающее, что суммарный запас груза равен суммарной потребности в нем.
$$c_{ij}$$ — стоимость перевозки одной тонны груза из пункта $$A_i$$ в пункт $$B_j$$.
$$x_{ij}$$ — количество тон груза, перевезенное из пункта $$A_i$$ в пункт $$B_j$$.
Требуется найти оптимальный план перевозок, то есть рассчитать, сколько груза должно быть отправлено из каждого пункта отправления в каждый пункт назначения, с тем условием, чтобы суммарная стоимость перевозок была наименьшей.
Неизвестными в нашей задаче являются $$mn$$ неотрицательных чисел $$x_{ij}(i=1,...,m;j=1,...,n)$$. Сведем их в таблицу 6.1, назовем ее матрицей перевозок.
| $$B_1$$ | $$B_2$$ | ... | $$B_n$$ | ||
| $$A_1$$ | $$x_{11}$$ | $$x_{12}$$ | ... | $$x_{1n}$$ | $$a_1$$ |
| $$A_2$$ | $$x_{21}$$ | $$x_{22}$$ | ... | $$x_{2n}$$ | $$a_2$$ |
| ... | ... | ... | ... | ... | ... |
| $$A_m$$ | $$x_{m1}$$ | $$x_{m2}$$ | ... | $$x_{mn}$$ | $$a_m$$ |
| $$b_1$$ | $$b_2$$ | ... | $$b_n$$ |
Запишем соотношение для пунктов поставщиков $$A_1,A_2,...,A_m$$ и пунктов потребителей $$B_1,B_2,...,B_n$$.
Будем называть уравнение 0I горизонтальными уравнениями, а 0II – вертикальными. Перевозка из $$A_i$$ и $$B_j$$ стоит $$c_{ij}x_{ij}$$, общая стоимость всех перевозок будет
$$S=\sum\limits_{i,j}c_{ij}x_{ij}$$,
где суммирование производится по всем $$i=1,...m$$ и всем $$j=1,...n$$. Таким образом, мы пришли к следующей задаче линейного программирования:
Дана система уравнений I и линейная функция II. Требуется среди неотрицательных решений системы найти такое, которое минимизирует функцию II.
Разберем метод на примере.
Пусть есть 3 пункта отправления
$$A_1,A_2,A_3$$
и 4 пункта назначения
$$B_1,B_2,B_3,B_4$$.
Запасы в пунктах отправления:
$$a_1=60,a_2=80,a_3=100$$.
Потребности:
$$b_1=40,b_2=60,b_3=80,b_4=60$$.
Занесем данные в таблицу.
| $$B_1$$ | $$B_2$$ | $$B_3$$ | $$B_4$$ | Запасы | |
| $$A_1$$ | 40 | 60 | |||
| $$A_2$$ | 80 | ||||
| $$A_3$$ Потребности |
40 | 60 | 80 | 60 | 100 |
Потребности пункта $$B_1-b_1=40$$ удовлетворены полностью и поэтому столбец, соответствующий $$B_1$$, можно временно исключить из рассмотрения, то есть переходим к таблице 3.
| $$A_1$$ | $$B_2$$ 20 |
$$B_3$$ | $$B_4$$ | $$a\prime =60-40=20$$ (так как переслали в $$B_1$$ ) |
| $$A_2$$ | 80 | |||
| $$A_3$$ | 100 | |||
| 60 | 80 | 60 |
Отметим, что и в таблице 6.3 сумма всех потребностей по-прежнему равна сумме всех запасов. К Таблице 6.3 применим тот же прием и попытаемся удовлетворить потребности $$b_2=60$$ пункта $$B_2$$.(в таблице 6.3 пункт $$B_2$$ играет роль первого) запасами $$a_1^{\prime}=20$$ пункта $$A_1$$. Очевидно, что потребности эти удается удовлетворить лишь частично, так как $$b_2 > a_1^{\prime}$$. При этом потребности $$B_2$$ сократятся до $$b_2^{\prime}=40$$, а запасы $$A_1$$ окажутся исчерпаны полностью. В силу этого строку, отвечающую $$A_1$$, из таблицы 6.3 можно временно удалить. Получим новую таблицу – таблицу 6.4, в которой имеются уже два пункта отправления $$A_2$$ и $$A_3$$ и три пункта назначения $$B_2,B_3,B_4$$.
| $$B_2$$ | $$B_3$$ | $$B_4$$ | ||
| $$A_2$$ | 40 | 80 | ||
| $$A_3$$ | 100 | |||
| 40 | 80 | 60 |
Аналогичным приемом продолжаем сокращать последовательно получаемые таблицы, пока не удовлетворим потребности всех пунктов назначения. В случае, когда новые запасы равны новым потребностям, можно исключить из таблицы по желанию строку и столбец. В процессе сокращения таблиц мы получим следующие значения для некоторых из неизвестных:
$$x_{11}=40, x_{12}=20, x_{22}=40, x_{23}=40, x_{33}=40,x_{34}=60$$.
Вписав их в таблицу 6.2, получим таблицу 6.5.
| $$B_1$$ | $$B_2$$ | $$B_3$$ | $$B_4$$ | |
| $$A_1$$ | 40 | 20 | ||
| $$A_2$$ | 40 | 40 | ||
| $$A_3$$ | 40 | 60 |
Условимся называть те клетки таблицы 6.5, в которые вписаны значения неизвестных, — базисными, а остальные клетки — свободными. Если считать, что значения неизвестных $$x_{ij}$$, которые отвечают свободным клеткам, равны нулю, то получившийся набор значений всех неизвестных дает допустимое решение рассматриваемой задачи.
Действительно, легко проверить, что сумма значений неизвестных в каждой строке таблицы равна запасу в соответствующем пункте отправления, а в каждом столбце – потребности в соответствующем пункте назначения. Поэтому уравнения I, II удовлетворяются.
В качестве примера прикладных задач
Настоящая лекция посвящена
Исследования в этом направлении, начатые еще в шестидесятые годы прошлого столетия, к настоящему времени продвинулись настолько далеко, что сейчас мы уже вправе говорить о самостоятельном разделе математического программирования – дискретном программировании. В литературе употребляется также термин "
Линейное программирование является составной частью более общего метода — математического программирования. Математическое программирование позволяет находить наилучшие планы распределения ограниченных ресурсов для достижения требуемой цели – решения задачи. Линейное программирование может быть использовано как один из методов оптимизации решения. Наилучший результат здесь достигается не за счет выделения дополнительных сил и средств или иных ресурсов, а за счет их рационального распределения.
Линейное программирование от других видов математического программирования отличается тем, что математическая модель, соответствующая целевой установке задачи, может быть записана с помощью линейных соотношений вида:
$$c_1x_1+c_2x_2+...+c_jx_j+...+c_nx_n=c_0$$,
где $$c_j$$ — $$j$$ - $$e$$ — известные коэффициенты;
$$x_j$$ - $$j$$ - $$e$$ — неизвестные переменные $$(j=1,2,...,n)$$.
В общем виде постановка задачи линейного программирования выглядит следующим образом.
Условия задачи задаются в виде системы линейных уравнений или неравенств, которые представляют ограничения, налагаемые на использование имеющихся ресурсов:
$$a_{11}x_1+a_{12}x_2+...+a_{1j}x_j+...+a_{1n}x_n=b_1;\\ a_{21}x_1+a_{22}x_2+...+a_{2j}x_j+...+a_{2n}x_n=b_2;\\ .......................................\\ a_{i1}x_1+a_{i2}x_2+...+a_{ij}x_j+...+a_{in}x_n=b_i;\\ a_{m1}x_1+a_{m2}x_2+...+a_{mj}x_j+...+a_{mn}x_n=b_m;\\ $$
где
$$j=1,2,...n;i=1,2,...,m;m < n\\ x_j \ge 0 (j=1,2,...n)$$.
Искомые величины $$(x_1,x_2,...,x_n)$$ не могут быть отрицательными; $$a_{ij},b_i$$ — известные постоянные величины, характеризующие условия задачи.
$$y=c_1x_1+c_2x_2+...+c_jx_j+...+c_nx_n$$
где $$c_j$$ — постоянные коэффициенты, которые обычно называют коэффициентами стоимости $$(j=1,2,...,n)$$.
Целевую функцию по условиям задачи требуется обратить в минимум или максимум. В некоторых задачах выражения (6.2.) задаются в виде неравенств. В этих случаях, вводя в каждое линейное ограничение дополнительные неотрицательные неизвестные
$$x_{n+1},x_{n+2},...,x_{n+m}$$,
можно привести систему линейных ограничений к виду (6.2.).
Геометрическую интерпретацию задачи линейного программирования рассмотрим на примере.
Четыре вида овощей $$(m=4)$$ необходимо распределить по шести транспортным средствам $$(n=6)$$.
Распределение овощей по транспортным средствам сопряжено с необходимостью учета ряда ограничений, которые могут быть описаны системой четырех уравнений с шестью неизвестными, аналогичными системе 6.2.
$$\left. \begin{array}{ccc} 4x_1+x_4=16;\\ 2x_2+x_5=10;\\ x_3+2x_4+6x_5=76;\\ 4x_1+3x_2+x_6=24;\\ x_j\ge 0(j=1,...,4)\\ \end{array} \right\}$$
Смысл первого уравнения в нашем примере означает, что овощ типа 1, общий ресурс которого составляет 16 единиц, может размещаться в количестве четырех единиц на транспортном средстве первого типа и одной единицы на транспортном средстве четвертого типа. Аналогично и второе уравнение и так далее.
Последнее условие говорит о том, что число типов транспортного средства не может быть отрицательным.
Необходимо определить, какое количество транспортного средства каждого типа следует иметь, чтобы общие потери в них были минимальными.
Оплата за конкретное транспортное средство (в тысячах рублей) задана следующей таблицей.
| Тип единицы транспорта, $$j$$ | 1 | 2 | 3 | 4 | 5 | 6 |
| Стоимость перевозки на транспорте данного типа, $$c_j$$ | 0,4 | 0,5 | 0,2 | 0,8 | 0,6 | 0,3 |
В соответствии с приведенными данными, целевая функция, подлежащая оптимизации, примет вид:
$$y=0,4x_1+0,5x_2+0,2x_3+0,8x_4+0,6x_5+0,3x_6$$.
Решение задачи сводится к выполнению ограничений, заданных уравнением (6.4.)
В этом примере, когда $$n-m=2$$, каждое из ограничительных линейных уравнений (6.4.), а также линейная функция (6.5.), могут быть представлены геометрически в двухмерном пространстве (на плоскости), что дает возможность весьма наглядно интерпретировать основные идеи метода линейного программирования.
Геометрическая интерпретация задачи линейного программирования. Чтобы иметь возможность наглядно представить ограничения и целевую функцию на графике, необходимо выразить все неизвестные через две независимые величины, например, $$x_1$$ и $$x_2$$, соответствующие координатным осям, относительно которых будет производиться построение (рис. 6.1). Из уравнения (6.4.) следует:
$$\left. \begin{array}{ccc} x_3=8x_1+12x_2-16;\\ x_4=16-4x_1;\\ x_5=10-2x_2;\\ x_6=24-4x_1-3x_2 \end{array} \right\}$$
А целевая функция примет такой вид:
$$y=-2,4x_1+0,8x_2+22,8$$.
Из сопоставления уравнений (6.6.) и последнего из ограничений (6.2.) $$x_j\ge 0$$ следует:
$$x_1\ge 0;\\ x_2\ge 0;\\ x_3=8x_1+12x_2-16\ge 0;\\ x_4=16-4x_1\ge 0;\\ x_5=10-2x_2\ge 0;\\ x_6=24-4x_1-3x_2\ge 0;$$
Каждому из неравенств (6.8.) на графике рис. 6.1 соответствует полуплоскость, в пределах которой находятся все допускаемые данным неравенством значения переменной величины $$x_j(j=1,2,...,6)$$.
Так, например, неравенству $$x_1\ge 0$$ соответствует полуплоскость вправо от оси $$x_2$$ (граница ее заштрихована).
Неравенству
$$x_3=8x_1+12x_2 -16\ge 0$$
соответствует полуплоскость вправо и вверх от линии, соответствующей значению данного неравенства (при $$x_3=0$$ ).
Уравнение этой линии
$$x_1+\frac{3}{4}x_2-1=0$$.
Таким же образом можно построить границы, определяемые другими уравнениями.
Неравенствам (6.8.) соответствует некоторая область – шестиугольник $$ABCDEF$$, образованный границами упомянутых выше полуплоскостей.
Из всех доступных планов нас интересует оптимальный план, при котором функция цели достигает минимума.
Целевой функции соответствует семейство параллельных прямых. Рассмотрим одну из них, проходящую через начало координат, что будет иметь место при $$y=22,8$$.
При этом
$$x_2=3x_1$$.
Интересующая нас прямая $$y=22,8$$, как видно из рисунка 6.1, имеет наклон вправо от оси $$x_2$$. Задаваясь различными значениями $$y$$, получим семейство прямых линий, параллельных прямой $$y=22,8$$, которая проходит через точку 0. При этом чем меньше будет $$y$$, тем, очевидно, правее располагается соответствующая прямая.
Поскольку мы добиваемся минимального значения $$y$$, нас будет интересовать прямая, расположенная в наибольшем удалении вправо от прямой $$y=22,8$$ и проходящая через многоугольник $$ABCDEF$$, — прямая $$y_{min}$$.
Как видно из рисунка 6.1, единственной точкой, соответствующей оптимальному плану, будет та вершина многоугольника $$ABCDEF$$, которая одновременно принадлежит области допустимых планов и отвечает требованию минимизации целевой функции $$y$$ — вершина $$C$$.
Итак минимум целевой функции достигается в вершине многогранника. Существует теорема о том, что для любой задачи линейного программирования найдется вершина многогранника допустимых решений, в которой целевая функция достигает своего минимального (максимального) значения.
(рис 6.1)
Рассмотрим общий путь нахождения оптимального плана на примере.
Первый шаг в решении задачи – построение области допустимых планов – нами уже сделан (см. рис. 6.1). Из рисунка видно, как определить координаты точки $$C$$, соответствующей оптимальному плану. Из уравнения прямой $$BC$$, проходящей через ту же точку, следует, что $$x_1=4$$. Из уравнения прямой $$DC$$, проходящей через ту же точку, следует, что $$x_2=0$$. Подставляя полученные значения $$x_1=4$$ и $$x_2=0$$ в уравнения (6.6.), определим величины остальных переменных, составляющих оптимальный план:
$$x_3=16;\\ x_4=0;\\ x_5=10;\\ x_6=8;$$
Таким образом, оптимальный план будет следующим:
$$\left. \begin{array}{ccc} x_1=4;\\ x_2=0;\\ x_3=16;\\ x_4=0;\\ x_5=10;\\ x_6=8; \end{array} \right\}$$
$$y=-\frac{24}{10}\cdot 4+ \frac{8}{10}\cdot 0 +\frac{228}{10}=\frac{132}{10}=13,2$$.
Рассмотренная геометрическая интерпретация задачи линейного программирования возможна лишь при наличии двух независимых переменных. При трех переменных наглядное представление существенно усложняется, так как в этом случае имеет место некоторый выпуклый многогранник в трехмерном пространстве, соответствующий объему допустимых планов.
При количестве переменных более трех задача теряет геометрическую наглядность, так как трудно представить себе, например, четырехмерное пространство. Однако идея получения решения, рассмотренного выше, сохраняет смысл и для случая многомерного пространства.
На основе этой идеи создан и разработан один из основных методов решения задач линейного программирования – так называемый
Первый шаг. Найти допустимый план, соответствующий одной из вершин области допустимых планов.
Второй шаг. Проверить, оптимален ли найденный план. Если оптимален, вычисления окончены. Если нет – следующий план.
Третий шаг. Переход к другой вершине (другому допустимому плану), в которой значение целевой функции меньше, проверка его на оптимальность и так далее.
Поэтому первым шагом должно быть получение координат одной из вершин многоугольника (многогранника) допустимых планов. Для этого необходимо преобразовать систему уравнений таким образом, чтобы с ее помощью можно было легко получить координаты вершины многоугольника (многогранника) области допустимых планов.
Анализируя рис 6.1, можно заметить, что в каждой из вершин две из переменных обращаются в нуль. Поэтому мы должны положить две переменные равными нулю, а затем найти остальные четыре из системы уравнений (6.4.). В совокупности все переменные дадут один из допустимых планов, соответствующих некоторой вершине.
Чтобы преобразовать систему уравнений описанным образом, необходимо выразить каждую из неизвестных $$x_1,x_2,...,x_m$$ через остальные.
Такая возможность существует лишь в случае, если определитель
$$\begin{vmatrix} a_{11} a_{12}... a_{1m}\\ a_{21} a_{22}... a_{2m}\\ ....\\ a_{m1} a_{m2}... a_{mm}\\ \end{vmatrix} \ne 0$$
Если это условие выполняется, то величины $$x_1,x_2,...,x_m$$ называют
Преобразуем систему уравнений (6.4.) так, чтобы, приравнивая две переменные нулю (например, $$x_5=0,x_6=0$$ ), можно было получить значения
Предварительно убедимся, что определитель, составленный из коэффициентов при этих неизвестных в уравнениях (6.4.), не равен нулю.
Действительно,
$$\begin{vmatrix} 4 00 1\\ 0200\\ 0012\\ 4300\\ \end{vmatrix} =8$$
Это дает нам право считать, что величины $$x_1,x_2,x_3,x_4$$ являются базисными и система (6.4.) может быть разрешена относительно их.
Все необходимые преобразования будем производить с матрицей коэффициентов уравнений (6.4.):
$$\begin{pmatrix} 40010016\\ 02001010\\ 00126076\\ 43000124\\ \end{pmatrix}$$
Преобразуем матрицу (6.11.) в соответствии с указанным выше требованием получения базисных значений переменных величин. Для этого необходимо выполнить над ней такие преобразования, чтобы базисные переменные остались по одной в каждом из уравнений (строке матрицы), а коэффициенты при них были равны единице. Начинаем с коэффициента при $$x_1$$ в первом уравнении. Чтобы сделать его равным единице, делим все коэффициенты первого уравнения на четыре. Для исключения переменной $$x_1$$ из остальных уравнений отнимаем от каждого из них первое уравнение, умноженное на такое число, при котором разность коэффициентов при $$x_1$$ была бы равна нулю. Например, второе и третье уравнения (строки) нужно умножить на нуль, четвертое – на единицу.
В результате преобразований получим
$$\begin{pmatrix} 100\frac{1}{4}004\\ 02001010\\ 00126076\\ 030-1018\\ \end{pmatrix}$$
Аналогичные преобразования выполняем для переменной во второй строке:
$$\begin{pmatrix} 100\frac{1}{4}004\\ 0100\frac{1}{2}05\\ 00126076\\ 000-1-\frac{3}{2}1-7\\ \end{pmatrix} $$
Для переменной $$x_3$$ — в третьей строке и $$x_4$$ — в четвертой:
$$\begin{pmatrix} 1000-\frac{3}{8}\frac{1}{4}\frac{9}{4}\\ 0100\frac{1}{2}05\\ 00103262\\ 0001\frac{3}{2}-17\\ \end{pmatrix}$$
Теперь, приравнивая переменные $$x_5$$ и $$x_6$$ (соответственно пятый и шестой столбцы матрицы) нулю, можем написать значение базисных переменных, которые будут в этом случае равны свободным членам соответствующих уравнений:
$$x_1=\frac{9}{4};\\ x_2=5;\\ x_3=62;\\ x_4=7;\\$$
Обращаясь к геометрической интерпретации (рис. 6.1), можно убедиться, что полученные координаты $$(x_1=2\frac{1}{4}, x_2=5, x_5=x_6=0)$$ соответствуют вершине $$A$$ многоугольника $$ABCDEF$$ — области допустимых планов. Это и есть первый допустимый план.
Теперь можно перейти ко второму шагу симплекс-метода – установлению того, является ли допустимый план, соответствующий найденной вершине $$A$$, оптимальным.
Наиболее естественным путем решения этой задачи был бы сплошной перебор всех вершин области допустимых планов, определение для каждой из них значений переменных $$x_j(j=1,2,...,6)$$ и вычисление по ним в каждой вершине величины целевой функции.
Та вершина, в которой величина $$y$$ окажется минимальной, и даст искомый оптимальный план.
Но этот путь весьма неэкономный, ибо требует просчитать большое количество планов, в том числе и явно неоптимальных.
В чем сущность направленного перебора?
В первом допустимом плане, соответствующем вершине $$A$$, целевая функция в соответствии с формулой (6.7.) равна:
$$y_A=-2,4\cdot 2\frac{1}{4}+0,8\cdot 5+22,8=21,4$$
Мы уже знаем из (6.10.), что $$y_{min}=13,2$$. Следовательно, целевая функция в точке $$A$$ значительно больше минимума, и необходимо продолжать перебор вершин-планов до тех пор, пока не придем к оптимальному.
Из вершины $$A$$ можно перейти к соседним вершинам $$F$$ и $$B$$ (рис. 6.1), двигаясь по сторонам многоугольника $$AF$$ и $$AB$$ соответственно. Видимо, нужно избрать такое направление перехода к соседней вершине, которое приведет к наибольшему уменьшению целевой функции.
Рассчитаем значения целевой функции для соседних вершин $$F,B$$. Пользуясь формулой (6.7.) и подставляя соответствующие значения $$x_1$$, $$x_2$$, получим:
$$y_F= -2,4\cdot 0+0,8\cdot 5=26,8;\\ y_B= -2,4\cdot 4+0,8\cdot 2\frac{2}{3}+22,8=15,33$$.
Сопоставляя два последних выражения, нетрудно убедиться, что минимизация функции цели достигается при движении к точке $$B$$ по стороне $$AB$$. Это означает, что в базис вводится переменная $$x_5$$, которая в вершине $$A$$ была равна нулю.
Поскольку при отсутствии наглядного геометрического представления заранее нельзя располагать значениями переменных в вершинах многоугольника, то для установления необходимости и направления перебора планов пользуются специальным критерием $$\delta_j$$:
$$\delta_j=\sum\limits_{i=1}^{m}c_ia_{ij}-c_j$$,
где индекс $$j$$ приписывается небазисным (нулевым) переменным, а индекс $$i$$ — базисным. Имеется доказательство того, что в случае оптимальности полученного плана все $$\delta_j$$ становятся равными нулю или меньшими нуля. Включению в базис подлежит та переменная, для которой $$\delta_j$$ принимает наибольшее положительное значение. В нашем примере это:
$$\delta_5=-\frac{8}{5}\cdot (\frac{3}{8})+(-\frac{16}{10})\cdot \frac{1}{2}+\frac{2}{10}\cdot 3+\frac{8}{10}\cdot\frac{3}{2}-0=\frac{13}{10};$$
$$\delta_6=-\frac{8}{10}\cdot \frac{1}{4}-\frac{16}{10}\cdot 0+\frac{2}{10}\cdot 2-\frac{8}{10}\cdot 1-0=-\frac{3}{5}$$.
Таким образом, мы приходим к тому же заключению о необходимости включения в базис переменной $$x_5$$, для которой критерий имеет наибольшее положительное значение.
Далее необходимо установить, какая переменная должна быть выведена из базиса при введении в него переменной $$x_5$$. Чтобы ответить на этот вопрос, будем рассуждать так.
Очевидно, следует переместиться по стороне $$AB$$ как можно дальше от точки $$A$$, чтобы как можно больше уменьшить целевую функцию. Стало быть, можно взять в качестве координаты $$x_1$$ точки $$B$$ ее максимальное возможное значение, которое допускается системой уравнений , соответствующей матрице (6.12.), то есть такое, при котором ни одна из переменных не становится отрицательной. Можно показать, что это достигается в том случае, если вывести из базиса переменную, которой соответствует минимальное положительное
Поэтому избирается четвертая строка матрицы и соответственно переменная $$x_4$$, подлежащая исключению из базиса.
Теперь необходимо получить в четвертой строке значение коэффициента при новой
Получим
$$\begin{pmatrix} 1000004\\ 01000\frac{1}{3}\frac{8}{3}\\ 00100448\\ 000\frac{2}{3}1-\frac{2}{3}\frac{14}{3} \end{pmatrix}$$
Данной матрице отвечает допустимый план в вершине $$B$$. Приравнивая небазисные переменные нулю $$(x_4=x_6=0)$$, получаем значения остальных переменных, соответствующих второму плану:
$$x_1=4; x_3=48;\\ x_2=\frac{8}{3};x_5=\frac{14}{3}$$.
Как уже было показано, $$y_B=15\frac{1}{3}$$. Итак, получено существенное сокращение целевой функции, однако критерий $$\delta_6$$ продолжает оставаться положительным, что говорит о необходимости дальнейшего улучшения плана:
$$\delta_4=-\frac{2}{5}; \delta_6=\frac{3}{10}$$.
На этот раз в базис вводится переменная $$x_6$$, а выводится переменная $$x_2$$, которой соответствует наименьшее значение коэффициента в столбце $$x_6$$.
После преобразования матрицы (6.14.) получаем матрицу (6.15.), отвечающую третьему плану:
$$\begin{pmatrix} 1000004\\ 0300018\\ 0-12100016\\ 020\frac{2}{3}1010 \end{pmatrix}$$.
Данный план соответствует вершине $$C$$:
$$x_1=4; x_4=0;\\ x_2=0; x_5=10;\\ x_3=16; x_6=8$$.
Критерии для данного плана равны:
$$\delta_2=-\frac{4}{5}; \delta_4 =-\frac{2}{5}$$.
Поскольку нет ни одного положительного критерия, то третий план и является оптимальным, что следует из рис. 6.1.
Целевая функция при данном плане равна:
$$y_C=13,2$$
Итак, мы пришли аналитическим путем к тому же оптимальному плану, который был ранее получен геометрическим способом.
Решение примера 6.1. можно сформулировать следующим образом.
Чтобы общие потери были минимальны, количество носителей первого типа должно быть равно 4, второго – 0, третьего – 16, четвертого 0, пятого 10, шестого – 8.
При этом потери в носителях будут составлять 13,2 единицы.
Важно отметить, что наихудший план распределения, соответствующий точке $$F$$, приводит к потерям 26,8 единиц. Таким образом, без дополнительного расходования носителей и овощей (только за счет их рационального распределения) улучшен результат решения задачи перевозки более чем в два раза.
Полученное решение – целочисленное, что, однако, не является обязательным для задач линейного программирования. В ряде случаев для получения целочисленного решения приходится прибегать к искусственным приемам, что существенно усложняет вычислительную процедуру.
Имеется $$m$$ пунктов поставщиков $$A_1,A_2,...,A_m$$ и $$n$$ пунктов назначения (потребителей) $$B_1,B_2,...,B_n$$.
$$a_i$$ — количество груза в тоннах, сосредоточенное в пункте $$A_i(i=1,2,...,m)$$ ;
$$b_j$$ — количество груза, ожидаемое в пункте $$B_j(j=1,2,...,n)$$.
Принимаем условие
$$a_1+a_2+...+a_m=b_1+b_2+...+b_n$$,
означающее, что суммарный запас груза равен суммарной потребности в нем.
$$c_{ij}$$ — стоимость перевозки одной тонны груза из пункта $$A_i$$ в пункт $$B_j$$.
$$x_{ij}$$ — количество тон груза, перевезенное из пункта $$A_i$$ в пункт $$B_j$$.
Требуется найти оптимальный план перевозок, то есть рассчитать, сколько груза должно быть отправлено из каждого пункта отправления в каждый пункт назначения, с тем условием, чтобы суммарная стоимость перевозок была наименьшей.
Неизвестными в нашей задаче являются $$mn$$ неотрицательных чисел $$x_{ij}(i=1,...,m;j=1,...,n)$$. Сведем их в таблицу 6.1, назовем ее матрицей перевозок.
| $$B_1$$ | $$B_2$$ | ... | $$B_n$$ | ||
| $$A_1$$ | $$x_{11}$$ | $$x_{12}$$ | ... | $$x_{1n}$$ | $$a_1$$ |
| $$A_2$$ | $$x_{21}$$ | $$x_{22}$$ | ... | $$x_{2n}$$ | $$a_2$$ |
| ... | ... | ... | ... | ... | ... |
| $$A_m$$ | $$x_{m1}$$ | $$x_{m2}$$ | ... | $$x_{mn}$$ | $$a_m$$ |
| $$b_1$$ | $$b_2$$ | ... | $$b_n$$ |
Запишем соотношение для пунктов поставщиков $$A_1,A_2,...,A_m$$ и пунктов потребителей $$B_1,B_2,...,B_n$$.
Будем называть уравнение 0I горизонтальными уравнениями, а 0II – вертикальными. Перевозка из $$A_i$$ и $$B_j$$ стоит $$c_{ij}x_{ij}$$, общая стоимость всех перевозок будет
$$S=\sum\limits_{i,j}c_{ij}x_{ij}$$,
где суммирование производится по всем $$i=1,...m$$ и всем $$j=1,...n$$. Таким образом, мы пришли к следующей задаче линейного программирования:
Дана система уравнений I и линейная функция II. Требуется среди неотрицательных решений системы найти такое, которое минимизирует функцию II.
Разберем метод на примере.
Пусть есть 3 пункта отправления
$$A_1,A_2,A_3$$
и 4 пункта назначения
$$B_1,B_2,B_3,B_4$$.
Запасы в пунктах отправления:
$$a_1=60,a_2=80,a_3=100$$.
Потребности:
$$b_1=40,b_2=60,b_3=80,b_4=60$$.
Занесем данные в таблицу.
| $$B_1$$ | $$B_2$$ | $$B_3$$ | $$B_4$$ | Запасы | |
| $$A_1$$ | 40 | 60 | |||
| $$A_2$$ | 80 | ||||
| $$A_3$$ Потребности |
40 | 60 | 80 | 60 | 100 |
Потребности пункта $$B_1-b_1=40$$ удовлетворены полностью и поэтому столбец, соответствующий $$B_1$$, можно временно исключить из рассмотрения, то есть переходим к таблице 3.
| $$A_1$$ | $$B_2$$ 20 |
$$B_3$$ | $$B_4$$ | $$a\prime =60-40=20$$ (так как переслали в $$B_1$$ ) |
| $$A_2$$ | 80 | |||
| $$A_3$$ | 100 | |||
| 60 | 80 | 60 |
Отметим, что и в таблице 6.3 сумма всех потребностей по-прежнему равна сумме всех запасов. К Таблице 6.3 применим тот же прием и попытаемся удовлетворить потребности $$b_2=60$$ пункта $$B_2$$.(в таблице 6.3 пункт $$B_2$$ играет роль первого) запасами $$a_1^{\prime}=20$$ пункта $$A_1$$. Очевидно, что потребности эти удается удовлетворить лишь частично, так как $$b_2 > a_1^{\prime}$$. При этом потребности $$B_2$$ сократятся до $$b_2^{\prime}=40$$, а запасы $$A_1$$ окажутся исчерпаны полностью. В силу этого строку, отвечающую $$A_1$$, из таблицы 6.3 можно временно удалить. Получим новую таблицу – таблицу 6.4, в которой имеются уже два пункта отправления $$A_2$$ и $$A_3$$ и три пункта назначения $$B_2,B_3,B_4$$.
| $$B_2$$ | $$B_3$$ | $$B_4$$ | ||
| $$A_2$$ | 40 | 80 | ||
| $$A_3$$ | 100 | |||
| 40 | 80 | 60 |
Аналогичным приемом продолжаем сокращать последовательно получаемые таблицы, пока не удовлетворим потребности всех пунктов назначения. В случае, когда новые запасы равны новым потребностям, можно исключить из таблицы по желанию строку и столбец. В процессе сокращения таблиц мы получим следующие значения для некоторых из неизвестных:
$$x_{11}=40, x_{12}=20, x_{22}=40, x_{23}=40, x_{33}=40,x_{34}=60$$.
Вписав их в таблицу 6.2, получим таблицу 6.5.
| $$B_1$$ | $$B_2$$ | $$B_3$$ | $$B_4$$ | |
| $$A_1$$ | 40 | 20 | ||
| $$A_2$$ | 40 | 40 | ||
| $$A_3$$ | 40 | 60 |
Условимся называть те клетки таблицы 6.5, в которые вписаны значения неизвестных, — базисными, а остальные клетки — свободными. Если считать, что значения неизвестных $$x_{ij}$$, которые отвечают свободным клеткам, равны нулю, то получившийся набор значений всех неизвестных дает допустимое решение рассматриваемой задачи.
Действительно, легко проверить, что сумма значений неизвестных в каждой строке таблицы равна запасу в соответствующем пункте отправления, а в каждом столбце – потребности в соответствующем пункте назначения. Поэтому уравнения I, II удовлетворяются.
В качестве примера прикладных задач
Для получения официальных документов о завершении программы дополнительного профессионального образования (удостоверения о повышении квалификации, дипломов о профессиональной переподготовке и MBA) необходимо предоставить:
Внимание! Вы можете не заказывать доставку бумажной версии официального документы, а скачать его в электронном виде и распечатать самостоятельно. Информация о выданном документе в течение 1 месяца загружается в Федеральную информационную систему «Федеральный реестр сведений о документах об образовании и (или) о квалификации, документах об обучении» - ФИС ФРДО.
Доступ на новый сайт осуществляется с использованием адреса электронной почты, который был указан вами при регистрации на "старом". Мы постарались перенести все ваши данные с прежнего ресурса, однако не исключена вероятность потери части информации.
При возникновении проблемы со входом, воспользуйтесь функцией сброса пароля
Если вы обнаружите несоответствия, пожалуйста, сообщите нам.