Графы и орграфы. Основные понятия

 
 
Так как в  строке F нет отрицательных элементов, то найдено оптимальное решение F=189.73 
при значениях переменных равных: X2=12.24, X1=15.3,

 
Решение многомерной  задачи

Придумаем условие  задачи:

Фирме требуется  определить объем производства каждой из красок с целью получения максимальной прибыли. Фирма производит 4 вида красок:

1. Вид 1
2. Вид 2
3. Вид 3
4. Вид 4

Используются  ингредиенты А и В, С и D.

Условия задачи представлены в виде таблицы.

Целевая функция: 
 
14X₁+5X₂+2X₃+1X₄→max 
Условия: 
 
15X₁+2X₂+8X₃+3X₄≤223 
3X₁+12X₂+5X₃+9X₄≤189 
3X₁+6X₂+7X₃+2X₄≤193 
9X₁+4X₂+3X₃+7X₄≤212

Приведем систему  ограничений к каноническому  виду, для этого необходимо неравенства  преобразовать в равенства, с  добавлением дополнительных переменных. Тогда система запишется в виде: 
15X₁+2X₂+8X₃+3X₄+s1=223 
3X₁+12X₂+5X₃+9X₄+s2=189 
3X₁+6X₂+7X₃+2X₄+s3=193 
9X₁+4X₂+3X₃+7X₄+s4=212 
Переходим к формированию исходной симплекс таблицы. В строку F таблицы заносятся коэффициенты целевой функции. Так как нам необходимо найти максимум целевой функции, то в таблицу заносятся коэффициенты с противоположным знаком. Из данных задачи составляем исходную симплекс таблицу.

 
 
Так как в столбце свободных  членов нет отрицательных элементов, то найдено допустимое решение. В  строке F имеются отрицательные элементы, это означает что полученное решение  не оптимально. Определим ведущий  столбец. Для этого найдем в строке F максимальный по модулю отрицательный  элемент: это -14 Ведущей строкой будет  та, для которой отношение решения  к соответствующему элементу ведущего столбца минимально. Ведущей строкой  является s1, а ведущий элемент: 15.

 
В строке F имеются отрицательные  элементы, это означает, что полученное решение не оптимально. Определим  ведущий столбец. Для этого найдем в строке F максимальный по модулю отрицательный  элемент - это -3.13 Ведущей строкой  будет та, для которой отношение  решения к соответствующему элементу ведущего столбца минимально. Ведущей  строкой является s2, а ведущий элемент: 11.6.

 
 
Так как в строке F нет отрицательных  элементов, то найдено оптимальное  решение F=247.14 
при значениях переменных равных: X1=13.21, X2=12.45, 
 
 
 
 
 
 

Решение транспортной задачи

Транспортную  задачу решим методом потенциалов. Для начала напишем условие. Четыре поставщика имеют следующие запасы: 90. 190, 40, 130. Требуется поставить груз с минимальными затратами трем потребителям с потребностями: 240, 100, 110. Затраты  на перевозку единицы товара даны в таблице.

 

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

 ∑ a = 90 + 190 + 40 + 130 = 450

 ∑ b = 240 + 100 + 110 = 450

 Условие баланса  соблюдается. Запасы равны потребностям. Следовательно, модель является  закрытой.

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

 Используя  метод наименьшей стоимости, построим  первый опорный план транспортной  задачи. Искомый элемент равен  2. Для этого элемента запасы  равны 40, потребности равны 110. Поскольку минимальным является 40, то вычитаем его. Следующий искомый элемент это 3. Для этого элемента запасы равны 90, а потребности 70. Поскольку минимальным является 70, то вычитаем его. Следующий искомый элемент также равен 3. Для этого элемента запасы равны 190, а потребности 240. Поскольку минимальным является 190, то вычитаем его. Следующим искомым элементов является 3. Для этого элемента запасы равны 130, а потребности 100. Поскольку минимальным является 100, то вычитаем его. Искомый элемент равен 4. Для этого элемента запасы равны 20, а потребности 50. Поскольку минимальным является 20, то вычитаем его. Искомый элемент равен 7. Для этого элемента запасы равны 30, потребности 30. Вычитаем.

 

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

 Подсчитаем  число занятых клеток таблицы,  их 6, а должно быть m + n - 1 = 6. Следовательно, опорный план является невырожденным.

Проверим оптимальность  опорного плана. Найдем потенциалы u_i, v_i. по занятым клеткам таблицы, в которых u_i + v_i = c_ij, полагая, что u₁ = 0.

U1 + v1 = 4; 0 + v1 = 4; v1 = 4

U2 + v1 = 3; 4 + u2 = 3; u2 = -1

U4 + v1 = 7; 4 + u4 = 7; u4 = 3

U4 + v2 = 3; 3 + v2 = 3; v2 = 0

U1 + v3 = 3; 0 + v3 = 3; v3 = 3

U3 + v3 = 2; 3+ u3 = 2;  u3 = -1