How to optimize for following cost function?

This is a tentative answer only. I've come up with a simple greedy algorithm, which seems to work on the few examples I've tried, but I haven't proved that it actually works in all cases. Here's the idea.

The first thing we do is check that a feasible solution exists. If so, we set $n_i=1$ for all $i$. For each $i,$ we calculate the decrease in $(b_i/n_i)\lceil n_ia_i\rceil$ that would result from increasing $n_i$ to $n_i+1,$ and we sort the records in descending order of the decrease. We choose the biggest decrease, and recalculate what the next decrease would be. Then we resort and choose the biggest decrease again, continuing until we get the sum to le $\le c.$

I did this in python, using exact rational arithmetic. That probably isn't necessary in real life, but I want to use exact values when trying to establish the correctness of the algorithm. Because it's python the fastest thing to do is to keep calling the sort function. In a systems programming language, I'd use a min-heap.

Here's my code

# optimize.py
from fractions import Fraction 
from collections import namedtuple
import sys

'''
Given positive rational numbers, C, a[i], b[i], with a[i] < 1, 1 <= i <= N,
find positive integers n[i] that minimize sum(n[i]), subject to
sum ( b[i]/n[i]* ceil(n[i]*a[i])) <= C

This problem arises in real-time scheduling.

https://math.stackexchange.com/questions/2688544/how-to-optimize-for-following-cost-function
'''
'''
Datum describes item i.  a,b are a[i], b[i], n is the current value of n[i].
value is the value of b[i]/n[i]* ceil(n[i]*a[i])
delta is the increase in the value if n[i] is increased by 1
'''
Datum = namedtuple('Datum', 'i a b n value delta'.split())

def ceiling(f):
    q, r = divmod(f.numerator, f.denominator)
    return q if r == 0 else q+1

def datum(i, a, b):
    n = 1
    value = b
    delta = value-b/2*ceiling(2*a)
    return Datum(i,a,b,n,value,delta)

def readFile(filename):
    '''
    Input file should have the following format:
    Line 1: numerator and denominator of C (ints)
    For each i, one line of 4 ints:
    a[i].numerator a[i].denominator b[i].numerator b[i].denominator
    '''
    text = open(filename).read()
    text = list(map(int, text.strip().split())) 
    if (len(text) % 4 != 2): 
        print('Need 2 inputs for C and 4 for each i')
        exit()
    C = Fraction(text[0],text[1])
    A = [Fraction(*a) for a in zip(text[2::4],text[3::4])] 
    B = [Fraction(*b) for b in zip(text[4::4] ,text[5::4])]
    data = [ ]
    for i, (a,b) in enumerate(zip(A,B)):
        data.append(datum(i,a,b))
    s = sum(d.a*d.b for d in data) 
    if s > C:
        print('Sum is %s, bound is %s No feasible solution'%(s,C))
        exit()
    return C, data

def solve(C, data):
    heat = sum(d.b for d in data)
    data.sort(key = lambda d:d.delta, reverse=True)
    while heat > C:
        d = data[0]
        heat -=d.delta
        a,b,n = d.a,d.b,d.n
        n+=1
        v = (b/n)*ceiling(n*a)
        delta = v - b/(n+1)*ceiling((n+1)*a)
        data[0] = Datum(d.i,a,b,n,v,delta)
        data.sort(key = lambda d:d.delta, reverse=True)
    data.sort(key=lambda d:d.i)
    return data

if __name__ =='__main__':
    C, data = readFile(sys.argv[1])
    data = solve(C, data)
    for d in data:
        print(d.a, d.b, d.n, ceiling(d.n*d.a))
    s = sum(d.b/d.n*ceiling(d.n*d.a) for d in data) 
    print('\nsum is %s bound is %s'%(s.__float__(), C))
    if s > C:
        print('FAILED AUDIT')   
    else:
        print('passed audit')

You'll notice that at the end, I'm printing out $\lceil n_ia_i\rceil.$ In the examples I've done so far (which are not many) this has always been $1$ for every $i$. I think this is probably true in general. I have been trying to prove it, in hopes that it will make proving the algorithm correct easier.

I want to put in a routine to test by brute force that the computed answer is actually optimal. So long as $\sum{n_i}$ isn't too big, this should be practicable.

I'll be happy to hear any thoughts you have on this.