Программа решения транспортной задачи с неправильным балансом

Размещено на http://www.allbest.ru/

Содержание

Аннотация

Введение

1. Экономико-математическая модель задачи

1.1 Экономико-математическая модель задачи

1.2 Примеры задачи линейного программирования

1.3 Общая задача линейного программирования

2. Решение транспортной задачи

2.1 Метод севера - западного угла

2.2 Метод наименьших затрат

2.3 Метод потенциалов

Заключение

Список использованной литературы

Приложение

Аннотация

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

Введение

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

B данной дипломной работе рассмотрены вопросы:

Этапы составления экономико-математической модели;

Примеры задач линейного программирования;

Общая задача линейного программирования;

?Математическая модель транспортной задачи (виды транспортных задач).

? Метод севера -- западного угла;

? Метод наименьших затрат;

? Метод потенциалов.

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

1. Экономико-математическая модель задачи

1.1 Экономика-математическая модель задачи

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

Экономико-математическая модель - математическое описание исследуемого экономического процесса в абстрактном виде с помощью математических соотношений.

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

Экономический анализ расширить область экономической информации, интенсифицировать экономические расчеты.

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

Процедура экономико-математическое моделирование заменяет дорогостоящие и трудоемкие натуральные эксперименты расчетами.

Действительно, при использовании экономико-математических методов достаточно быстро и дешево производится на ЭВМ сравнение многочисленных вариантов планов и управленческих решений. В результате отбираются наиболее оптимальные варианты. Ниже рассматриваются примеры экономико-математических моделей.

1.2 Примеры задач линейного программирования

1. Задача об использование ресурсов (задача планирование производства).

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

Вид ресурса	Запас ресурса	Число единиц ресурсов, затрачиваемых на изготовление единицы продукции
	18 16 5 21	1 2 - 3	3 1 1 -

Прибыль, получаемая от единицы продукции и , -соответственно 2 и 3 руб.

Необходимо составить такой план производства продукции, при котором прибыль от ее реализации будет максимальной.

Решение. Составим экономико-математическую модель задачи.

Обозначим - число единиц продукции соответственно и , запланированных и производству. Для их изготовления (см. таб. 1) потребуется единиц ресурса , единиц ресурса , единиц ресурса и единиц ресурса . Так как потребление ресурсов и не должно превышать их запасов, соответственно 18, 16, 5 и 21 единицы, то связь между потреблением ресурсов и их запасами выразится системой неравенств.

(1)

По смыслу задачи переменные

(2)

Суммарная прибыль составит руб. от реализации продукции и руб. - от реализации продукции т.е.

(3)

Итак, экономико-математическая модель задачи: найти такой план выпуска продукции X=(х₁, x₂), удовлетворяющий системе (1), и условию (2), при котором функция (3) принимает максимальное значение.

Задачу легко обобщить на случай выпуска n видов продукции с использованием m видов ресурсов.

Обозначим - число единиц продукции , запланированной к производству; ? запас ресурса , ? число единиц ресурса затрачиваемого на изготовление единицы продукции (числа часто называют технологическими коэффициентами); -прибыль от реализации единицы продукции .

Тогда экономико-математическая модель задачи об использовании ресурсов в общей постановке примет вид: найти такой план выпуска продукции, удовлетворяющий системе

(4)

и условию

(5)

При котором функция

(6)

принимаем максимальное значение

2. Задача составление рациона (задача о диете, задача о смесях).

1.2 Имеется два вида корма I и II, содержащие питательные вещества витамины) . Содержание числа единиц питательных веществ в 1кг каждого вида корма и необходимый минимум питательных веществ приведены в табл. (цифры условные).

Питательное вещество (витамин)	Необходимый минимум питательных веществ	Число единиц питательных веществ в 1 кг корма
		I	II
	9 8 12	3 1 1	1 2 6

Стоимость 1 кг корма I и II соответственно равна 4 и 6 руб.

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

Решение. Составим экономико-математическую модель задачи.

Обозначим ? количество корма I и II, входящих в дневной рацион. Тогда этот рацион (см. табл.) будет включать единиц питательных веществ , единица веществ , и единица питательных веществ . Так как, содержание питательных веществ , и , в рационе должно быть не менее 9, 8 и 12 единиц соответственно, то получим систему неравенств:

