Решение [ч. ] Теорема 38. Необходимое и достаточное условие разрешимости транспортной задачи



Скачать 91,13 Kb.
страница1/4
Дата24.04.2019
Размер91,13 Kb.
Название файлаТАНСПОРТНАЯ ЗАДАЧА 2.docx
ТипЗадача
  1   2   3   4

Транспортная задача. Опорное решение [ч.2]

Теорема 38.1 Необходимое и достаточное условие разрешимости транспортной задачи

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

Теорема 38.2 Свойство системы ограничений транспортной задачи

Ранг системы векторов-условий транспортной задачи равен N=m+n-1 (m — поставщики, n-потребители)

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

Ввиду того, что ранг системы векторов-условий транспортной задачи равен m+n — 1, опорное решение не может иметь отличных от нуля координат более m+n-1. Число отличных от нуля координат невырожденного опорного решения равняется m+n-1, а для вырожденного опорного решения меньше m+n-1

Цикл

Циклом называется такая последовательность клеток таблицы транспортной задачи (i1, j1),(i1, j2),(i2, j2),...,(ik, j1), в которой две и только две соседние клетки распложены в одной строке или столбце, причем первая и последняя клетки также находятся в одной строке или столбце.

Цикл изображают в виде таблицы транспортной задачи в виде замкнутой ломаной линии. В цикле любая клетка является угловой, в которой происходит поворот звена ломаной линии на 90 градусов. Простейшие циклы изображены на рисунке 38.1


http://www.grandars.ru/images/1/review/id/38/f191d38a23.jpg

Теорема 38.3

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

Метод вычеркивания

Метод вычеркивания позволяет проверить, является ли данное решение транспортной задачи опорным.

Пусть допустимое решение транспортной задачи, которое имеет m+n-1 отличных от нуля координат, записано в таблицу. Чтобы данное решение было опорным, векторы-условий, соответствующие положительным координатам, а также базисным нулям, должны быть линейно независимыми. Для этого занятые решением клетки таблицы должны быть расположены так, чтобы нельзя было из них образовать цикл.

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

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

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

Примеры "вычеркнутого" (опорного) и "не вычеркнутого" (не опорного решений):


http://www.grandars.ru/images/1/review/id/38/74c4bd1b38.jpg



Поделитесь с Вашими друзьями:
  1   2   3   4


База данных защищена авторским правом ©nashuch.ru 2020
обратиться к администрации

    Главная страница
Контрольная работа
Курсовая работа
Лабораторная работа
Пояснительная записка
Методические указания
Рабочая программа
Методические рекомендации
Теоретические основы
Практическая работа
Учебное пособие
Общая характеристика
Общие сведения
Теоретические аспекты
Физическая культура
Дипломная работа
Самостоятельная работа
Федеральное государственное
История развития
Направление подготовки
Методическое пособие
Общая часть
Технологическая карта
квалификационная работа
Техническое задание
Выпускная квалификационная
Общие положения
Краткая характеристика
Методическая разработка
Теоретическая часть
Исследовательская работа
Гражданское право
государственное бюджетное
Технология производства
прохождении производственной
Техническое обслуживание
Решение задач
Математическое моделирование
Организация работы
учреждение высшего
Металлические конструкции
Основная часть
Метрология стандартизация
Правовое регулирование
Практическое занятие
Понятие предмет
Технологическая часть
Технология приготовления
Экономическая теория
Образовательная программа
Общие требования
Уголовное право