Презентация на тему Линейное программирование

линейного программирования называется задача, которая состоит в определений максимального

значения функции (8.6) при выполнении условий (8.8) и (8.9), где k = 0 и l = n.
Определение. Вектор X = (х1, х2,... хn)T, удовлетворяющий
ограничениям задачи (8.7)—(8.9), называется допустимым решением, или планом.
Определение. План X* = (х1*, х2*, ... хn*)T, при котором целевая функция принимает свое максимальное (минимальное) значение, называется оптимальным.
F = c1х1 + c2х2 + … + cnхn
F1 = -F = -c1х1 - c2х2 - … - cnхn
min F = max(-F)

по условию задачи отрицательна, то ее следует заменить двумя

неотрицательными переменными uk и vk, приняв xk = uk - vk.

и В предприятие использует три вида сырья. Нормы расхода

каждого вида сырья на изготовление единицы продукции данного вида приведены в табл.





Требуется определить такой план выпуска, при котором прибыль предприятия от реализации совокупности изделий будет максимальной.




Общая прибыль от реализации всей продукции составит F = 30x1 + 40x2.
Найдем решение данное! задачи, используя ее геометрическую интерпретацию. Сначала определим многоугольник решений. Для этого в неравенствах системы ограничений и условиях неотрицательности переменных следует заменить знаки неравенств знаками точных равенств и найти соответствующие прямые.

{Pj} входящих в левую часть уравнения (8.13), (8.14) с

положительными коэффициентами {xj > 0} линейно независима, то план X = (x1 , х2 , … хn)T называется опорным планом канонической задачи линейного программирования.
Определение. Опорный план X = (x1 , х2 , … хn)T называется невырожденным, если он содержит ровно m ненулевых компонент {xj > 0}, а если их меньше т, то вырожденным.

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

путём перебора вершин выпуклого многогранника в многомерном пространстве.
Нахождение решения

симплекс-методом гарантируется только в том случае, когда на каждом шаге рассматриваемый опорный план является невырожденным.

(bl - alk xl) = 0 и компоненту xl

следует исключить из опорного плана, а вместо включить компоненту хk. Базисный вектор Pl исключается, вместо него в базис включается вектор Pk. Значение функции
при этом увеличится

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

при неизвестных целевой функции, имеющие те же индексы, что

и векторы данного базиса.
В столбце Р0 записывают положительные компоненты исходного опорного плана, в нем же в результате вычислений получают компоненты оптимального плана.
Столбцы векторов Pj представляют собой коэффициенты разложения этих векторов по векторам данного базиса.
j = zj - сj. Величина zj - скалярное произведение вектора Рj на вектор Р0.

изделий A, В и С предприятие использует три различных

вида сырья. Нормы расхода сырья на производство одного изделия каждого вида, цена одного изделия, а также общее количество сырья каждого вида приведены в табл. 2.




Составить план производства изделий, при котором общая стоимость произведенной продукции будет максимальной.

Система неравенств

(8.22)

Общая стоимость произведенной предприятием продукции составляет
(8.23)
(8.24)

от ограничений-неравенств к ограничениям-равенствам. Вводим три дополнительные переменные.



Преобразованную систему

уравнений запишем в векторной форме

где


Поскольку среди векторов P1, ... P6 имеются три единичных вектора, то можно непосредственно записать опорный план X = (0,0,0,360,192,180)T, определяемый системой трехмерных единичных векторов Р4, Р5, Р6 , которые образуют базис векторного пространства.

итерации 1 и проверим исходный план на оптимальность:

Для векторов

базиса Таблица 1.1





Опорный план X не является оптимальным: имеются отрицательные числа.
Для определения вектора, подлежащего исключению, находим min(bi / ai3) при ai3 > 0, т.е. min (360/12; 192/8; 180/3) = 192/8 = 24. Таким образом, из базиса следует исключить вектор Р5. Ограничивающим фактором для производства изделий С является имеющийся объем сырья II вида. С учетом этого предприятие может выпустить 24 изделия С.

строка Р5 являются в симплекс-таблице направляющими. Составим таблицу для

итерации 2 Таблица 1.2





Для определения элементов применяем правило треугольника. Элементы можно вычислены непосредственно по формулам (8.18)—(8.21).
Вычислим число, являющееся первым элементом вектора Р0 . Для его вычисления находим три числа, расположенные:
1) в табл. 1.1 на пересечении столбца вектора Р0 и первой строки (360);
2) в табл. 1.1 на пересечении столбца вектора Р3 и первой строки (12);
3) в табл. 1.1 на пересечении столбца вектора Р0 и второй строки (24).
360 -12 • 24 = 72. Аналогично находим элементы столбцов Р1, Р2, Р5.
Новый опорный план X = (0,24,0,72,0,108)T и значения ’j и F’0