(7)

Кроме того, переменные

(8)

Общая стоимость рациона составит (в руб.)

(9)

Итак, экономико-математическое модель задачи: составить дневной рацион , удовлетворяющий системе (7) и условию (8), при котором функция (9) принимает минимальное значение.

Для формулировки задачи в общей постановке обозначим ? число единиц корма n-го вида; -- необходимый минимум содержание в рационе питательного вещества -- число единиц питательного вещества в единицы корма j-го вида; -- стоимость единицы корма j- го вида. Тогда экономико-математическая модель задачи примет вид: программирование транспортный математический

Найти такой рацион , удовлетворяющий системе

(10)

И условию

(11)

При котором функция

(12)

Принимает максимальное значение.

Задача об использовании мощностей (задача о загрузке оборудования)

Предприятию задан план производство продукции по времени номенклатуре: требуется за время T выпустить единиц продукции . Продукции производиться на станках .

Для каждого станка известны производительность (т.e. число единиц продукции , которая можно произвести на станке ) и затраты на изготовление продукции на станке в единицу времени.

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

Составить экономико-математическую модель задачи. Обозначим ? время, в течение которого станок будет занять изготовление продукции .

Так как время работы каждого станка ограниченно и не превышает T, то справедливы неравенства:

(13)

Для выполнения плана выпуска по номенклатуре необходимо, чтобы выполнялись следующие равенства:

(14)

Кроме того,

(15)

затраты на производства всей продукции выразятся функцией

(16)

Экономико-математическая модель задачи об использовании мощности примет вид: найти такое решение , удовлетворяющие системам (13) и (14) и условию (15), при котором (16) принимает минимальное значение.

Задача о раскрое материалов.

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

Необходимо найти план раскроя, обеспечивающий максимальное число комплектов

Составим экономико-математическую модель задачи.

Обозначим - число единиц материала, раскраиваемых i-м способом, и ? число изготавливаемых комплектов изделий.

Так как общее количество материала равно сумме его единиц, раскраиваемых различными способами, то

(17)

Требование комплектности выразиться уравнениями

(18)

Очевидно, что

(19)

Экономико-математическая модель задачи: найти такое решение , удовлетворяющие системе уравнение (17) ? (18) и условие (1.19), при котором функция принимает максимальное значение.

Рассмотрим задачу:

Для изготовления брусьев длиной 1,2 м., З м. и 5 м. в соотношение 2:1:3 на распил поступают 195 бревен длиной 6 м. определить план распила, обеспечивающий максимальное число комплектов. Составить экономико-математическую модель задачи.

Решение: Прежде всего определим всевозможные способы распила бревен, указав соответствующее число получаемых при этом брусьев (таб.).

Способ распила	Число получаемых брусьев длиной, м.
	1,2	3,0	5,0
1 2 3 4	5 2 - -	- 1 2 -	- - - 1

