Аналитический способ решения задач линейного программирования

Геометрическая интерпретация симплексного метода.

Симплекс – метод решения задач Л.П.

(симплекс – это простейший, выпуклый многоугольник).

Метод является универсальным, т.к. позволяет решить практически любую задачу Л.П., записанную в каноническом виде. Идея симплексного метода (метода последовательного улучшения плана) заключается в том, что, начиная с некоторого исходного опорного решения, осуществляется последовательно направленное перемещение по опорным решениям задачи к оптимальному.

Этот метод был предложен американским ученным Данцингом и опубликован в 1951 г., хотя идеи этого метода разработал Канторович еще в 1939 г. В настоящее время название «симплекс» используется независимо от формы линейных ограничений.

Схема решения задачи симплексным методом состоит из трёх основных элементов:

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

2) при помощи признака оптимальности проверяется, не является ли это решение оптимальным.

3) По выбранному начальному решению строятся другие решения, более близкие к оптимальному.

Доказано, что таким путем через конечное число шагов (итераций) можно получить оптимальное решение задачи. В ходе решения задачи симплекс-методом можно установить является ли задача разрешимой.

Из основных теорем Л.П. следует:

1. Если задача Л.П. имеет оптимальное решение, то оно соответствует хотя бы одной угловой точке многоугольника решений и совпадает, по крайней мере, с одним из допустимых базисных решений.

2. Для этого следует перебрать конечное число допустимых базисных решений системы ограничений и выбрать среди них то, на котором целевая функция Z принимает оптимальное решение.

3. Геометрически это соответствует перебору всех угловых точек многоугольника решений.

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

ü если Z → max, то Z должно увеличиваться;

ü если Z → min, то Z должно уменьшаться.

a) Задача на максимум

Хозяйству требуется не более десяти 3-х-тонных машин и не более восьми 5-тонных. Отпускная цена машины одной марки 2 000усл.ед., другой марки 4 000усл.ед. Хозяйство может выделить для приобретения машин 40 000усл.ед. Сколько следует приобрести машин каждой марки в отдельности, чтобы их общая суммарная грузоподъемность была максимальной?

Решение. Пусть хозяйство приобрело:

х₁ – 3-х-тонных машин

х₂ – 5-тонных машин.

Тогда план покупки Х=(х₁, х₂).

Система ограничений:

- экономико-математическая модель задачи

Дата добавления: 2014-11-08