Общая задача линейного программирования. Симплекс-метод решения канонических задач линейного программирования

Алгоритм расчёта

Общей задачей линейного программирования (ОЗЛП) называется задача, состоящая в определении оптимально­го (максимального или минимального) значения линейной функции

                                                      (l)

при условиях

 (i=1, 2, …, m)                                            (2)

                                               (3)

где    a_ij,    c_i,    b_i – фиксированные   действительные    числа;    – один из знаков отношения: , , = .

Другими словами, в ОЗЛП ищется оптимальное значение
линейной функции (1) на множестве решений системы равенств и
неравенств (2) при условии неотрицательности некоторых переменных. Заметим, что требование неотрицательности (3) может быть на­ложено на все переменные (L = {1, 2, …, n}) или вообще отсутство­вать (L = 0).

Функция F называется линейной формой или целевой функцией задачи (1) – (3), а условия – (2) – (3) – ограничениями.

Совокупность чисел X=(x₁, x₂, ..., x_n), удовлетворяющая огра­ничениям (2) – (3), называется допустимым решением или планом задачи.

План , при котором целевая функция при­нимает минимальное или максимальное значение, называется опти­мальным.

Таким образом, при любом плане X оптимальный план X* удов­летворяет условию F(X*)F(X) (или F(X*)F(X)).

Не всякая задача линейного программирования имеет оптималь­ный план. Это связано с тем, что множество решений D систе­мы ограничений (2) – (3) может быть пустым или форма F на D не ограничена снизу (сверху).

Множество D допустимых планов задачи (1) – (3) называют многогранником решений ОЗЛП. Может оказаться, что D = 0. D представляет собой некоторое подмножество конечномерного Ев­клидова пространства R_n. Особую роль в многограннике D иг­рают его вершины, т. е. такие точки, которые не могут быть внут­ренними для любого отрезка, соединяющего две точки D. Обозна­чим множество вершин D через D₀. Элементы D₀ называются опорными планами ОЗЛП. Заметим, что D₀ всегда конечно. Извест­но, что если D₀ ≠ 0 и оптимум F существует, то он достигается хотя бы в одной из вершин D₀. В связи с этим утверждением напрашивается такой способ решения ОЗЛП: найти множест­во D₀ опорных планов и простым перебором определить требуемый оптимум F на D₀. Пусть он равен F₀ и F(X₀) = F₀ (X₀ÎD₀). Если при этом удается установить существование искомого оптимума F на D, то ясно, что он равен F₀ и X₀ – соответствующий оптималь­ный план задачи (1) – (3). Однако практически воспользоваться предложенным способом решения задачи линейного программирования затруднительно. Дело в том, что даже при относительно не большом числе ограничений и неизвестных получается астрономи­ческое количество вершин. Да и сам процесс отыскания вершин не является простой процедурой.

Симплекс-метод решения канонических задач линейного программирования называют также методом последовательного улучшения плана. А название это объясняется тем, что в отличие от простого перебора вершин и вычисления значений формы F в них в симплекс-методе сначала определяют одну из вершин D, в которых значение F ближе к оптимуму.

Список использованных источников

1. Информатика: Учеб. пособие для пед. спец. высш. учеб. заведений / А.Р. Есаян, В.И. Ефимов, Л.П. Лапицкая и др. – М.: Просвещение, 1991. 288 с.