Курс лекций по линейному программированию (стр. 6 из 6)
Для расширения трех предприятий фирма выделила 5000000$. Каждое предприятие предоставляет проект в котором С – суммарные издержки, R – доходы. Цель фирмы – получить максимальную прибыли от инвестиций.
| проекты | I | II | III | |||
| C1 | R1 | C2 | R2 | C3 | R3 | |
| 1 | 0 | 0 | 0 | 0 | 0 | 0 |
| 2 | 1 | 5 | 2 | 8 | 1 | 3 |
| 3 | 2 | 6 | 3 | 9 | - | - |
| 4 | - | - | 4 | 12 | - | - |
1. Сетевая модель
Для построения сети следует определить этапы решения задач: каждому из предприятий ставят в соответствие некоторый этап, т.к. требуется выбратя оптимальный проект для каждого предприятия. Этапы связаны между собой посредством ограничений объема инвестиций.
х1 – объем инвестиций, распределяемых на первом этапе
х2 – объем инвестиций, распределяемых на первом и втором этапах
х3 – объем инвестиций, распределяемых на первом, втором и третьем этапах.
Эначение х1 и х2 – заранее неизвестны, но они могут принимать значения из 1, 2, 3, 4, 5. х3 = 5
Каждому из возможных значений х1, х2, х3 поставляется в соответствие узел, ассоциируемый с одним из этапов (j=1, j=2 j=3).
Длины дуг, соединяющие узлы на некотором этапе с узлами на последующем этапе численно равны доходам от реализации лучшего проекта. Величина (х2 – х1) = объему инвестиций, распределенных только на втором этапе, следовательно дуга х1, х2 является допустимой лишь для проектов, затраты на реализацию которых не превышают (х2 – х1) и длина этой дуги = max (R) для всех таких проектов.
Рассмотрим дугу L U
Из первого этапа во второй, следовательно между 1 и 2 предприятиями распределяет 4000000$, из них 2000000$ во второе и 2000000$ в первое.
На последнем этапе распределяется 5000000$. Из них 3000000 – в 1 и 2 предприятия; 2000000$ - в 3 предприятие.
По аналогии с сетевыми графиками максимальный доход соответствующий самому длинному пути с этапа G0 до этапа G3.
Регулентные соотношения.
Расчеты на некотором этапе осуществляются на базе сводной информации о максимальном суммарном доходе (суммарном длинном пути, полученном в результате вычисления кроме всех предшествующих этапов). Все последующие решения строятся оптимальным образом, независимо от решений, полученных на предшествующих этапах.
Это отражает сущность принципа оптимальности Баумана составляет основу вычисление схемы ДП.