In General Practitioner’s work the fundamental problem is the accuracy of the diagnosis under time constraints and health care cost limitations. The General Practitioner (GP) after an interview and a physical examination makes a preliminary diagnosis. The goal of the paper is to find the set of tests with such total diagnostic potential in verification of this diagnosis that is not smaller than a threshold value and with minimal total cost of tests. In proposed solution method, the set of preliminary diagnoses after the interview and the physical examination is given. For each preliminary diagnosis, for each test, diagnostic potential of the test in verification of the diagnosis is determined using Analytic Hierarchy Process based method with medical expert participation. Then binary linear programming problem with constraint imposed on total diagnostic potential of tests but with criterion function of minimal total test cost is solved for each diagnosis. For the case study when the patient with lumbal pain is coming to the GP, for each of six preliminary diagnoses, for each test, the diagnostic potentials of tests have been estimated. Then for each diagnosis, the solution of the binary linear programming problem has been found. A limitation of the case study is the estimation of diagnostic potential of tests by one expert only.