10. Задача линейного программирования (злп), различные формы записи.

Линейное программирование является частным разделом математического программирования. Математическое программирование – направление прикладной математики, в котором изучаются задачи условной оптимизации. В экономике такие задачи возникают при практической реализации принципа оптимальности в планировании и управлении.

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

В общем виде ЗЛП формулируется следующим образом: максимизировать (минимизировать) функцию

,

при ограничениях:

где  .

Рассмотрим матричную форму записи ЗЛП.

Введем следующие обозначения:

,  ,  ,  .

Следовательно,  и  .

Различают следующие формы записи математической модели ЗЛП:

Составные части модели	Формы записи математической модели ЗЛП
Общая	Стандартная	Каноническая
Ограничения
Управляемые переменные	Произвольного знака
Целевая функция

 

Определение 1.10. Каноническая форма называется предпочтительной или с предпочтительными переменными, если в каждое уравнение ограничений входит некоторое  с коэффициентом +1, которого нет ни в одном другом уравнении ограничений и в целевой функции.

Определение 1.11.Если дополнительно в предпочтительной канонической форме свободные члены ограничений неотрицательны ( ), то канонический вид называется допустимым, в противном случае – недопустимым.

Три формы записи ЗЛП (общая, стандартная, каноническая) эквивалентны в том смысле, что каждая из них с помощью несложных преобразований может быть сведена к другой форме.

При необходимости задачу минимизации можно заменить задачей максимизации, и наоборот, так как

(минимальное значение функции  равно максимальному значению функции  , взятому с противоположным знаком, рис. 1.1).

Рис 1.1

Неравенства типа  путем умножения левых и правых частей на –1, можно преобразовать в неравенство типа  , и наоборот.

Ограничения-неравенства  преобразуются в ограничения-равенства путем прибавления (вычитания) к левым частям дополнительных (балансовых) неотрицательных переменных  :

.

В случае необходимости ограничение-равенство  , можно записать в виде системы-неравенств:

Если в ЗЛП какая-то переменная  не подчинена условию неотрицательности, ее заменяют разностью двух других неотрицательных переменных  и  :

.

Вводимые дополнительные переменные имеют определенный экономический смысл, прямо связанный с содержанием задачи.

15. Классическая транспортная задача, ее модификации.

Транспортная задача (классическая) — задача об оптимальном плане перевозок товара со складов в пункты потребления на транспортных средствах. Для классической транспортной задачи выделяют два типа задач: критерий стоимости (достижение минимума затрат на перевозку) или расстояний и критерий времени (затрачивается минимум времени на перевозку). 

Однако в реальной жизни на нее может накладываться целый ряд дополнительных оганичений. Рассмотрим некоторые примеры:

а) Задача с избытком отправляемой продукции. Классический случай предполагает сбаллансированность объемов произведенной продукции и продукции требуемой получателями. Рассмотрим случай с избытком проиведенной продукции. Модель данной задачи представлена в ESolver2/Tr2. Как можно убедится отличие от прошлой модели заключается только в увеличении значений объемов выпускаемой продукции. Однако, как можно убедиться, SOLVER находит другое решение ( более дешевое). Постройте данную модель на отдельном листе в своем компютере и попытайтесь объяснить полученный феномен. В качестве дополнительного задания предлагается построить график остатков продукции на заводах. Анализ полученных данных позволяет сделать вывод, что транспортировка продукции с завода А3 является наименее привлекательной. Теперь предположим, что объемы складских помещений завода А3 не позволяют хранить более 100 единиц готовой продукции. Предлагаем самостоятельно решить данную задачу. Если в найденном решении суммарная стоимость перевозок будет равна 2830 у.е. , то ваше решение правильное. Обратите внимание на изменение графика и попытайтесь сделать его анализ.

б) Задачи с прямыми поставками. На практике часто бывает, что между некоторыми поставщиками и потребителями уже существует договора о прямых поставках определенного количества продукции. Пример такой модели представлен в ESolver2/Tr3. Объемы прямых поставок отражены в матрице находящейся в ячейках K8:O10. На данном рабочем листе можно увидеть решение найденное при помощи SOLVER, однако читателю прийдется найти данное решение самостоятельно, посколько данный лист защищен и не все можно увидеть.

в) Запрет маршрутов. Представим, что исходя из некоторых соображений, запрещены перевозки из завода А2 получателям В2,В3,В4. Наиболее подходящее решение заключается в искусственном завышении тарифов на соответствующие перевозки. Введите в ячейки D17, E17, F17 достаточно большие числа и запустите SOLVER, вы увидите, что данные маршруты в силу их дороговизны будут исключены из нового решения.