36. Критерий оптимальности. Переход к оценочной матрице.

От матрицы затрат переходят к оценочной матрице C’, элементы которой- дельта st= C’st находят по формуле - st= C’st= Cst+Us+Vt.

Для того, чтобы некоторые опорные решения X= {Xik}, i=1,p, k=1,q транспортной задачи было оптимальным, необходимо и достаточно чтобы существовала система p+q чисел Ui и Vk, которые удовлетворяли бы критериям оптимальности:

Cik+Ui+Vk=0 - для всех занятых клеток.

Cik+Ui+Vk>0 - для всех свободных клеток.

37.Открытая модель транспортной задачи.

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

условие i=1m ai=j=1n bj

Называется закрытой моделью;

в противном случае- открытой.

Для открытой модели может быть два случая:

а) суммарные запасы превышают суммарные потребности i=1m ai > j=1n bi ;

b) суммарные потребности превышают суммарные запасы;

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

Найти минимальное значение линейной функции z = i=1m j=1n Cij Xij при ограничениях j=1n xij < ai, i=1,2,…,m,

i=1m xij=bj, j= 1,2,…,n; (случай а)

j=1n xij= ai, i= 1,2,…, m,

i=1m xij< bj, j= 1,2,…, n, (случай б)

Открытая модель решается привидением к закрытой модели .В случае (а), когда суммарные запасы превышают суммарные потребности, вводится фиктивный потребитель Вn+1, потребности которого bn+1 = i=1m ai – j=1n bi. В случае (b), когда суммарные потребности превышают суммарные запасы, вводится фиктивный поставщик Аm+1, запасы которого

am+1 = j=1n bj – i=1mai. Стоимость перевозки единицы груза как до фиктивного потребителя, так и стоимость перевозки единицы груза от фиктивного поставщика полагают равными нулю, т.к. груз в обоих случаях не перевозится.

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

38. Распределительный метод

1. Строим исходное опорное решение, при этом должны оказаться занятыми p+q-1 клеток.

2. Производим оценку свободных клеток, начиная с клетки с наименьшими затратами путем построения цикла и вычитания по этому циклу величины Δst. Если Δst<0, то переходят к следующему пункту алгоритма.

3. Перемещают по циклу число А=min{xik}, возвращаются к п.2.

4. Если Δst≥0, то оценивают следующую свободную клетку и т.д.

Если оценки всех свободных клеток окажутся неотрицательными, то оптимальное решение найдено.

При решении ТЗ распределительным методом метод подсчета оценок свободных клеток оказывается довольно трудоемким. Этого недостатка лишен метод потенциалов.

39. Постановка задачи цп.

Значительная часть экономических задач, относящихся к задачам ЛП требует целочисленного решения. Это задачи, где переменные величины обозначают количество единиц неделимой продукции. Задача целочисленного программирования формулируется так же, как и задача ЛП, но включает дополнительное требование- значения переменных в оптимальном решении должны быть целыми неотрицательными числами.

Найти min или max значение линейной функции z= j=1n Cjxj при ограничениях j=1n aijxj= bi, i=1,2,…,m,

xj-целые. xj>0, j=1,2,…,n.