I try to find alghoritm for this program, and can't find it.
I read in other post next scheme
w(x)=a-b*x is weight of every edge
Z(x)=0 - solution.
how understand w(x) ?
Can I solve this problem without Z(x)=0 ?

Я также хотел бы почитать про данную идею решения. На форуме есть ссылка на статью, но она на недоступном для меня английском языке.
Насколько я понял с помощью Google переводчика, на форуме обсуждается следующее:каждому ребру присваивается вес w(x)=a-x*b, a-себестоимость, b-расстояние. Рассматривается целевая функция Z(x)=Sum(a,x,E)-x*Sum(b,x,E), где E-рёбра минимального остова с весовой ф-ей w(x), x-параметр, Sum(a,x,E) = Sum(a) в E, Sum(b,x,E) = Sum(b) в E (или Z(x)=Sum(w(x) в E)).
Уверяется, что решение задачи 1447 достигается только в т.х : Z(x)=0.
Док-во (моё):
Сразу скажем, что ai,bi>0;
1)Необх.: пусть х - решение => Sum(a,E)/Sum(b,E)=x -> min => Sum(a,E)-x*Sum(b,E)=0, т.е. Z(x)=Sum(a,x,E)-Sum(b,x,E)=0
2)Дост.: пусть Z(x)=0, но y<x - решение, Ey - соответствующий набор рёбер для y;  Z(y)=0 (из 1)); в силу минимального остова 0=Z(x)=Sum(a,x,E)-x*Sum(b,x,E)<=Sum(a,x,Ey)-x*Sum(b,x,Ey)=> Sum(a,Ey)>=x*Sum(b,Ey)>y*Sum(b,Ey) => Sum(a,Ey)-y*Sum(b,Ey)=Z(y)>0 - противоречие.

Свойства:
Пусть Z(x)=0. Тогда:
1)y<x <=> Z(y)>0
2)y>x <=> Z(y)<0
(Доказывается просто)

Edited by author 22.11.2017 22:34