Работа 1. Решение задачи распределения ресурсов

1. Цель работы

Ознакомление с решением ЗЛП симплес-методом и надстройкой Поиск решения.

2. Основные теоретические положения

Из теорем двойственности следует, что оптимальные решения прямой и двойственной задач должны удовлетворять следующим свойствам:

1) оптимальные решения следует искать среди допустимых базисных решений;

2) все производства, входящие в оптимальный план прямой задачи, должны быть рентабельными, т. е. для всех базисных переменных x_j величины Δ _j =0;

3) все производства, не входящие в оптимальный план, должны быть неприбыльными, т. е. для всех небазисных переменных x_j Δ _j ≥ 0, т. е. допустимый базисный план прямой задачи X – неоптимальный, если хотя бы для одной небазисной переменной x_j величина <0;

4) максимальное значение выручки в прямой задаче Z будет равно минимальной стоимости всех ресурсов в теневых ценах W, т. е. max Z = min W;

5) допустимый базисный план прямой задачи X будет оптимальным, если соответствующие ему двойственные переменные будут допустимым решением двойственной задачи (критерий оптимальности).

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

Поиск по сайту: