Читать курсовая по финансовому менеджменту, финансовой математике: "Решения задач линейного программирования геометрическим методом" Страница 2

(Назад) (Cкачать работу)

Термин «программирование» нужно понимать в смысле «планирования». Он был предложен в середине 1940-х годов Джорджем Данцигом, одним из основателей линейного программирования, еще до того, как компьютеры были использованы для решения линейных задач оптимизации.

Математическая формулировка задачи линейного программирования Нужно максимизироватьпри условиях при i = 0, 1, 2, . . . , m .

Иногда на xi также накладывается некоторый набор ограничений в виде равенств, но от них можно избавиться, последовательно выражая одну переменную через другие и подставляя ее во всех остальных равенствах и неравенствах (а также в функции f).

Такую задачу называют "основной" или "стандартной" в линейном программировании.

Даны линейная функция Z=С1х1+С2х2+...+СNxN (1.1)

и система линейных ограниченийa11x1 + a22x2 + ... + a1NХN = b1

a21x1 + a22x2 + ... + a2NХN = b2

. . . . . . . . . . . . . . .

ai1x1 + ai2x2 + ... + aiNХN = bi (1.2) . . . . . . . . . . . . . . .

aM1x1 + aM2x2 + ... + aMNХN = bM

xj 0 (j = 1, 2, ... ,n) (1.3) где аij, bj и Сj - заданные постоянные величины.

Найти такие неотрицательные значения х1, х2, ..., хn, которые удовлетворяют системе ограничений (1.2) и доставляют линейной функции (1.1) минимальное значение.

Общая задача имеет несколько форм записи.

Векторная форма записи. Минимизировать линейную функцию Z = СХ при ограничениях А1х1 + А2x2 + ... + АNxN = Ао, X0 (1.4)

где С = (с1, с2, ..., сN); Х = (х1, х2, ..., хN); СХ - скалярное произведение; векторы A1 = A2 = ,..., AN состоят соответственно из коэффициентов при неизвестных и свободных членах.

Матричная форма записи. Минимизировать линейную функцию, Z = СХ при ограничениях АХ = А0Х0, где С = (с1, с2, ..., сN) - матрица-cтрока; А = (аij) - матрица системы; Х =(xij)- матрица-столбец, А0 = (аi) матрица-столбец

Запись с помощью знаков суммирования. Минимизировать линейную функцию Z = Сjхj при ограничениях

0пределение 1. Планом или допустимым решением задачи линейного программирования называется Х = (х1, х2, ..., хN), удовлетворяющий условиям (1.2) и (1.3).

0пределение 2. План Х = (х1, х2, ..., хN) называется опорным, если векторы А (i = 1, 2, ..., N), входящие в разложение (1.4) с положительными коэффициентами х , являются линейно независимыми.

Так как векторы А являются N-мерными, то из определения опорного плана следует, что число его положительных компонент не может превышать М.

0пределение 3. Опорный план называется невырожденным, если он содержит М положительных компонент, в противном случае опорный план называется вырожденным.

0пределение 4. Оптимальным планом или оптимальным решением задачи линейного программирования называется план, доставляющий наименьшее (наибольшее) значение линейной функции.

В дальнейшем рассмотрено решение задач линейного программирования, связанных с нахождением минимального значения линейной функции. Там, где необходимо найти максимальное значение линейной функции, достаточно заменить на противоположный знак линейной функции и найти минимальное значение последней функции. Заменяя на противоположный знак полученного минимального значения, определяем максимальное значение исходной линейной функции.

Похожие работы