КАНОНИЧЕСКАЯ ЗАДАЧА ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ КАК МАТЕМАТИЧЕСКАЯ МОДЕЛЬ

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

В математическое программирование обычно включаются задачи на максимум и минимум с ограничениями типа равенств или неравенств.

К линейному программированию относятся те задачи математического программирования, в которых и целевая функция, и ограничения линейны.

Из линейного программирования рассмотрим задачу об использовании ресурсов.

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

Математическая модель:

Найти значения , , , которые доставляют , где ,

при условиях .

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

Таблица 1

Виды товаров Виды сырья				Запасы
Цена единицы товара

Теперь построим математическую модель транспортной задачи:

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

Таблица 2

Пункты назначения Пункты отправления				Запасы
Потребность в грузе

Здесь – стоимость перевозки 1 т груза из пункта отправления в пункт назначения . Весь груз из пунктов отправления нужно перевезти в пункты назначения, поэтому .

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

Обозначим через – количество груза, предназначенного к отправлению из в , тогда придем к следующей математической модели:

Найти значения , которые доставляют , где ,

при условиях:

(Каноническая задача линейного программирования, в которой ограничения на запасы и потребности записаны в виде уравнений).

10) 1 – УСТОЙЧИВОСТЬ РЕШЕНИЙ

Устойчивость решения – очень важный практический вопрос.

Исходные данные – приближенны. При использовании ЭВМ возникают ошибки округления. Каким же образом погрешности влияют на результат?

Если малые изменения входных данных мало влияют на результат – решение устойчивое.

В противном случае таким решением пользоваться нельзя.

Пример:

X + 10*Y = 11

10X + 101*Y=111

X=1; Y=1;

 

Если же

X + 10*Y = 11,1

10X + 101*Y=111

X=11,1; Y=0;

Система плохо обусловлена, а решение неустойчивое.

Другой пример:

X + 2*Y = 39

-X + 3*Y=21

X=15; Y=12;

Если же

X + 2*Y = 39,1

-X + 3*Y=21

X=15,06; Y=12,02; - устойчивое решение.

В первом случае неустойчивость решения показывает нам необходимость технической доработки.

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