Обозначим: ? число бревен, распиленных i-м способом (; ? число комплектов брусьев.

Учитывая, что все бревна должны быть распилены, а число брусьев каждого размера должно удовлетворять условию комплектности, экономико--математическая модель задачи примет вид:

При ограничениях:

Задачу о раскрое легко обобщить на случай раскраиваемых материалов.

Пусть каждая единица j-го материала может быть раскроена различными способами, причем использование i- го способа дает единиц k-го изделия , а запас j-го материала равен единиц.

Обозначим -- число единиц j- го материала, раскрываемого i-м способом.

Экономико-математическая модель задачи о раскрое в общей постановке примет вид: найти такое решение , удовлетворяющее системе

И условию , при котором функция принимает максимальное значение.

1.3 Общая задача линейного программирования

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

Дана система линейных уравнений и неравенства с переменными

(20)

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

(21)

Необходимо найти такое решение системы , где

(22)

При котором линейная функция принимает оптимальное (т.е. максимальное или минимальное) значение.

Система (20) называется системой ограничений, а функция ? линейной функцией, линейной формой, целевой функцией или функцией цели.

Более кратко общую задачу линейного программирования можно представить в виде:

При ограничениях:

Оптимальное решение (или оптимальным планом) задачи линейного программирования называется решение система ограничений (20), удовлетворяющее условию (22), при котором линейная функция (21) принимает оптимальное (максимальное или минимальное) значение.

Термины «решение» и «план» ? синонимы, однако первый используется чаще, когда речь идет о формальной стороне задачи (ее математическая решении), а второй -- содержательной стороне (экономической интерпретации).

При условии, что все переменные неотрицательны , система ограничений (20) состоит лишь из одних неравенств, ? такая задача линейного программирования называется стандартной; если система ограничений состоит из одних уравнений, то задача называется канонической. Так, в приведенных выше примерах задач линейного программирования задачи 1 и 2 ? стандартные, задача 4 --каноническая, а задача 3 -- общая.

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

Теорема 1.1. всякую решению неравенства

(23)

Соответствует определенное решение уравнения

(24)

В котором

(25)

И, наоборот, каждому решению уравнения (24) и неравенства (25) соответствует определенное решение неравенства (23).

Используя эту теорему (которую принимаем без доказательство ), представим в качестве примера стандартную задачу (4)-(6) в каноническом виде. С той целью в каждое из неравенств системы ограничений (4) введем дополнительные неотрицательные переменные и система ограничений (4) примет вид:

(26)

Таким образом, стандартная задача (4) - (6) в канонической форме: найти такое решение , удовлетворяющее системе (26) и условию (5), пи котором функция (6) принимает максимальное значение.

Замечание. B рассматриваемой задаче все неравенства вида « ? » , поэтому дополнительные неотрицательные переменные вводились со знаком «+», в случае неравенства вида «?», соответствующие дополнительные переменные следовало бы ввести со знаком «?».

Опорный план транспортной задачи.

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

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

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

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

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

Известны ? стоимости перевозки единицы груза от каждого поставщика j-му потребителю. Требуется составить такой план перевозок, при котором запасы всех поставщиков вывозятся полностью, запросы всех потребителей удовлетворяются полностью и суммарные затраты на перевозку всех грузов минимальны. Исходные данные транспортной задачи записываются в таблице вида:

Переменными (неизвестными) транспортной задачи являются ? объемы перевозок от каждого i-го поставщика каждому j-му потребителю. Эти переменные могут быть записаны в виде матрицы перевозок:

.

Математическая модель транспортной задачи в общем случае имеет вид:

(27)

(28)

(29)

(30)

Целевая функция задачи (27) выражает требование обеспечить минимум суммарных затрат на перевозку всех грузов. Первая группа из уравнений (28) описывает тот факт, что запасы всех поставщиков вывозятся полностью. Вторая группа из уравнений (29) выражает требование полностью удовлетворить запросы всех потребителей. Неравенство (30) является условиями не отрицательности всех переменных задачи. Таким образом, математическая формулировка транспортной задачи состоит в следующем: найти переменные задачи

Удовлетворяющие системе ограничений (28), (29), условиям не отрицательности (30) и обеспечивающие минимум целевой функции (27).

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

(31)

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

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

Рассмотрим задачу:

Решение:

Введем переменные задачи (матрицы перевозок)

Запишем матрицу стоимостей

Целевая функция задачи равна сумме произведений всех соответствующих элементов матриц и :

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

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

Это означает, что запасы поставщиков вывозятся полностью.

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

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

Ответ: математическая модель задачи формулируется следующим образом: найти переменные задачи, обеспечивающие минимум функции

и удовлетворяющие системе ограничений

И условиям не отрицательности

2. Решение транспортной задачи

2.1 Метод севера - западного угла

При нахождении опорного плана транспортной задачи методом севера ? западного угла на каждом шаге рассматривает первый из оставшихся пунктов отправления их первый из оставшихся пунктов назначения. Заполнения таблицы клеток условий начинается с левой верхней клетки для неизвестного («севера ? западного угла») и заканчивается клеткой для неизвестного , идет как бы по диагонали таблицы.

Рассмотрим задачу: на три базы поступил однородный груз в количествах, соответственно 140, 180, и 160 ед. Этот груз требуется перевести в пять пунктов назначения 60, 70, 120, 130, и 100 ед. тарифы перевозок единицы груза каждого из пунктов отправления в соответствующие пункты назначения указаны в следующей таблице:

Пункты отправления	Пункты назначения	запасы
	2 8 9	3 4 7	4 1 3	2 4 7	4 1 2	140 180 160
потребности	60	70	120	130	100	480

Найти план перевозок данной транспортной задачи методом севера ? западного угла.

Решение: здесь число пунктов отправления , а число пунктов назначения . Следовательно, опорный план задачи определяется числами, стоящими 5+3-1=7 заполненными клетками.

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

Пункты отправления	Пункты назначения	запасы
	2 60 8 9	3 70 4 7	4 10 1 110 3	2 4 70 7 60	4 1 2 100	140 180 160
потребности	60	70	120	130	100	480

Рассмотрим первый из оставшихся пунктов отправления и назначения , запасы пункта больше потребности пункта , положим , запишем этот значения в соответствующей клетке таблице и временно исключим из рассмотрения столбец . B пункте запасы считаем равными 10 ед. Снова рассмотрим первый из оставшихся пунктов отправления и назначения , потребности пункта больше оставшихся запасов пункта . Положим , исключим из рассмотрения строку , значения запишем в соответствующую клетку таблицу 6 и считаем потребности пункта равными 110 ед.

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

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

2.2 Метод наименьших затрат

Данный метод позволяет построить опорное решение, которое достаточно близко к оптимальному, так как использует матрицу стоимости транспортной задачи Как и метод севера ? западного угла, он состоит ряда однотипных шагов , на каждом из которых заполняется только одно клетка таблицы, соответствующая минимальной стоимости , и исключается из рассмотрения только одно строка (поставщик) или один столбец (потребитель). Очередную клетку, соответствующую , заполняет по тем же правилом, что и метод севера ? западного угла. Поставщик исключается из рассмотрения, если его запасы заканчиваются. Потребитель исключается из рассмотрения, если его запросы удовлетворенны полностью. На каждом шаге исключается либо один поставщик, либо один потребитель. При этом если поставщик не исключен, но его запасы равны нулю, то на том шаге, когда от него требуется поставить груз, в соответствующую клетку таблицы заноситься базисный нуль и лишь, затем поставщик исключается из рассмотрения. Аналогично поступает с потребителем.

Рассмотрим задачу:

Используя метод минимальной стоимости, построить начальное опорное решение транспортной задачи, исходные данные таковы:

	80	120	160	120
120	1	3	4	2
160	4	5	8	3
200	2	3	6	7

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

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

	80	120	160	120
120	1 80	3	4	2 40
160	4	5	8 80	3 80
200	2	3 120	6 80	7

В оставшееся часть матрицы C, наименьший является стоимость . Максимальная возможная перевозка, которую можно осуществить от первого поставщика к четвертому потребителю, равны . B соответствующей клетке таблицы записываем перевозку . Запасы первого поставщика исчерпаны, исключаем его из рассмотрения. B матрице C вычеркиваем первую строку. Запросы четвертого потребителя уменьшаем на 40, .

В оставшемся части матрицы C минимальная стоимость . Заполняем одну из двух клеток таблицы. Пусть в клетку (2, 4) запишем . Запросы четвертого потребителя удовлетворены полностью, исключаем его из рассмотрения, вычеркиваем четвертый столбец матрицы C. Уменьшаем запасы второго поставщика .

В оставшемся части матрицы C минимальная стоимость . Запишем в клетку таблицы (3,2) перевозку . Исключаем из рассмотрения второго потребителя, а из матрицы C второй столбец. Вычисляем .

В оставшемся части матрицы C наименьшая стоимость . Запишем в клетку таблицы (3,3) перевозку . Исключаем из рассмотрения третьего поставщика, а из матрицы C третью строку. Определяем .

B матрице C остался единственный элемент . Записываем в клетку таблицы (2, 3) перевозку . Проверяем правильность построения опорного решения. Число занятых клеток таблицы равно . Применяя метод вычеркивания, проверяем линейную независимость векторов условий, соответствующих положительным координатам решения.

2.3 Метод потенциалов

Широко распространенным методом решения транспортных задач метод потенциалов.

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

при , (32)

при . (33)

Группа равенств (32) используется как система уравнений для нахождения потенциалов. Данная система уравнений имеет неизвестных и . Число уравнений системы, как и число отличных от нуля до координат невырожденного опорного решения, равно . Так, как число неизвестных системы на единицу больше числа уравнений, то одной из них можно задать значение произвольно, а остальные найти из системы.

Группа неравенств (33) используется для проверки оптимальности опорного решения. Эти неравенства удобнее представить в следующем виде:

при (34)

Числа называются оценками для свободных клеток таблицы (векторов условий) транспортной задачи.

Опорное решение является оптимальным, если для всех векторов условий (клеток таблицы) оценки неположительные.

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

Особенности решения транспортных задач c неправильным балансом:

1. Если суммарные запасы поставщиков превосходят суммарные запросы потребителей, т. e.

, (35)

то необходимо ввести фиктивного ? го потребителя c запросами

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

2. Если суммарные запросы потребителей превосходят суммарные запасы поставщиков, т. e.

, (36)

то необходимо ввести фиктивного -го поставщика c запасами , равными разности суммарных запросов потребителей и запасов поставщиков, и нулевыми стоимостями перевозок единиц груза .

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

Составление опорного плана. Решение транспортной задачи начинается с нахождения опорного плана. Для этого существуют различные способы. Например, способ «северо-западного угла", способ минимальной стоимости по строке, способ минимальной стоимости по столбцу и способ минимальной стоимости таблицы. Рассмотрим простейший, так называемый способ «северо-западного угла». Пояснить его проще всего будет на конкретном примере:

Условия транспортной задачи заданы транспортной таблицей.

ПН ПО						Запасы
	10	8	5	6	9	48
	6	7	8	6	5	30
	8	7	10	8	7	27
	7	5	4	6	8	20
Заявки	18	27	42	12	26	125

Будем заполнять таблицу перевозками постепенно, начиная c левой верхней ячейки ("северо-западного угла" таблицы). Будем рассуждать при этом следующим образом. Пункт подал заявку на 18 единиц груза. Удовлетворим эту заявку за счёт запаса 48, имеющегося в пункте , и запишем перевозку 18 в клетке (1,1). После этого заявка пункта удовлетворена , a в пункте осталось ещё 30 единиц груза. Удовлетворим за счёт них заявку пункта (27 единиц), запишем 27 в клетке (1,2); оставшиеся 3 единицы пункта назначим пункту . B составе заявки пункта остались неудовлетворёнными 39 единиц. Из них 30, покроем за счёт пункта , чем его запас будет исчерпан, и ещё 9 возьмём из пункта . Из оставшихся 18 единиц пункта , 12 выделим пункту ; оставшиеся 6 единиц назначим пункту , что вместе со всеми 20 единицами пункта покроет его заявку. На этом распределение запасов закончено; каждый пункт назначения получил груз, согласно своей заявки. Это выражается в том, что сумма перевозок в каждой строке равна соответствующему запасу, a в стол6це -- заявке. Таким образом, нами сразу же составлен план перевозок, удовлетворяющий балансовым условиям. Полученное решение является опорным решением транспортной задачи:

ПН ПО						Запасы
	10 18	8 27	5 3	6	9	48
	6	7	8 30	6	5	30
	8	7	10 9	8 12	7 6	27
	7	5	4	6	8 20	20
Заявки	18	27	42	12	26	125

Составленный нами план перевозок, не является оптимальным по стоимости, так как при его построении мы совсем не yчитывали стоимость перевозок .

Другой способ -- способ минимальной стоимости по строке -- основан на том, что мы распределяем продукцию от пункта не в любой из пунктов , а в тот, к которому стоимость перевозки минимальна. Если в этом пункте заявка полностью удовлетворена, то мы убираем его из расчетов и находим минимальную стоимость перевозки из оставшихся пунктов . Во всем остальном этот метод схож c методом "северо-западного угла". B результате, опорный план, составленный способом минимальной стоимости по строке, выглядит как показано в таблице.

При этом методе может получиться, что стоимости перевозок и от пункта к пунктам и , равны. В этом случае, c экономической точки зрения, выгоднее распределить продукцию в тот пункт, в котором заявка больше. Так, например, в строке 2: , но заявка больше заявки , поэтому 4 единицы продукции мы распределим в клетку (2,1).

ПН ПО						Запасы
	10	8	5 42	6 6	9	48
	6 4	7	8	6	5 26	30
	8	7 27	10	8	7 0	27
	7 14	5	4	6 6	8	20
Заявки	18	27	42	12	26	125

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

Клетки таблицы, в которых стоят ненулевые перевозки, являются базисными. Их число должно равняться . Необходимо отметить также, что встречаются такие ситуации, когда количество базисных клеток меньше чем . B этом случае распределительная задача называется вырожденной. И следует в одной из свободных клеток поставить количество перевозок равное нулю.

,

а базисных клеток 7, поэтому нужно в одну из клеток строки 3 или столбца 2 поставить значение "0". Например в клетку (3,5).

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

Распределительный метод достижения оптимального плана

Теперь попробуем улучшить план, составленный способом "северо-западного угла". Перенесем, например, 18 единиц из клетки (1,1) в клетку (2,1) и чтобы не нарушить баланса перенесём те же 18 единиц из клетки (2,3) в клетку (1,3). Получим новый план. Подсчитав стоимость опорного плана (она ровняется 1039) и стоимость нового плана (она ровняется 913) нетрудно убедиться что стоимость нового плана на 126 единиц меньше. Таким образом, за счёт циклической перестановки 18 единиц груза из одних клеток в другие нам удалось понизить стоимость плана:

ПН ПО						Запасы
	10	8 27	5 21	6	9	48
	6 18	7	8 12	6	5	30
	8	7	10 9	8 12	7 6	27
	7	5	4	6	8 20	20
Заявки	18	27	42	12	26	125

На этом способе уменьшения стоимости в дальнейшем и будет основан алгоритм оптимизации плана перевозок. Циклом в транспортной задаче мы будем называть несколько занятых клеток, соединённых замкнутой ломанной линией, которая в каждой клетке совершает поворот на 90°.

Нетрудно убедиться, что каждый цикл имеет чётное число вершин и значит, чётное число звеньев (стрелок). Условимся отмечать знаком "+" те вершины цикла, в которых перевозки необходимо увеличить, а знаком «?» те вершины, в которых перевозки необходимо уменьшить. Цикл с отмеченными вершинами будем называть «означенным». Перенести какое-то количество единиц груза по означенному циклу ? это значит увеличить перевозки, стоящие в положительных вершинах цикла, на это количество единиц, а перевозки, стоящие в отрицательных вершинах уменьшит на то же количество. Очевидно, при переносе любого числа единиц по циклу равновесие между запасами и заявками не меняется: по прежнему сумма перевозок в каждой строке равна запасам этой строки, а сумма перевозок в каждом столбце?заявке этого столбца. Таким образом при любом циклическом переносе, оставляющем перевозки неотрицательными допустимый план остается допустимым. Стоимость же плана при этом может меняться: увеличиваться или уменьшатся. Назовем ценой цикла увеличение стоимости перевозок при перемещении одной единицы груза по означенному циклу. Очевидно, цена цикла равна алгебраической сумме стоимостей, стоящих в вершинах цикла, причем, стоящие в положительных вершинах берутся со знаком "+", а в отрицательных со знаком «?». Обозначим цену цикла через . При перемещении одной единицы груза по циклу стоимость перевозок увеличивается на величину . При перемещении по нему единиц груза стоимость перевозок увеличиться на . Очевидно, для улучшения плана имеет смысл перемещать перевозки только по тем циклам, цена которых отрицательна. Каждый раз, когда нам удается совершить такое перемещение, стоимость плана уменьшается на соответствующую величину . Так как перевозки не могут быть отрицательными, мы будем пользоваться только такими циклами, отрицательные вершины которых лежат в базисных клетках таблицы, где стоят положительные перевозки. Если циклов с отрицательной ценой в таблице больше не осталось, это означает, что дальнейшее улучшение плана невозможно, то есть оптимальный план достигнут. Метод последовательного улучшения плана перевозок в том, что в таблице отыскиваются циклы с отрицательной ценой, по ним перемещаются перевозки, и план улучшается до тех пор, пока циклов с отрицательной ценой уже не останется. При улучшении плана циклическими переносами, как правило, пользуются приемом, заимствованным из симплекс-метода: при каждом шаге (цикле) заменяют одну свободную переменную на базисную, то есть заполняют одну свободную клетку и взамен того освобождают одну из базисных клеток. При этом общее число базисных клеток остается неизменным и равным . Этот метод удобен тем, что для него легче находить подходящие циклы.

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

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

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

Решение транспортной задачи методом потенциалов. Транспортная задача с правильным балансом.

Этот метод позволяет автоматически выделять циклы c отрицательной ценой и определять их цены.

Пусть имеется транспортная задача c балансовыми условиями

,

причем -- то есть закрытая задача.

Стоимость перевозки единицы груза из в равна ; таблица стоимостей задана. Требуется найти план перевозок , который удовлетворял бы балансовым условиям и при этом стоимость всех перевозок была минимальна.

Идея метода потенциалов для решения транспортной задачи сводиться к следующему. Представим себе, что каждый из пунктов отправления вносит за перевозку единицы груза (всё ровно куда) какую-то сумму ; в свою очередь каждый из пунктов назначения также вносит за перевозку груза (куда угодно) сумму . Эти платежи передаются некоторому третьему лицу ("перевозчику"). Обозначим и будем называть величину "псевдостоимостью" перевозки единицы груза из в . Заметим, что платежи и не обязательно должны быть положительными; не исключено, что "перевозчик" сам платит тому или другому пункту какую-то премию за перевозку. Также надо отметить, что суммарная псевдостоимость любого допустимого плана перевозок при заданных платежах ( и ) одна и та же и от плана к плану не меняется.

До сих пор мы никак не связывали платежи ( и ) и псевдостоимости с истинными стоимостями перевозок . Теперь мы установим между ними связь. Предположим, что план невырожденный (число базисных клеток в таблице перевозок равно (). Для всех этих клеток . Определим платежи ( и ) так, чтобы во всех базисных клетках псевдостоимости были ровны стоимостям:

, при

Что касается свободных клеток (где ), то в них соотношение между псевдостоимостями и стоимостями может быть какое угодно.

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

Если для всех базисных клеток плана ()

,

а для всех свободных клеток ()

,

то план является оптимальным и никакими способами улучшен быть не может.

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

(для всех базисных клеток ) (1)

(для всех свободных клеток ) (2)

называется потенциальным планом, a соответствующие ему платежи ( и ) -- потенциалами пунктов и . Пользуясь этой терминологией вышеупомянутую теорему можно сформулировать так: Всякий потенциальный план является оптимальным. Итак, для решения транспортной задачи нам нужно одно -- построить потенциальный план. Оказывается, его можно построить методом последовательных приближений, задаваясь сначала какой-то произвольной системой платежей, удовлетворяющей условию (1). При этом в каждой базисной клетке получиться сумма платежей, равная стоимости перевозок в данной клетке; затем, улучшая план следует одновременно менять систему платежей. Так, что они приближаются к потенциалам. При улучшении плана нам помогает следующее свойство платежей и псевдостоимостей: Какова бы ни была система платежей ( и ) yудовлетворяющая условию (1), для каждой свободной клетки цена цикла пересчёта равна разности между стоимостью и псевдостоимостью в данной клетке : .

Таким образом, при пользовании методом потенциалов для решения транспортной задачи отпадает наиболеетрудоёмкийэлемент распределительного метода: поиски циклов c отрицательной ценой.

Процедура построения потенциального (оптимального) плана состоит в следующем.

B качестве первого приближения к оптимальному плану берётся любой допустимый план (например, построенный способом минимальной стоимости по строке). В этом плане m + n - 1 базисных клеток, где m -- число строк, n -- число столбцов транспортной таблицы. Для этого плана можно определить платежи ( и ), так, чтобы в каждой базисной клетке выполнялось условие:

Уравнений всего m + n - 1, a число неизвестных равно m + n. Следовательно, одну из этих неизвестных можно задать произвольно (например, равной нулю). После этого из m + n - 1 уравнений (3) можно найти остальные платежи , , a по ним вычислить псевдостоимости: для каждой свободной клетки.

ПН ПО
	10	8	5 42	6 6	9	0
	6 4	7	8	6	5 26	-1
	8	7 27	10	8	7 0	1
	7 14	5	4	6 6	8	0
	7	6	5	6	6

Если оказалось, что все эти псевдостоимости не превосходят стоимостей

,

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

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

Теперь будем перемещать по циклу число 14, так как оно является минимальным из чисел, стоящих в клетках, помеченных знаком - . При перемещении мы будем вычитать 14 из клеток со знаком - ,и прибавлять к клеткам со знаком + .

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

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

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

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

при ,

если известен потенциал , и

при ,

Если известен потенциал .

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

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

Строят цикл, включающий в свой состав данную клетку и часть клеток, занятых опорным решением. B клетках цикла расставляют поочередно знаки «+» и «-», начиная с «+» в клетке с наибольшей положительной оценкой. Осуществляют сдвиг (перераспределение груза) по циклу на величину . Клетка со знаком «-», в которой достигается , остается пустой. Если минимум достигается в нескольких клетках, то одна из них остается пустой, а в остальных проставляют базисные нули, чтобы число занятых клеток оставалось равным .

Далее переходи к пункту 3.

При этом стоимость всей перевозки изменялась следующим образом:

Следует отметить так же, что оптимальный план может иметь и другой вид, но его стоимость останется такой же .

Транспортная задача с неправильным балансом.

Решить транспортную задачу, исходные данные которой таковы:

	200	200	300	400
200	4	3	2	1
300	2	3	5	6
500	6	7	9	12

Решение:

Проверяем выполнение необходимого и достаточного условия разрешимости задачи. Находим суммарные запасы поставщиков и суммарные запросы потребителей:

, .

Задача с неправильным балансом. Вводим четвертого, фиктивного поставщика с запасами и нулевыми стоимостями перевозок единиц груза (14).

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

Для проверки оптимальности опорного решения необходимо найти потенциалы. По признаку оптимальности в каждой занятой опорным решением клетке таблицы транспортной задачи сумма потенциалов равна стоимости ( при ). Записываем систему уравнений для нахождения потенциалов и решаем ее:

Система состоит из семи уравнений и имеет восемь переменных. Система неопределенная. Одному из потенциалов задаем значение произвольно: пусть . Остальные потенциалы находятся однозначно:

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

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

Проверяем опорное решение на оптимальность. C этой целью вычисляем оценки для всех незаполненных клеток таблицы (для всех занятых клеток ):

Положительные оценки записываем в левые нижние углы соответствующих клеток таблицы, вместе отрицательных ставим знак «-».

Начальное опорное решение не является оптимальным, так как имеется положительная оценка .

Переходим к новому опорному решению. Для клетки (2, 4) с положительной оценкой строим цикл. Ставим в эту клетку знак «+», присоединяем ее к занятым клеткам и, применяя метод вычеркивания, находим цикл (2, 4), (3, 4), (3, 2), (2, 2). Цикл изображен в таблице. B угловых точках цикла расставляем поочередно знаки «+» и «-», начиная с «+» в клетке (2, 4). B клетки, отмеченные знаком «+», добавляется груз , а из клеток, отмеченных знаком «-», убавляется такой же по величине груз. Определяем величину груза , перераспределяемого по циклу. Она равна значению наименьшей из перевозок в клетках цикла, отмеченных знаком «-»: . Осуществляем сдвиг по циклу на величину . получаем второе опорное решение .

Вычисляем оценки:

Все оценкинеположительные. Следовательно, решение является оптимальным. Вычисляем значение целевой функции на этом решений:

.

Ответ: при

Решение транспортной задачи с помощью ЭВМ:

Постановка задачи.

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

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

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

Заключение

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

Список использованной литературы

1. Сборник задач по высшей математике /Учебное пособие под редакцией проф. B. И. Ермакова./ -M.: 2002 г.

2. Исследование операции в экономике./Под редакцией проф. H.Ш. Кремера/ -M.: 2002г.

3. И. Л. Акулич. Математическое программирование в примерах и задачах. «Высшая школа», -М.: 1986 г.

4. Канторович Л. B., Горстко A. Б. Математическое оптимальное программирование В Экономике. -M.: 1968 г.

5. Применение пакетов прикладных программ по экономика-математическим метод...