![]() |
![]() |
Мастерская программиста Гирича Семёна Николаевича Решение задач линейного программирования |
|||||||||||
![]() |
|||||||||||||
|
|||||||||||||
![]() |
1. Постановка задачи |
Постановка практической задачи ЛП включает следующие основные этапы: определение показателя эффективности, переменных задачи, задание линейной целевой функции S(x), подлежащей минимизации или максимизации, функциональных hk(x), gj(x) и областных xli <xi <xui ограничений.
Приведем сейчас общую математическую формулировку основной задачи линейного программирования. Дана система т линейных уравнений с п неизвестными: a11 x1 + a11 x2 + …… + a11 xn = b1 , a21 x1 + a21 x2 + …… + a21 xn = b2 , ………………………………………… (1.1) am1 x1 + am1 x2 + …… + am1 xn = bm , и линейная функция f = c1 x1 + c2 x2 +………+ cn xn (1.2) Требуется найти такое неотрицательное решение системы x1 ≥0, x2 ≥0, … … , xn ≥0 (1.3) при котором функция f принимает наименьшее значение.
Уравнения (1.1) называют системой ограничений данной задачи; функцию f — целевой функцией (или линейной формой). Следует заметить, что систему ограничений в виде неравенств всегда можно свести к системе в виде равенств (способом введения фиктивных добавочных неизвестных). Так, если имеется ai1 x1 + ai1 x2 + …… + ai1 xn ≥ bi , то, вводя неизвестное хn+1 ≥ 0, получим ai1 x1 + ai1 x2 + …… + ai1 xn - хn+1 = bi , (Значением хn+1 в окончательном результате можно пренебречь.) Кроме того, так как min f = — max ( — f ), то любая задача на (максимизацию сводится к задаче минимизации (и наоборот). Так что постановку задачи линейного программирования в форме (1.1) — (1.3) вполне можно считать общей.
Источник:
|
|
![]() |
![]() |
![]() |
|||||
© 2011 Семён Гирич, |
|
![]() ![]() |
|||||
![]() |
![]() |
![]() |