Применение методов теории графов и линейного программирования для решения производственных и технологических задач. Веткасов Н.И - 31 стр.

UptoLike

ВУЗ: 

УлГТУ | Ульяновск

Составители: 

Рубрика: 

z/
По виду коэффициентов матрицы (см. табл. 5) легко судить, является ли
найденное базисное решение допустимым и, если оно допустимо, то будет ли
оно оптимальным. Действительно, замечая, что столбец коэффициентов a
io
(i
^ 0) представляет собой базисное решение, соответствующее базису
х\
9
...
9
х'
т9
а строчка коэффициентов aqj G ^ 0) представляет собой взятые с об-
ратным знаком коэффициенты при свободных переменных в выражении (14),
приходим к выводу, что базисное решение, соответствующее базису xj,...,x'
m
,
допустимо, если а
ю
> 0. Если, кроме того, aqj > 0, то это базисное решение
является оптимальным. Очевидно также, что при оптимальном базисном
решении коэффициент аоо дает значение q^ax .
Следовательно, решение задачи линейного программирования табличным
методом заключается в нахождении на первом этапе какого-либо допустимого
базисного решения, которое в общем случае не является оптимальным, и
преобразовании первоначальной матрицы коэффициентов с целью перехода к
лучшему базисному решению.
Пример решения задачи линейного программирования табличным ме-
тодом рассмотрен ниже.
2.4.ПРИМЕР РЕШЕНИЯ ЗАДАЧИ ЛИНЕЙНОГО
ПРОГРАММИРОВАНИЯ
Максимизировать функцию прибыли от производства четырех продуктов q'
= 60xi + 70x2 + 120хз + 130x4, если затраты ресурсов на их изготовление заданы
следующими ограничениями: Xi + х
2
+ х
3
+ х
4
< 6; 4xj + 6х
2
+
*
10х
3
+ 13x4 < 100;
6xi + 5х
2
+ 4х
3
+ Зх
4
< 110.
Математическая модель задачи имеет следующий вид:
(16)

Страницы