14

Федеральное государственное образовательное учреждение

высшего профессионального образования

Пермская сельскохозяйственная академия имени академика д. Н. Прянишникова

Факультет землеустройства и кадастра

Кафедра земельного кадастра

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

по специальности 120303

“Городской кадастр”

Выполнил: студент группы ГК 42 а

Кокшарова Т.Н._________________

“____”_____________________2009

Проверил: преподаватель

Осокина Н.В.__________________

“____”____________________2009

Пермь 2009

Содержание

Задание……………………………………………………………………………….……3

Введение…………………………………………………………………………….…….4

1. Проверка задач на сбалансированность…………………………………………...…6

2. Составление базисного плана способом северо-западного угла, расчет функции цели базисного плана……………………………………………………………….……7

3. Составление базисного плана методом наилучшего элемента на максимальное значение функции цели. Расчет максимального значения функции цели базисного плана……………………………………………………………………………………….9

4. Составление базисного плана методом аппроксимации (Фогеля) на минимальное значение функции цели. Расчет минимального значения функции цели базисного плана………………………………………………………………………….………….10

5. Сравнение результатов решения двух базисных планов…………………….…….11

6. Проверка базисного плана, составленного методом наилучшего элемента на максимальное значение функции цели, на оптимальность методом потенциалов. Улучшение плана до оптимального результата…………………………….…………12

7. Проверка базисного плана, составленного методом аппроксимации (Фогеля) на минимальное значение функции цели, на оптимальность методом потенциалов. Улучшение плана до оптимального результата……………………………………….16

Задание:

На минимум (67 вариант).

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

Таблица 1 – Задание для решения

Пункты хранения	Расстояния от рабочих участков до пунктов хранения, км				Макс. вмести-мость зернохра-нилищ, тонн
	Участок 1	Участок 2	Участок 3	Участок 4
База 1	15	2	4	19	320
База 2	3	4	14	19	780
База 3	22	13	5	15	1430
База 4	2	6	15	3	460
База 5	8	25	11	29	1060
Объем зерна, перевозимого с уч-ка, тонн	200	1650	1500	600	4050 3950

Введение

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

Идея этого метода принадлежит отечественным ученым (А. Толстой, Л.В. Канторович), которые в 1939-1940 г., по существу, поставили и решили транспортную задачу с использованием методов потенциалов. Аналогичный метод, отличающийся лишь небольшой деталью, был предложен независимо в 1951 г. американским ученым Дж. Данцигом и назван им модифицированным распределительным методом.

Первоначально распределительный метод применялся в задачах, связанных с транспортировкой грузов, их распределением между несколькими пунктами отправления и приема; поэтому он известен также под названием «транспортная задача».

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

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

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

Первый базисный план может составляться несколькими методами:

1. метод северо-западного угла;

2. метод наилучших оценок;

3. метод аппроксимации.

1. Проверка задач на сбалансированность.

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

ΣА_i=ΣВj

На минимум ΣА_i=4050, ΣВj=3950 → возникает открытая модель транспортной задачи.