Integer Linear Programming

Python 3, 534 bytes

import itertools as t
import operator as o
I=float("inf")
e=lambda p,A:sum([i[0]*i[1]for i in zip(p,A[:-1])])+A[-1]
def w(x,j):
	d=len(x[0])-1;C=[0]*d;v,w=I,I
	while 1:
		L={(*n,):(sum([0 if e(n,A)<=0 else e(n,A)for A in x[:-1]]),j*e(n,x[-1]))for n in [[sum(a) for a in zip(C,c)]for c in t.product(*[[-1,0,1]]*d)]};C,P=min(L.items(),key=o.itemgetter(1))[0],C;v,w,p,q=L[C][0],L[C][1],v,w
		if(all([e(C,A)<=e(P,A)for A in x[:-1]]))*(j*(e(C,x[-1])-e(P,x[-1]))<0)+(p==v>0):return I
		if(p==v)*(q<=w):return j*q
f=lambda x:(w(x,1),w(x,-1))

Try it online!

Overview

It is an iterative algorithm, starting from the origo. It collects the neighbour positions and assigns a potential function: x:(a,b) where x is the position, a is the sum of the position's distances from the half-spaces of each linear inequality, b is the value of the objective at that position.

x:(a,b) < y:(c,d) iff a<c or a=c and b<d

The iteration stops, when:

  • the first coordinate of the potential hasn't decreased and positive: the system is infeasible
  • the distance from every half-space has decreased just like the objective: the system is unbounded.
  • none of previous and the potential hasn't decreased: it is the optimal value.