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

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

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

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

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

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

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

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

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

,

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

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

 

Таблица 7.1

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

 

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

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

Таблица 7.2

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

 

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

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

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

 

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