Министерство путей сообщения РФ

САМАРСКАЯ ГОСУДАРСТВЕННАЯ АКАДЕМИЯ

ПУТЕЙ СООБЩЕНИЯ

Кафедра «Высшая математика»

Линейное программирование в задачах

строительного производства

Методические указания и контрольные задания для студентов

строительных специальностей всех форм обучения

Составители: Гуменникова Ю.В.

Маркович О.Ф.

Самара 2003

УДК 519.7

Линейное программирование в задачах строительного производства. Методические указания и контрольные задания для студентов строительных специальностей всех форм обучения.- Самара: СамГАПС, 2003.- 23 с.

Утверждено на заседании кафедры 1.10. 2003г., протокол №2.

Печатается по решению редакционно - издательского совета академии.

Методические указания составлены в соответствии с Государственным образовательным стандартом для строительных специальностей, действующей рабочей программой по курсу «Линейное программирование» и содержат основные разделы этой дисциплины: графический и симплексный методы решения задач линейного программирования, транспортную задачу.

Составители: к.ф.-м.н., доцент Гуменникова Ю.В.

доцент Маркович О.Ф.

Под редакцией к.т.н., проф. Герасимова В.А.

Рецензенты: к.ф.-м.н., доц. СамГУ Воскресенская Г.В.;

к.т.н., доц. Шур В.Л.

Подписано в печать 30.12.03. Формат 64х90 1/16.

Бумага писчая. Печать оперативная. Усл. п.л. 1.5.

Тираж 200 экз. Заказ №. 216.

© Самарская государственная академия путей сообщения, 2003.

Введение

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

Решение этих задач требует привлечения экономико- математических методов для составления и исследования математических моделей изучаемых процессов. В боль­шинстве случаев полученная математическая модель задачи требует определения наи­большего или наименьшего значения некоторой функции, которая называется целевой функцией. Эта функция, как правило, зависит от большого числа неизвестных, удовлетворяющих некоторым условиям (ограничениям), вытекающим из постановки задачи. Обычные методы математического анализа здесь не работают и было разра­ботано специальное экономико-математическое направление как раздел математики, получившее название математического программирования. Среди задач математического программирования выделяется группа, в которых целевая функция и ограничения для неизвестных линейны. Этот раздел называется линейным программированием, его методы хорошо разработаны и имеют наиболее широкое применение.

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

В основе методов линейного программирования лежат методы решения систем линейных уравнений и неравенств.

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

Основной математической моделью указанных задач является так называемая каноническая модель.

Дана система из m линейных уравнений с n неизвестными.

(1)

и целевая функция

. (2)

Среди неотрицательных решений системы (1) найти такое, при котором функция (2) будет иметь максимальное или минимальное значения.

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

Найти max или min целевой функции (2) при условии, что

(3)

Системы ограничений в форме (1) и (3) определяются конкретными условиями задач и при необходимости от одной формы легко перейти к другой.

Рассмотрим две конкретные задачи и на основе решений этих задач покажем основные методы решения любых задач линейного программирования.

Задача о рациональном использовании производительных сил

Для перевозки 3-х видов строительных материалов В₁, В₂, В₃ используется два вида машин А₁ и А₂. Грузоподъемность каждой машины, запасы строительных материалов, прибыль от эксплуатации машин каждого вида заданы в следующей таблице:

	В1	В2	В3	Прибыль
А1	7	4	3	12
А2	8	9	1	10
Запасы	474	396	174

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

Обозначим число требуемых машин вида А₁ через х₁, а вида А₂ – через х₂. Тогда должны выполняться условия (продумать!):

(4)

При этом функция (5)

должна принимать максимальное значение.

Рассмотрим два метода решения этой задачи.