Билет №31

Экономическая интерпретация взаимно двойственных задач

Экономическое содержание исходной задачи ЛП, как правило, определяет соответствующее экономическое содержание двойственной к исходной задаче.

Рассмотрим следующую ситуацию: имеется m видов ресурсов в количествах b₁,b₂,…,b_m единиц каждого ресурса. На основе этих ресурсов можно производить продукцию n различными технологическими способами. При этом за еденицу времени использования j-го технологического способа j=(1,2,…,n) расходуется a_ij единиц i-го ресурса i=1,2,…,m и производится продукция ценностью y_j единиц.

Спрашивается как оценить имеющиеся ресурсы в зависимости от технологических возможностей производства продукции?

Билет №32

Теорема (достаточное условие оптимальности опорного решения)

Пусть U_i(i=1,2,…,m), V_j (j=1,2,…,n) потенциалы опорного решения a⁰=(x_ij⁰,…,x_mn⁰) транспортной задачи ЛП. Если для всех не занятых клеток, т.е. x_ij⁰=0, i=1,2,…,m; j=1,2,…,n выполняется неравенство U_i+ V_j ≤C_ij , то спорное решение является оптимальным решением данной задачи.

Решение ТЗЛП методом потенциалов.

Шаг1. Найдём потенциалы опорного решения.

Если для любой из незаполненных клеток окажется, что U_i+ V_j ≤C_ij то это решение и является оптимальным.

Ели же найдётся клетка( r,s)для которой выполняется неравенство U_i+ V_j >C_ij то строим цикл, одна из вершин которого находится в этой клетке, а все остальные вершины находятся в ранее заполненных клетках. Такой цикл существует и притом один. Назовем его циклом пересчёта. Каждой вершине цикла пересчёта, начиная с вершины ( r,s), присвоим поочерёдно положительные и отрицательные знаки.

Среди клеток со знаком минус выберем клетку (k,l) с наименьшей величиной перевозки. Пусть x_kl=p. Тогда транспортную таблицу заполним следующим образом:

x_ij’’=x_uj’, если клетка (i,j) не является вершиной цикла пересчёта

x_ij’’=x_uj’+р, если клетке (i,j) был присвоен знак плюс

x_ij’’=x_uj’-р, если клетке (i,j) был присвоен знак минус

клетка (k,l) не заполняется.

Можно доказать что получено новое опорное решение на котором значение целевой функции будет не меньше, чем на первоначальном опорном решении.

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