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

ЛИЧНЫЙ КАБИНЕТ 

 

Здравствуйте гость!

 

Логин:

Пароль:

 

Запомнить

 

 

Забыли пароль? Регистрация

Повышение уникальности

Предлагаем нашим посетителям воспользоваться бесплатным программным обеспечением «StudentHelp», которое позволит вам всего за несколько минут, выполнить повышение уникальности любого файла в формате MS Word. После такого повышения уникальности, ваша работа легко пройдете проверку в системах антиплагиат вуз, antiplagiat.ru, etxt.ru или advego.ru. Программа «StudentHelp» работает по уникальной технологии и при повышении уникальности не вставляет в текст скрытых символов, и даже если препод скопирует текст в блокнот – не увидит ни каких отличий от текста в Word файле.

Работа № 43568


Наименование:


Контрольная Постановка транспортной задачи

Информация:

Тип работы: Контрольная. Предмет: Программирование. Добавлен: 19.11.2012. Сдан: 2012. Уникальность по antiplagiat.ru: < 30%

Описание (план):


Федеральное агентство по образованию
ГОУ ВПО «Удмуртский государственный университет»
Институт экономики и управления
Кафедра УСЭС







Контрольная работа №1
По предмету ЭММиМ
По теме: Транспортная задача линейного программирования








Выполнил:
студент гр.610-31
Проверил:
доцент








Ижевск, 2012

Содержание
Введение
1.Постановка и основные свойства транспортной задачи ……………
2. Модели транспортной задачи …………………………………………
2.1. Закрытая модель транспортной задачи ……………………..
2.2. Открытая модель транспортной задачи …………………….
3. . Теорема существования. Двойственная транспортная задача ……...
Заключение………………………………………………………………….














Введение
Транспортная задача линейного программирования получила в настоящее время широкое распространение в теоретических обработках и практическом применении на транспорте и в промышленности. Особенно важное значение она имеет в деле рационализации постановок важнейших видов промышленной и сельскохозяйственной продукции, а также оптимального планирования грузопотоков и работы различных видов транспорта.
Кроме того, к задачам транспортного типа сводятся многие другие задачи линейного программирования - задачи о назначениях, сетевые, календарного планирования.
Цель заданной работы - освоить математическую постановку транспортной задачи линейного программирования.











1. Постановка и основные свойства транспортной задачи
Классическая транспортная задача ЛП формулируется следующим образом.
Имеется m пунктов производства (поставщиков) и n пунктов
потребления (потребителей) однородного продукта. Заданы величины:
- объем производства (запас) i-го поставщика, i=1, m ;
- объем потребления (спрос) j-го потребителя, i=1, n ;
- стоимость перевозки (транспортные затраты) единицы продукта от i-го поставщика к j-му потребителю.
Требуется составить такой план перевозок, при котором спрос
всех потребителей был бы выполнен и при этом общая стоимость всех
перевозок была бы минимальна.
Математическая модель транспортной задачи имеет вид (1)
Транспортная задача, в которой суммарные запасы и суммарные потребности совпадают, называется закрытой моделью; в противном случае - открытой. Открытая модель решается приведением к закрытой. В случае, когда суммарные запасы превышают суммарные потребности, т.е. вводится фиктивный n+1 потребитель, потребности которого .
В случае, когда суммарные потребности превышают суммарные запасы, т.е. , вводится фиктивный m+1 поставщик, запасы которого .
Стоимость перевозки единицы груза как до фиктивного потребителя, так и стоимость перевозки единицы груза от фиктивного поставщика полагают равными нулю, так как груз в обоих случаях не перевозится.
Прежде чем решать транспортную задачу, необходимо проверить, к какой модели она принадлежит, и если необходимо, то привести ее к
закрытой модели.
Основные свойства транспортной задачи
Математические модели любых транспортных задач ЛП обладают общими чертами, а именно,
1) коэффициенты целевой функции неотрицательны (стоимости перевозок не могут быть отрицательными величинами);
2) коэффициенты правых частей ограничений неотрицательны (запасы и потребности продукта);
3) коэффициенты в ограничениях принимают только два значения, это нули и единицы.
В силу этих особенностей транспортная задача обладает следующими свойствами.
Теорема 1.
Базисное решение закрытой модели транспортной задачи содержит m+n-1 базисных компонент.
Доказательство.
Количество базисных компонент определяется число линейно-независимых ограничений задачи. В транспортной задаче не все m+n ограничений линейно-независимы.
Действительно, сложив первые m ограничений и следующие n ограничений задачи, получим

Но в закрытой модели выполняется балансовое равенство

поэтому получаем, что нетривиальная линейная комбинация строк ограничений (линейная комбинация с ненулевыми коэффициентами) равна нулю. Это означает, что среди ограничений задачи есть линейно-зависимое ограничение. Следовательно, число линейно-независимых ограничений равно m+n-1 и базис задачи состоит из m+n-1 компонент.
Теорема доказана
В силу специфики содержательной постановки транспортной задачи допустимое решение называется планом, базисное допустимое решение называется опорным планом, оптимальное решение называется оптимальным планом.
Теорема 2.
Оптимальный план закрытой модели транспортной задачи существует всегда.
Доказательство.
Оптимальное решение задачи ЛП существует, если, во-первых, существует допустимое решение и, во-вторых, целевая функция ограничена на этом допустимом решении.
Покажем существование допустимого решения. Так как суммарные запасы совпадают с суммарными потребностями , то всегда можно найти такой план перевозок, который будет допустимым решением (все запасы вывозятся и все потребности выполняются в силу балансового равенства).
Покажем ограниченность целевой функции. Так как
следовательно L ограничена снизу нулем для всех допустимых решений.
Теорема доказана









2. Модели транспортной задачи
2.1. Закрытая модель транспортной задачи
Для доказательства теоремы необходимо показать, что при заданных условиях существует хотя бы один план задачи и линейная функция на множестве планов ограничена.
Доказательство. Пусть = M > 0.
Тогда величины xij = aibj /M (i = 1,2,3, ... m; j = 1,2,3, ..., n) являются планом, так как они удовлетворяют системе ограничений
(1)
(2)
Действительно, подставляя значения в (1) и (2) , находим
= ai ,
= bj .
Выберем из значений Cij наибольшее C¢ = max Cij и заменим в линейной функции все коэффициенты на C¢ тогда, учитывая что (1) , получим
,
Выберем из значений Cij наименьшее C¢¢=min Cij и заменим в линейной функции все коэффициенты на C¢¢ ; тогда, учитывая ( 1) имеем
Объединяя два последних неравенства в одно двойное , окончательно получаем C¢¢M ? Z ? C¢ M, т. е. линейная функция ограничена на множестве планов транспортной задачи.



Подать заявку на покупку Контрольная по Программированию

Ваше предложение по стоимости за работу: