Мастерская программиста Гирича Семёна Николаевича
Решение задач линейного программирования

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) вполне можно считать общей.

 

Источник:
Заварыкин В.М. и др. Численные методы: Учеб. пособие для студентов физ.-мат. спец. пед.ин-тов/В. М. Заварыкин, В. Г. Житомирский, М. П. Лапчик.—М.: Просвещение, 1990.—176 с.: ил.
Раздел: Глава 3 Элементы линейного программирования, 3.1.Постановка задачи

 


Далее: 2. Решение графическим методом

Вернуться в Начало

© 2011 Семён Гирич,
Система Orphus: Выделите текст с ошибкой и нажмите [Ctrl] + [Enter]
Назад    Вверх